譜聚類原理介紹

廣義上來說，任何在算法中用到SVD/特征值分解的，都叫Spectral Algorithm。順便說一下，對于任意矩陣隻存在奇異值分解，不存在特征值分解。對于正定的對稱矩陣，奇異值就是特征值，奇異向量就是特征向量。

傳統的聚類算法，如K-Means、EM算法都是建立在凸球形樣本空間上，當樣本空間不為凸時，算法會陷入局部最優，最終結果受初始參數的選擇影響比較大。而譜聚類可以在任意形狀的樣本空間上聚類，且收斂于全局最優解。

譜聚類和CHAMELEON聚類很像，都是把樣本點的相似度放到一個帶權無向圖中，采用“圖劃分”的方法進行聚類。隻是譜聚類算法在進行圖劃分的時候發現計算量很大，轉而求特征值去了，而且最後還在幾個小特征向量組成的矩陣上進行了K-Means聚類。

Simply speaking，譜聚類算法分為3步：

1. 構造一個N×N的權值矩陣W，Wij表示樣本i和樣本j的相似度，顯然W是個對稱矩陣。相似度的計算方法很多了，你可以用歐拉距離、街區距離、向量夾角、皮爾森相關系數等。并不是任意兩個點間的相似度都要表示在圖上，我們希望的權值圖是比較稀疏的，有2種方法：權值小于門檻值的認為是0；K最鄰近方法，即每個點隻和跟它最近的k個點連起來，CHAMELEON算法的第1階段就是這麼幹的。再構造一個對角矩陣D，Dii為W第i列元素之和。最後構造矩陣L=D-W。可以證明L是個半正定和對稱矩陣。
2. 求L的前K小特征值對應的特征向量（這要用到奇異值分解了）。把K個特征向量放在一起構造一個N×K的矩陣M。
3. 把M的每一行當成一個新的樣本點，對這N個新的樣本點進行K-Means聚類。