譜聚類演算法

04-02

以下內容來自劉建平Pinard-博客園的學習筆記，總結如下：

1 譜聚類（spectral clustering）原理總結

譜聚類（spectral clustering）是廣泛使用的聚類演算法，比起傳統的K-Means演算法，譜聚類對數據分布的適應性更強，聚類效果也很優秀，同時聚類的計算量也小很多，更加難能可貴的是實現起來也不複雜。

在處理實際的聚類問題時，個人認為譜聚類是應該首先考慮的幾種演算法之一。下面我們就對譜聚類的演算法原理做一個總結。

1.1 譜聚類概述

譜聚類是從圖論中演化出來的演算法，後來在聚類中得到了廣泛的應用。它的主要思想是把所有的數據看做空間中的點，這些點之間可以用邊連接起來。距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，通過對所有數據點組成的圖進行切圖，讓切圖後不同的子圖間邊權重和儘可能的低，而子圖內的邊權重和儘可能的高，從而達到聚類的目的。

乍一看，這個演算法原理的確簡單，但是要完全理解這個演算法的話，需要對圖論中的無向圖，線性代數和矩陣分析都有一定的了解。下面我們就從這些需要的基礎知識開始，一步步學習譜聚類。

1.2 譜聚類基礎之一：無向權重圖

由於譜聚類是基於圖論的，因此我們首先溫習下圖的概念。對於一個圖 $G$ ，一般用點的集合 $V$ 和邊的集合 $E$ 來描述。即為 $G(V,E)$ 。其中 $V$ 即為我們數據集裡面所有的點 $(v_{1},v_{2},...,v_{n})$ 。對於 $V$ 中的任意兩個點，可以有邊連接，也可以沒有邊連接。我們定義權重 $w_{ij}$ 為點 $v_{i}$ 和點 $v_{j}$ 之間的權重。由於我們是無向圖，所以 $W_{ij}=W_{ji}$ 。

對於有邊連接的兩個點 $v_{i}$ 和 $v_{j}$ ， $w_{ij}>0$ ，對於沒有邊連接的兩個點 $v_{i}$ 和 $v_{j}$ ， $w_{ij}=0$ .對於圖中的任意一個點 $v_{i}$ ,它的度 $d_{i}$ 定義為和它相連的所有邊的權重之和，即

利用每個點度的定義，我們可以得到一個nxn的度矩陣D,它是一個對角矩陣，只有主對角線有值，對應第i行的第i個點的度數，定義如下：

利用所有點之間的權重值，我們可以得到圖的鄰接矩陣W，它也是一個nxn的矩陣，第i行的第j個值對應我們的權重 $w_{ij}$ 。

除此之外，對於點集V的的一個子集A?V，我們定義：

1.3 譜聚類基礎之二：相似矩陣

在上一節我們講到了鄰接矩陣W，它是由任意兩點之間的權重值 $w_{ij}$ 組成的矩陣。通常我們可以自己輸入權重，但是在譜聚類中，我們只有數據點的定義，並沒有直接給出這個鄰接矩陣，那麼怎麼得到這個鄰接矩陣呢？

基本思想是，距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，不過這僅僅是定性，我們需要定量的權重值。一般來說，我們可以通過樣本點距離度量的相似矩陣S來獲得鄰接矩陣W。

構建鄰接矩陣W的方法有三類。?-鄰近法，K鄰近法和全連接法。

從上式可見，兩點間的權重要不就是?,要不就是0，沒有其他的信息了。距離遠近度量很不精確，因此在實際應用中，我們很少使用?-鄰近法。

第二種定義鄰接矩陣W的方法是K鄰近法，利用KNN演算法遍歷所有的樣本點，取每個樣本最近的k個點作為近鄰，只有和樣本距離最近的k個點之間的 $w_{ij}>0$ 。但是這種方法會造成重構之後的鄰接矩陣W非對稱，我們後面的演算法需要對稱鄰接矩陣。為了解決這種問題，一般採取下面兩種方法之一：

第三種定義鄰接矩陣W的方法是全連接法，相比前兩種方法，第三種方法所有的點之間的權重值都大於0，因此稱之為全連接法。

可以選擇不同的核函數來定義邊權重，常用的有多項式核函數，高斯核函數和Sigmoid核函數。最常用的是高斯核函數RBF，此時相似矩陣和鄰接矩陣相同：

在實際的應用中，使用第三種全連接法來建立鄰接矩陣是最普遍的，而在全連接法中使用高斯徑向核RBF是最普遍的。

1.4 譜聚類基礎之三：拉普拉斯矩陣

單獨把拉普拉斯矩陣(Graph Laplacians)拿出來介紹是因為後面的演算法和這個矩陣的性質息息相關。它的定義很簡單，拉普拉斯矩陣L=D?W。D即為我們第二節講的度矩陣，它是一個對角矩陣。而W即為我們第二節講的鄰接矩陣，它可以由我們第三節的方法構建出。

拉普拉斯矩陣有一些很好的性質如下：

1.5 譜聚類基礎之四：無向圖切圖

對於無向圖G的切圖，我們的目標是將圖G(V,E)切成相互沒有連接的k個子圖，每個子圖點的集合為：

那麼如何切圖可以讓子圖內的點權重和高，子圖間的點權重和低呢？

一個自然的想法就是最小化 $cut(A_{1},A_{2},...,A_{k})$ ，但是可以發現，這種極小化的切圖存在問題，如下圖：

我們選擇一個權重最小的邊緣的點，比如C和H之間進行cut，這樣可以最小化 $cut(A_{1},A_{2},...,A_{k})$ ，但是卻不是最優的切圖，如何避免這種切圖，並且找到類似圖中"Best Cut"這樣的最優切圖呢？我們下一節就來看看譜聚類使用的切圖方法。

1.6 譜聚類之切圖聚類

為了避免最小切圖導致的切圖效果不佳，我們需要對每個子圖的規模做出限定，一般來說，有兩種切圖方式，第一種是RatioCut，第二種是Ncut。下面我們分別加以介紹。

1.6.1 RatioCut切圖

RatioCut切圖為了避免第五節的最小切圖，對每個切圖，不光考慮最小化 $cut(A_{1},A_{2},...,A_{k})$ ，它還同時考慮最大化每個子圖點的個數，即：

那麼怎麼最小化這個RatioCut函數呢？牛人們發現，RatioCut函數可以通過如下方式表示。

注意到 $H$ 矩陣裡面的每一個指示向量都是n維的，向量中每個變數的取值為0或者 $frac{1}{sqrt{left| A_{j} ight|}}$ ，就有 $2^{n}$ 種取值，有k個子圖的話就有k個指示向量，共有 $k 2^{n}$ 種 $H$ ，因此找到滿足上面優化目標的H是一個NP難的問題。那麼是不是就沒有辦法了呢？

注意觀察 $tr(H^{T}LH)$ 中每一個優化子目標 $h_{i}^{T}Lh_{i}$ ，其中 $h$ 是單位正交基， $L$ 是對稱矩陣，此時 $h_{i}^{T}Lh_{i}$ 的最大值為 $L$ 的最大特徵值，最小值是 $L$ 的最小特徵值。如果你對主成分分析PCA很熟悉的話，這裡很好理解。在PCA中，我們的目標是找到協方差矩陣（對應此處的拉普拉斯矩陣L）的最大的特徵值，而在我們的譜聚類中，我們的目標是找到目標的最小的特徵值，得到對應的特徵向量，此時對應二分切圖效果最佳。也就是說，我們這裡要用到維度規約的思想來近似去解決這個NP難的問題。

對於 $h_{i}^{T}Lh_{i}$ ，目標是找到最小的 $L$ 的特徵值，而對於 $tr(H^{T}LH)=sum_{i=1}^{k}{h_{i}^{T}}Lh_{i}$ ，則我們的目標就是找到k個最小的特徵值，一般來說，k遠遠小於n，也就是說，此時我們進行了維度規約，將維度從n降到了k，從而近似可以解決這個NP難的問題。

通過找到L的最小的k個特徵值，可以得到對應的k個特徵向量，這k個特徵向量組成一個nxk維度的矩陣，即為我們的H。一般需要對H里的每一個特徵向量做標準化，即

$h_{i}=frac{h_{i}}{left| h_{i} ight|}$

由於我們在使用維度規約的時候損失了少量信息，導致得到的優化後的指示向量h對應的H現在不能完全指示各樣本的歸屬，因此一般在得到nxk維度的矩陣H後還需要對每一行進行一次傳統的聚類，比如使用K-Means聚類.

1.6.2 Ncut切圖

Ncut切圖和RatioCut切圖很類似，但是把Ratiocut的分母 $left| A_{i} ight|$ 換成 $vol(A_{i})$ 。由於子圖樣本的個數多並不一定權重就大，我們切圖時基於權重也更合我們的目標，因此一般來說Ncut切圖優於RatioCut切圖。

那麼對於 $h_{i}^{T}Lh_{i}$ 有：

推導方式和RatioCut完全一致。也就是說，我們的優化目標仍然是

此時我們的H中的指示向量h並不是標準正交基，所以在RatioCut裡面的降維思想不能直接用。怎麼辦呢？其實只需要將指示向量矩陣H做一個小小的轉化即可。

1.7 譜聚類演算法流程

一般來說，譜聚類主要的注意點為相似矩陣的生成方式（參見第二節），切圖的方式（參見第六節）以及最後的聚類方法（參見第六節）。

最常用的相似矩陣的生成方式是基於高斯核距離的全連接方式，最常用的切圖方式是Ncut。而到最後常用的聚類方法為K-Means。下面以Ncut總結譜聚類演算法流程。

1.8 譜聚類演算法總結

譜聚類演算法是一個使用起來簡單，但是講清楚卻不是那麼容易的演算法，它需要你有一定的數學基礎。如果你掌握了譜聚類，相信你會對矩陣分析，圖論有更深入的理解。同時對降維里的主成分分析也會加深理解。

下面總結下譜聚類演算法的優缺點。

譜聚類演算法的主要優點有：

1）譜聚類只需要數據之間的相似度矩陣，因此對於處理稀疏數據的聚類很有效。這點傳統聚類演算法比如K-Means很難做到。

2）由於使用了降維，因此在處理高維數據聚類時的複雜度比傳統聚類演算法好。

譜聚類演算法的主要缺點有：

1）如果最終聚類的維度非常高，則由於降維的幅度不夠，譜聚類的運行速度和最後的聚類效果均不好。

2) 聚類效果依賴於相似矩陣，不同的相似矩陣得到的最終聚類效果可能很不同。

2 用scikit-learn學習譜聚類

2.1 scikit-learn譜聚類概述

在scikit-learn的類庫中，sklearn.cluster.SpectralClustering實現了基於Ncut的譜聚類，沒有實現基於RatioCut的切圖聚類。同時，對於相似矩陣的建立，也只是實現了基於K鄰近法和全連接法的方式，沒有基於?-鄰近法的相似矩陣。最後一步的聚類方法則提供了兩種，K-Means演算法和 discretize演算法。

對於SpectralClustering的參數，我們主要需要調參的是相似矩陣建立相關的參數和聚類類別數目，它對聚類的結果有很大的影響。當然其他的一些參數也需要理解，在必要時需要修改默認參數。

2.2 SpectralClustering重要參數與調參注意事項

下面我們就對SpectralClustering的重要參數做一個介紹，對於調參的注意事項會一起介紹。

1）n_clusters：代表我們在對譜聚類切圖時降維到的維數（原理篇第7節的k1），同時也是最後一步聚類演算法聚類到的維數(原理篇第7節的k2)。也就是說scikit-learn中的譜聚類對這兩個參數統一到了一起。簡化了調參的參數個數。雖然這個值是可選的，但是一般還是推薦調參選擇最優參數。

2) affinity: 也就是我們的相似矩陣的建立方式。可以選擇的方式有三類，第一類是 nearest _neighbors即K鄰近法。第二類是precomputed即自定義相似矩陣。選擇自定義相似矩陣時，需要自己調用set_params來自己設置相似矩陣。第三類是全連接法，可以使用各種核函數來定義相似矩陣，還可以自定義核函數。最常用的是內置高斯核函數rbf。其他比較流行的核函數有『linear』即線性核函數, 『poly』即多項式核函數, 『sigmoid』即sigmoid核函數。如果選擇了這些核函數，對應的核函數參數在後面有單獨的參數需要調。自定義核函數我沒有使用過，這裡就不多講了。affinity默認是高斯核rbf。一般來說，相似矩陣推薦使用默認的高斯核函數。

3) 核函數參數gamma: 如果我們在affinity參數使用了多項式核函數 poly，高斯核函數『rbf』, 或者sigmoid核函數，那麼我們就需要對這個參數進行調參。

6）kernel_params：如果affinity參數使用了自定義的核函數，則需要通過這個參數傳入核函數的參數。

7 )n_neighbors: 如果我們affinity參數指定為nearest_neighbors即K鄰近法，則我們可以通過這個參數指定KNN演算法的K的個數。默認是10.我們需要根據樣本的分布對這個參數進行調參。如果我們affinity不使用nearest_neighbors，則無需理會這個參數。

8）eigen_solver:1在降維計算特徵值特徵向量的時候，使用的工具。有 None, 『arpack』, 『lobpcg』, 和『amg』4種選擇。如果我們的樣本數不是特別大，無需理會這個參數，使用None暴力矩陣特徵分解即可,如果樣本量太大，則需要使用後面的一些矩陣工具來加速矩陣特徵分解。它對演算法的聚類效果無影響。

9）eigen_tol：如果eigen_solver使用了arpack』，則需要通過eigen_tol指定矩陣分解停止條件。

10）assign_labels：即最後的聚類方法的選擇，有K-Means演算法和 discretize演算法兩種演算法可以選擇。一般來說，默認的K-Means演算法聚類效果更好。但是由於K-Means演算法結果受初始值選擇的影響，可能每次都不同，如果我們需要演算法結果可以重現，則可以使用discretize。

11）n_init：即使用K-Means時用不同的初始值組合跑K-Means聚類的次數，這個和K-Means類裡面n_init的意義完全相同，默認是10，一般使用默認值就可以。如果你的n_clusters值較大，則可以適當增大這個值。

從上面的介紹可以看出，需要調參的部分除了最後的類別數n_clusters，主要是相似矩陣affinity的選擇，以及對應的相似矩陣參數。當我選定一個相似矩陣構建方法後，調參的過程就是對應的參數交叉選擇的過程。對於K鄰近法，需要對n_neighbors進行調參，對於全連接法裡面最常用的高斯核函數rbf，則需要對gamma進行調參。

2.3 SpectralClustering實例

這裡我們用一個例子講述下SpectralClustering的聚類。

我們選擇最常用的高斯核來建立相似矩陣，用K-Means來做最後的聚類。

首先我們生成500個6維的數據集，分為5個簇。由於是6維，這裡就不可視化了，代碼如下：　

　接著我們看看默認的譜聚類的效果：　　

輸出的Calinski-Harabasz分數為：

Calinski-Harabasz Score 14908.9325026　　

由於我們使用的是高斯核，那麼我們一般需要對n_clusters和gamma進行調參。選擇合適的參數值。代碼如下：

輸出如下：

Calinski-Harabasz Score with gamma= 0.01 n_clusters= 3 score: 1979.77096092Calinski-Harabasz Score with gamma= 0.01 n_clusters= 4 score: 3154.01841219Calinski-Harabasz Score with gamma= 0.01 n_clusters= 5 score: 23410.63895Calinski-Harabasz Score with gamma= 0.01 n_clusters= 6 score: 19303.7340877

可見最好的n_clusters是5，而最好的高斯核參數是1或者0.1.

我們可以看看不輸入可選的n_clusters的時候，僅僅用最優的gamma為0.1時候的聚類效果，代碼如下：

輸出為：

Calinski-Harabasz Score 14950.4939717

可見n_clusters一般還是調參選擇比較好。