譜聚類（Spectral Clustering）

本文技術來自“ A Tutorial on Spectral Clustering ”：

• 最近用到了譜聚類算法，在對譜聚類有了初步的了解之後打算寫下這片文章作為筆記。

定義

• 無向圖 G=<V,E> ：V是由資料集構成的圖的頂點；E為每條邊的權值，也就是頂點之間的相似度，換句話說E是每兩個資料集之間的相似度。
• 相似度矩陣。計算相似度，計算頂點之間的相似度。想用什麼距離判斷方法就用什麼，隻要符合資料的性質即可，如Nearest neighbors、高斯核函數等等。

• 鄰接矩陣 W (Adjacency Matrix)：子圖A和子圖 B 之間所有邊的權值之和(ωij為頂點i到頂點j的權值,如果兩個點不相鄰,權值為0)：

  W(A,B)=∑i∈A,j∈Bωij

  

• 度矩陣(Degree Matrix) D ：與頂點vi相連的所有邊的權值累加和為該頂點的 d (Degree)，由所有頂點v構成的 d 組合成度矩陣D (Degree Matrix):

  di=∑j=1nωij

  

  A Tutorial on Spectral Clustering 這片文章裡稱為 Degree Matrix，是圖論裡的概念，我不知道翻譯為度矩陣是否準确。
• Laplacian 矩陣 L ：L=D−W

• 

  Laplacian矩陣性質為:

  f′Lf=12∑i,j=1Nωij(fi−fj)2，

  其中 f 為任意向量，L=D−W，W(A,B)=∑i∈A,j∈Bωij，di=∑nj=1ωij

  證明過程：

  f′Lf=f′Df−f′Wf=12(∑i=1ndif2i−2∑i,j=1nfifjωij−∑j=1ndif2j)=12∑i,j=1Nωij(fi−fj)2

譜聚類原理

• 目的：給定資料集 X ，轉化為圖G=<V,E>，将圖 G 劃分為k個子圖，使分割後的k個子圖中各個子圖之間頂點V的相似度低，同一子圖内頂點 V 的相似度高。
• 分割方法：

RatioCut (first introduced by Hagen and Kahng, 1992)

NormalizedCut (first introduced by Shi and Malik, 2000)

RatioCut

1 确定目标函數

假設由資料集得到圖 G ，我們要把圖G劃分為 k 個子集，記做Ai,...,Ak，為了使分割後的 k 個子圖中各個子圖之間頂點V的相似度盡可能低，同一子圖内頂點 V 的相似度盡可能高，得目标函數：

cut(Ai,...,Ak)=12∑i=1kW(Ai,Ai⎯⎯⎯⎯)

Ai 表示第 i 個子圖，Ai⎯⎯⎯⎯為 Ai 的補集， W(Ai,Ai⎯⎯⎯⎯) 表示子圖 Ai 與其他所有子圖（即 Ai⎯⎯⎯⎯ ）之間的所有邊的權重之和（換言之，如果要分成 k 個組，那麼其代價就是進行分割時去掉的邊的權值的總和）。我們要最小化目标函數：

mincut(Ai,...,Ak)=min(12∑i=1kW(Ai,Ai⎯⎯⎯⎯))

此時有個問題：假設 k=2 ，目标函數 cut() 有可能會将圖分成一個點和 n−1 個點的集合(即{ H },{A,B,C,D,E,F,G})，但{ A,B,C,H }, { D,E,F,G }反而是更理想的結果。（如下圖所示）

圖檔來自http://www.cnblogs.com/sparkwen/p/3155850.html

針對上面問題，改進後的目标函數為：

RatioCut(Ai,...,Ak)=12∑i=1kW(Ai,Ai⎯⎯⎯⎯)|Ai⎯⎯⎯⎯|=12∑i=1kcut(Ai,Ai⎯⎯⎯⎯)|Ai⎯⎯⎯⎯|

其中|Ai⎯⎯⎯⎯|為子圖Ai中頂點V的個數。

RatioCut 的原理很簡單：如果某一子圖中包含的頂點個數越少，那麼該圖的值就越大。也就解決了上述問題。

2 最小化目标函數

定義向量 fi=⎧⎩⎨⎪⎪⎪⎪|Ai⎯⎯⎯||Ai|‾‾‾√,−|Ai⎯⎯⎯||Ai|‾‾‾√,if vi∈A if vi∈A⎯⎯⎯

由 Laplacian 矩陣性質 f′Lf=12∑Ni,j=1ωi,j(fi−fj)2得:

f′Lf⇒2|V|⋅RatioCut(A,A⎯⎯⎯)

證明過程：

 f′Lf=12∑i,j=1Nωi,j(fi−fj)2=12⎛⎝⎜⎜⎜∑i∈A,j∈A⎯⎯ωij⎛⎝⎜⎜|A⎯⎯⎯||A|‾‾‾√+|A||A⎯⎯⎯|‾‾‾√⎞⎠⎟⎟2+∑i∈A,j∈A⎯⎯ωij⎛⎝⎜⎜−|A⎯⎯⎯||A|‾‾‾√−|A||A⎯⎯⎯|‾‾‾√⎞⎠⎟⎟2⎞⎠⎟⎟⎟=cut(A,A⎯⎯⎯)(|A⎯⎯⎯||A|+|A||A⎯⎯⎯|+2)=cut(A,A⎯⎯⎯)(|A⎯⎯⎯|+|A||A|+|A⎯⎯⎯|+|A||A⎯⎯⎯|+2)=2|V|⋅RatioCut(A,A⎯⎯⎯)

大緻上我們可得：

minRatioCut(A,A⎯⎯⎯)⇒minf′Lf⇒minL⇒minλ

即求得 Laplacian 矩陣的最小特征值 λ ,但 Laplacian 矩陣是半正定矩陣，最小特征值 λ 為 0 ，則根據 Rayleigh-Ritz 定理(e.g., see Section 5.5.2. of L¨utkepohl, 1997)取第二小特征值即可。

具體推導内容請看 A Tutorial on Spectral Clustering (https://arxiv.org/abs/0711.0189)

聚類過程

• 1 根據資料集建構圖G=<V,E>
• 2 min RatioCut将圖G分割為k個子圖
• 3 求得鄰接矩陣W、度矩陣（DegreeMatrix）D，得到Laplacian矩陣L
• 4 求L的前K個特征值及對應的特征向量（由小到大排列）
• 5 把k個特征向量組成shape=N∗k矩陣
• 6 用k−means對矩陣進行聚類

也就是利用拉普拉斯矩陣的特征值分析再利用 k-means 算法進行聚類。

代碼

scikit 有相應的包：sklearn.cluster.SpectralClustering

# -*- coding: utf-8 -*-
from sklearn import cluster

spectral = cluster.SpectralClustering(n_clusters=CLUSTER_NUM,   
                eigen_solver='arpack',
                affinity="nearest_neighbors").fit(data)
spectral.labels_  # 得到清單，内容為 data 所對應簇的下标
           

具體内容請看官方文檔：sklearn.cluster.SpectralClustering

Reference

[1]：Luxburg U V. A tutorial on spectral clustering[J]. Statistics & Computing, 2007, 17(4):395-416.

[2]：http://www.cnblogs.com/fengyan/archive/2012/06/21/2553999.html

[3]：http://www.cnblogs.com/sparkwen/p/3155850.html

[4]：http://blog.csdn.net/liu1194397014/article/details/52990015