- 簡述
- 圖相關的符号符号
- 相似度矩陣S
- 拉普拉斯矩陣L性質
- 譜聚類算法
- 總結
一、簡述
聚類是對探索性資料分析最廣泛使用的技術，在現在各個科學領域中處理沒有類标的資料時，人們總是想通過确定資料中不同樣本的歸類，來擷取對資料的直覺印象。傳統的聚類方法有很多，像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
拉普拉斯矩陣有如下的一些重要性質：
- 對于任意一個向量，我們都有如下的等式恒成立：
- 拉普拉斯L矩陣是對稱半正定矩陣（特征值非負數）
- L最小的特征值為0，對應的特征向量為全1向量。
- 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直接對樣本聚類會更快。剛開始你需要先了解譜聚類的整個運作流程。然後再帶着這個流程去分析每一部分會更好了解些。本次講解并沒有涉及深層次的原理，比如為什麼用拉普拉斯矩陣能夠解決圖的均勻分割問題，拉普拉斯矩陣的這些性質怎麼得來的，并且直覺上這些性質意味着什麼。我會在下次詳細講解這些性質的由來，并講解通過拉普拉斯矩陣如何去巧妙地解決聚類問題。