一．簡述
聚類是對探索性數據分析最廣泛使用的技術，在現在各個科學領域中處理沒有類標的數據時，人們總是想通過確定數據中不同樣本的歸類，來獲取對數據的直觀印象。傳統的聚類方法有很多，像K-means，single linkage等，但是k-means算法有些缺點，比如當樣本維度特別大的時候，k-means的計算量是很大的。最近幾年時間，譜聚類成為了最受歡迎的聚類算法，它很容易執行，能夠用標準的線代軟件高效地解決，而且比傳統的聚類算法比如k-means表現效果要好很多。不管怎樣，初次一瞥譜聚類時看起來很神秘，不太能弄透為什麼譜聚類能夠用於聚類。為了介紹譜聚類到底如何能夠作聚類，我們需要先了解相似度矩陣，拉普拉斯矩陣的概念，然後才能最終理解譜聚類原理。
二．圖相關的符號標記
現有給定樣本x_1,......x_n，想要用譜聚類來給這些樣本集進行聚類的話，需要將這些樣本之間的聯繫用圖的形式來表示。在這裡介紹下圖的相關符號。假設有若干個樣本x_i被歸為一類，該集合為A。這裡先給出相關需要的概念，剛看到不理解不用擔心，先記住他們是做什麼的就行。
設定：
1）譜聚類中，我們需要描述樣本與樣本間的聯繫，這時候需要構建一個圖。G=（V，E）是一個無向圖，其中V={v_1,...,v_n}代表這些樣本點，E是代表不同點之間相似度，其中e_ij代表v_i與v_j之間的權值（有多種方式構建此相似度），用w_ij表示，其中w_ij>=0，構成了鄰接矩陣W（兩樣本v_i與v_j之間有連接則w_ij>0,無連接則w_ij=0），因為G是無向圖，所以可知道w_ij=w_ji。
2）度矩陣D，其中
，代表v_i樣本與其他v_j樣本的權重之和。
三．相似度矩陣S
譜聚類算法需要的輸入是一個圖，該圖包含了所有樣本與樣本之間的相似度，該圖為一個矩陣，大小是n*n。這樣通過某種標準定義了樣本之間聯繫構建出來的矩陣，我們叫做它相似度矩陣。有很多種構建相似度矩陣的方式，比如K近鄰構建的相似度矩陣，高斯相似度矩陣等，eg:用高斯相似度S（x,y）計算兩樣本間的聯繫時：
公式一
其他相似度構造標準在此不再詳細闡述，你需要知道，這些不同的構建相似度矩陣的方式，他們有各自對樣本間相似度的構建標準，通過他們，給定的樣本就能變成一個相似度矩陣S，S_ij代表樣本v_i與v_j之間相似度，這裡的出的S_ij矩陣其實就是用作於後邊的W_ij鄰接矩陣。這裡需要指出的是，目前還沒有理論結果指明在不同的數據訓練中使用哪種方案構建相似度矩陣最合適。
四．拉普拉斯矩陣L性質
譜聚類中最重要的工具就是拉普拉斯矩陣，在這裡我們給出拉普拉斯矩陣的定義和一些他的重要性質。之前上文已經給出了一些相關符號的定義，我們已經根據不同的相似度標準求出了樣本與樣本之間的相似度，構建了鄰接矩陣W。這裡我們也知道了度矩陣D
：。而譜聚類中所需要的最重要的拉普拉斯矩陣L：
L=D-W
拉普拉斯矩陣有如下的一些重要性質：
1）對於任意一個向量
，我們都有如下的等式恆成立：
2）拉普拉斯L矩陣是對稱半正定矩陣（特徵值非負數）
3）L最小的特徵值為0，對應的特徵向量為全1向量。
4）L有多少個0特徵值，樣本構成的圖G中就存在多少個連通分量（最大連通子圖）
以上就是拉普拉斯矩陣L所具有的一些重要的性質，證明比較多，本次講解就不詳細展開，以後會將其單獨羅列出來並講下譜聚類更深入的細節，體會下當初發明人多麼巧妙的用拉普拉斯矩陣去解決樣本的均勻聚類問題。
五．譜聚類算法
將所有的樣本構建成一個圖，x_i與x_j之間的關聯程度構建了圖對應的邊。那現在我們就得到了一個圖，圖上有所有樣本和樣本間的聯繫。譜聚類算法是對這個圖進行合理的切分，分成幾類，這樣切分得到的每類都比較均勻。
輸入：樣本x_i，需要聚類的個數k
- 構建相似度矩陣S，樣本間x_i已經通過高斯相似度構建出了相似度矩陣S， 也就是鄰接矩陣W。
- 計算出度矩陣D
- 計算出拉普拉斯矩陣L=D-W
- 計算出L前k個最小的特徵向量v_1,...,v_k
- 將前k個特徵向量組合成一個矩陣V，其中第i列對應v_i列向量。
- 該矩陣V的每一行對應代表x_i的低維度的表示y_i。
- 對所有y_i進行k-means聚類，聚成k類
輸出：k個類，每個樣本標記聚成的類別。
譜聚類切割出來的圖的特點，他會讓所切分的樣本構建的圖比較均勻。
六．總結
本次只是簡單的闡述了下譜聚類所需要的一些相關和算法流程。想要對樣本進行合理的切割，用譜聚類算法相對於傳統的k-means算法會更高效，聚類的效果會均勻。譜聚類需要先將樣本通過某種標準計算出樣本間的相似度構建成相似度矩陣，也就是鄰接矩陣。然後計算拉普拉斯矩陣，求出拉普拉斯矩陣對應的前k個最小的特徵值，得到對應的特徵向量組成的矩陣V後，用V來給樣本在低維度上進行聚類，相比k-means直接對樣本聚類會更快。剛開始你需要先了解譜聚類的整個運作流程。然後再帶著這個流程去分析每一部分會更好理解些。本次講解並沒有涉及深層次的原理，比如為什麼用拉普拉斯矩陣能夠解決圖的均勻分割問題，拉普拉斯矩陣的這些性質怎麼得來的，並且直觀上這些性質意味著什麼。
對深度學習感興趣，熱愛Tensorflow的小夥伴，歡迎關注我們的網站http://www.panchuang.net 我們的公眾號：磐創AI。
閱讀更多 人工智能遇見磐創 的文章
