在處理實際的聚類問題時，個人認為譜聚類是應該首先考慮的幾種算法之一。下面我們就對譜聚類的算法原理做一個總結。
1.1 譜聚類概述
譜聚類是從圖論中演化出來的算法，後來在聚類中得到了廣泛的應用。它的主要思想是把所有的數據看做空間中的點，這些點之間可以用邊連接起來。距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，通過對所有數據點組成的圖進行切圖，讓切圖後不同的子圖間邊權重和儘可能的低，而子圖內的邊權重和儘可能的高，從而達到聚類的目的。
乍一看，這個算法原理的確簡單，但是要完全理解這個算法的話，需要對圖論中的無向圖，線性代數和矩陣分析都有一定的了解。下面我們就從這些需要的基礎知識開始，一步步學習譜聚類。
1.2 譜聚類基礎之一：無向權重圖
由於譜聚類是基於圖論的，因此我們首先溫習下圖的概念。對於一個圖 ，一般用點的集合 和邊的集合 來描述。即為 。其中 即為我們數據集裡面所有的點 。對於 中的任意兩個點，可以有邊連接，也可以沒有邊連接。我們定義權重 為點 和點 之間的權重。由於我們是無向圖，所以 。
對於有邊連接的兩個點 和 ， ，對於沒有邊連接的兩個點 和 ， .對於圖中的任意一個點 ,它的度 定義為和它相連的所有邊的權重之和，即
利用每個點度的定義，我們可以得到一個nxn的度矩陣D,它是一個對角矩陣，只有主對角線有值，對應第i行的第i個點的度數，定義如下：
利用所有點之間的權重值，我們可以得到圖的鄰接矩陣W，它也是一個nxn的矩陣，第i行的第j個值對應我們的權重 。
除此之外，對於點集V的的一個子集A⊂V，我們定義：
1.3 譜聚類基礎之二：相似矩陣
在上一節我們講到了鄰接矩陣W，它是由任意兩點之間的權重值 組成的矩陣。通常我們可以自己輸入權重，但是在譜聚類中，我們只有數據點的定義，並沒有直接給出這個鄰接矩陣，那麼怎麼得到這個鄰接矩陣呢？
基本思想是，距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，不過這僅僅是定性，我們需要定量的權重值。一般來說，我們可以通過樣本點距離度量的相似矩陣S來獲得鄰接矩陣W。
構建鄰接矩陣W的方法有三類。ϵ-鄰近法，K鄰近法和全連接法。
從上式可見，兩點間的權重要不就是ϵ,要不就是0，沒有其他的信息了。距離遠近度量很不精確，因此在實際應用中，我們很少使用ϵ-鄰近法。
第二種定義鄰接矩陣W的方法是K鄰近法，利用KNN算法遍歷所有的樣本點，取每個樣本最近的k個點作為近鄰，只有和樣本距離最近的k個點之間的 。但是這種方法會造成重構之後的鄰接矩陣W非對稱，我們後面的算法需要對稱鄰接矩陣。為了解決這種問題，一般採取下面兩種方法之一：
第三種定義鄰接矩陣W的方法是全連接法，相比前兩種方法，第三種方法所有的點之間的權重值都大於0，因此稱之為全連接法。
可以選擇不同的核函數來定義邊權重，常用的有多項式核函數，高斯核函數和Sigmoid核函數。最常用的是高斯核函數RBF，此時相似矩陣和鄰接矩陣相同：
在實際的應用中，使用第三種全連接法來建立鄰接矩陣是最普遍的，而在全連接法中使用高斯徑向核RBF是最普遍的。
1.4 譜聚類基礎之三：拉普拉斯矩陣
單獨把拉普拉斯矩陣(Graph Laplacians)拿出來介紹是因為後面的算法和這個矩陣的性質息息相關。它的定義很簡單，拉普拉斯矩陣L=D−W。D即為我們第二節講的度矩陣，它是一個對角矩陣。而W即為我們第二節講的鄰接矩陣，它可以由我們第三節的方法構建出。
拉普拉斯矩陣有一些很好的性質如下：
1.5 譜聚類基礎之四：無向圖切圖
對於無向圖G的切圖，我們的目標是將圖G(V,E)切成相互沒有連接的k個子圖，每個子圖點的集合為：
那麼如何切圖可以讓子圖內的點權重和高，子圖間的點權重和低呢？
一個自然的想法就是最小化 ，但是可以發現，這種極小化的切圖存在問題，如下圖：
我們選擇一個權重最小的邊緣的點，比如C和H之間進行cut，這樣可以最小化 ，但是卻不是最優的切圖，如何避免這種切圖，並且找到類似圖中"Best Cut"這樣的最優切圖呢？我們下一節就來看看譜聚類使用的切圖方法。
1.6 譜聚類之切圖聚類
為了避免最小切圖導致的切圖效果不佳，我們需要對每個子圖的規模做出限定，一般來說，有兩種切圖方式，第一種是RatioCut，第二種是Ncut。下面我們分別加以介紹。
1.6.1 RatioCut切圖
RatioCut切圖為了避免第五節的最小切圖，對每個切圖，不光考慮最小化 ，它還同時考慮最大化每個子圖點的個數，即：
那麼怎麼最小化這個RatioCut函數呢？牛人們發現，RatioCut函數可以通過如下方式表示。
注意到 矩陣裡面的每一個指示向量都是n維的，向量中每個變量的取值為0或者 ，就有 種取值，有k個子圖的話就有k個指示向量，共有 種 ，因此找到滿足上面優化目標的H是一個NP難的問題。那麼是不是就沒有辦法了呢？
注意觀察 中每一個優化子目標 ，其中 是單位正交基， 是對稱矩陣，此時 的最大值為 的最大特徵值，最小值是 的最小特徵值。如果你對主成分分析PCA很熟悉的話，這裡很好理解。在PCA中，我們的目標是找到協方差矩陣（對應此處的拉普拉斯矩陣L）的最大的特徵值，而在我們的譜聚類中，我們的目標是找到目標的最小的特徵值，得到對應的特徵向量，此時對應二分切圖效果最佳。也就是說，我們這裡要用到維度規約的思想來近似去解決這個NP難的問題。
對於 ，目標是找到最小的 的特徵值，而對於 ，則我們的目標就是找到k個最小的特徵值，一般來說，k遠遠小於n，也就是說，此時我們進行了維度規約，將維度從n降到了k，從而近似可以解決這個NP難的問題。
通過找到L的最小的k個特徵值，可以得到對應的k個特徵向量，這k個特徵向量組成一個nxk維度的矩陣，即為我們的H。一般需要對H裡的每一個特徵向量做標準化，即
由於我們在使用維度規約的時候損失了少量信息，導致得到的優化後的指示向量h對應的H現在不能完全指示各樣本的歸屬，因此一般在得到nxk維度的矩陣H後還需要對每一行進行一次傳統的聚類，比如使用K-Means聚類.
1.6.2 Ncut切圖
Ncut切圖和RatioCut切圖很類似，但是把Ratiocut的分母 換成 。由於子圖樣本的個數多並不一定權重就大，我們切圖時基於權重也更合我們的目標，因此一般來說Ncut切圖優於RatioCut切圖。
那麼對於 有：
推導方式和RatioCut完全一致。也就是說，我們的優化目標仍然是
此時我們的H中的指示向量h並不是標準正交基，所以在RatioCut裡面的降維思想不能直接用。怎麼辦呢？其實只需要將指示向量矩陣H做一個小小的轉化即可。
1.7 譜聚類算法流程
一般來說，譜聚類主要的注意點為相似矩陣的生成方式（參見第二節），切圖的方式（參見第六節）以及最後的聚類方法（參見第六節）。
最常用的相似矩陣的生成方式是基於高斯核距離的全連接方式，最常用的切圖方式是Ncut。而到最後常用的聚類方法為K-Means。下面以Ncut總結譜聚類算法流程。
1.8 譜聚類算法總結
譜聚類算法是一個使用起來簡單，但是講清楚卻不是那麼容易的算法，它需要你有一定的數學基礎。如果你掌握了譜聚類，相信你會對矩陣分析，圖論有更深入的理解。同時對降維裡的主成分分析也會加深理解。
下面總結下譜聚類算法的優缺點。
譜聚類算法的主要優點有：
1）譜聚類只需要數據之間的相似度矩陣，因此對於處理稀疏數據的聚類很有效。這點傳統聚類算法比如K-Means很難做到。
2）由於使用了降維，因此在處理高維數據聚類時的複雜度比傳統聚類算法好。
譜聚類算法的主要缺點有：
1）如果最終聚類的維度非常高，則由於降維的幅度不夠，譜聚類的運行速度和最後的聚類效果均不好。
2) 聚類效果依賴於相似矩陣，不同的相似矩陣得到的最終聚類效果可能很不同。
—THE END—