Unified Spectral Clustering with Optimal Graph

04-02

轉載請註明出處：

每周一篇機器學習論文筆記?

zhuanlan.zhihu.com

論文來源：AAAI 2018

論文鏈接：Unified Spectral Clustering with Optimal Graph

論文原作者：Zhao Kang, Chong Peng, Qiang Cheng and Zenglin Xu

Abstract

譜聚類在很多領域有廣泛的應用。大多傳統的譜聚類演算法有三個單獨的步驟：相似性矩陣構建；連續標籤學習；通過k-means聚類演算法將學習後的標籤離散化。這種常見的做法有兩缺點，這可能會導致嚴重的信息丟失還有性能衰減。首先，預先定義好的相似性矩陣對於接下來的聚類可能不是最理想的，而相似性矩陣會高度影響聚類結果。因此，作者提議從數據中自動學習相似性信息，同時考慮「如果有c聚類，相似性矩陣有確切的c個connected components」這樣一個約束。其次，k-means方法對聚類中心初始值設定很敏感。在論文中，作者經轉換得到了一個更好逼近離散類標的新方法。最後上述三個步驟被整合到一個統一的框架，每個步驟通過使用其他兩步驟的結果來不斷朝著一個全局最優的解向前。核方法的性能主要由核的選擇來決定，為了解決「如何對一個特定數據集選擇最合適的核」的問題，作者進一步拓展了模型，讓其有了multiple kernel learning的能力。

Introduction

K-means聚類演算法在各種現實問題中經常被採用。為了解決許多實際數據集的非線性結構問題，kernel k-means（KKM）演算法產生了，它的原理是通過一個非線性轉換將數據點映射到一個更高維的特徵空間，在這個特徵空間里數據點是線性分布的。KMM通常比標準的k-means演算法有更好的效果。為了解決雜訊和極端值的問題，魯棒kernel k-means（RKKM）演算法被提出，這個方法是基於模型的，它的效果很大程度上取決於數據是否符合這個模型。大多數情況下，我們預先是不知道數據分布的，而這個問題在某個程度上可以用multiple kernel learning方法得到緩解。

譜聚類演算法是另一種被廣泛使用的聚類方法，它能夠利用不同的相似性矩陣來探索內部數據結構。相似性矩陣構建方法有以下三種：k-nearest-neighborhood（knn）； $epsilon$ -nearest-neighborhood；The fully connected graph。那麼問題來了，怎樣選擇一個恰當的k或 $epsilon$ 值？如何選擇一個適當的相似性度量去衡量數據點之間的相似性？如何解決雜訊和極端值的不利影響？如何應對在不同維度大小和密度的結構數據？譜聚類的第二步驟是利用相似性矩陣去揭露數據的聚類結構，這是一個NP-hard問題。因此譜聚類解決了這個問題的寬鬆版本（discrete constraint被放寬到允許連續的值），得到了一個可行的近似方法。首先，在拉普拉斯矩陣上執行特徵值分解去得到一個恰當的有連續值的indicator matrix。其次，運用k-means去得到最後的聚類。此時，k-means可能會產生較差的效果，因為它對聚類中心的初始值設定很敏感。

為了解決上述問題，論文中作者提出了一個統一的譜聚類框架。通過解決最優問題，它將從數據中學習得到的相似性矩陣和離散聚類類標聯合在一起，其中的連續聚類類標看做中間產物。這是第一次將傳統譜聚類的三步驟聯合在一起，成了一個優化問題。

Contributions

相似性矩陣自適應地從一個核空間的數據中學習得到，而不是使用預先定義好的相似性矩陣。
不同於現存的譜聚類方法，作者同時學習了相似性矩陣，連續類標和離散聚類類標。
作者基於自己的single kernel model，進一步拓展到能夠去學習the optimal combination of multiple kernels.

Preliminary Knowledge

1.Sparse Representation

Sparse Representation假設了每個數據點都可以由其他數據點的線性組合進行重構，它解決的問題如下：

α > 0 是一個平衡參數，z是相似性矩陣

Sparse Representation有好些特性，比如對雜訊有魯棒性。但在另一方面，模型（1）有一個缺點，它沒有考慮非線性的數據集。

2.Spectral Clustering

譜聚類要求拉普拉斯矩陣 $L$ 作為輸入，有 $L=D-frac{Z^{ op}+Z}{2}$ ，其中 $D$ 是對角矩陣，第 $i$ 對角元素 $sum_{j}^{n}{frac{Z_{ij}+Z_{ij}}{2}}$ 。假設 $X$ 有 $c$ 聚類，譜聚類解決的問題如下：

$F=[f_{1},f_{2},...,f_{n}] op$ 是 $c$ 維的，是聚類的indicator matrix。模型（2）是NP-hard問題，而實際上解決的問題如下（ $F$ 放寬到允許連續的值）：

依據 $c$ 最小特徵值，最優解可以由 $L$ 的 $c$ 特徵向量得到。之後再利用k-means演算法去得到離散的聚類類標。

Model

1.Spectral Clustering with Single Kernel Model

公式（1）有一個缺點就是它假設了所有的數據點是在獨立或者不相交的子空間集合里而且是無雜訊的。在不獨立子空間和非線性原型的情況下，它可能會選擇不同結構的數據點去表示一個數據點，這會使得表示的信息量變少。為充分利用數據信息，作者用一個帶kernelization framework的一般方法確切地闡述了公式(1)。讓 $phi：R^{D} ightarrow$ $H$ 為一個kernel， $X$ 可以轉換成 $phi(X)=[phi(x_{1}),...,phi(x_{n})]$ 。數據樣本 $x_{i}$ 和 $x_{j}$ 的核相似性可以通過 $K_{x_{i}，x_{j}}=<phi(x_{i}),phi(x_{j})>$ 來定義。在新的空間里（數據之間是呈現線性關係的），公式（1）變成了：

為了完成聚類任務，作者提出了帶單核的譜聚類模型 spectral clustering with single kernel (SCSK)：

$alpha,eta, gamma$ 都是罰參數， $Q$ 是旋轉矩陣。在公式（5）中，相似性矩陣和最終的離散聚類類標可以從數據中自動學習得到。後續的優化過程作者設計了一個交替反覆的方法。

第一，固定 $F,P,Q$ ,計算 $Z$ 。其中引進了一個輔助變數 $S$ 來幫助求解，如下：

第二，固定 $F,Z,Q$ ,計算 $P$ 。如下：

第三，固定 $F,Z,P$ ,計算 $Q$ 。如下：

第四， $Z,P,Q$ ,計算 $F$ .如下：

SCSK演算法的函數優化詳情可看論文，演算法如下：

2.Spectral Clustering with Multiple Kernels Model

公式（5）的性能表現極大程度依賴於核的選擇。徹底搜索最合適的核是不實際的，加上真實世界的數據集通常是由帶有各種各樣特徵的不同sources產生，Single kernel method可能不能夠充分利用這樣的信息，而Multiple kernel learning有整合互補信息和確定一個合適的核的能力。

假定有 $r$ 個不同的核函數 { $K^{i}$ } $_{i=1}^{r}$ 。 $ilde{phi}(x)=[sqrt{w_{1}}phi_{1}(x),...,sqrt{w_{r}}phi_{r}(x)] op$

那麼作者提出的帶多核的譜聚類模型 spectral clustering with multiple kernels (SCMK)如下：

不斷重複更新 $Z,F,omega$ ，每一個都會反覆重定義根據其他兩個的結果。優化的過程可見於論文。SCMK演算法如下：

Experiment

實驗詳情可參考論文，效果真的十分出色！

Conclusion

作者將傳統譜聚類的三步驟融合到了一個統一的框架里，每個步驟通過使用其他兩步驟的結果來不斷朝著一個全局最優的解向前，而且不同於預先定義好的相似性矩陣，論文中的相似性矩陣是能夠自動從數據中學習得到。論文有大篇幅的公式，各種運算優化，需要花多點時間，值得一看，實驗效果特別棒！當滿篇幅的公式之後看到實驗篇，簡直眼前一亮。