這是我參與8月更文挑戰的第16天，活動詳情檢視：8月更文挑戰

譜聚類簡介

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

譜聚類原理

譜聚類演算法是一個使用起來較為容易但是從原理上不是那麼容易理解的演算法。對於譜聚類演算法我們可以歸納為以下的步驟：\ 輸入：樣本集D=(x1,x2,...,xn)，相似矩陣的生成方式, 降維後的維度k1, 聚類方法，聚類後的維度k2\ 輸出： 簇劃分C(c1,c2,...ck2).　\ 1) 根據輸入的相似矩陣的生成方式構建樣本的相似矩陣S\ 2）根據相似矩陣S構建鄰接矩陣W，構建度矩陣D\ 3）計算出拉普拉斯矩陣L\ 4）構建標準化後的拉普拉斯矩陣D−1/2LD−1/2\ 5）計算D−1/2LD−1/2最小的k1個特徵值所各自對應的特徵向量f\ 6) 將各自對應的特徵向量f組成的矩陣按行標準化，最終組成n×k1維的特徵矩陣F\ 7）對F中的每一行作為一個k1維的樣本，共n個樣本，用輸入的聚類方法進行聚類，聚類維數為k2。\ 8）得到簇劃分C(c1,c2,...ck2).　\ 譜聚類演算法的具體原理，需要一定圖論相關的基礎，就不在此展開了。詳細解釋可以參考斯坦佛大學CS224w課程第五課的內容，課程的課件可以參見【參考連結2】，也可以閱讀【參考連結3】對課件內容進行理解。

譜聚類演算法總結

譜聚類的主要優點

1. 譜聚類只需要資料之間的相似度矩陣，因此對於處理稀疏資料的聚類很有效。這點傳統聚類演算法比如K-Means很難做到
2. 由於使用了降維，因此在處理高維資料聚類時的複雜度比傳統聚類演算法好。

譜聚類的主要缺點

1. 如果最終聚類的維度非常高，則由於降維的幅度不夠，譜聚類的執行速度和最後的聚類效果均不好。
2. 聚類效果依賴於相似矩陣，不同的相似矩陣得到的最終聚類效果可能很不同。

譜聚類在Sklearn中的實現

在sklearn中提供了譜聚類演算法的實現：

sklearn.cluster.SpectralClustering(n_clusters=8, *, eigen_solver=None, n_components=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, eigen_tol=0.0, assign_labels='kmeans', degree=3, coef0=1, kernel_params=None, n_jobs=None, verbose=False)

引數詳解：

'n_clusters' 是投影子空間的維度，即聚類後的簇的數量也是原理中的k\ 'eigen_solver' 是所使用的特徵值分解策略，可選引數有'arpack', 'lobpcg', 'amg'。AMG 需要安裝 pyamg。它可以在非常大的稀疏問題上更快，但也可能導致不穩定性。如果沒有，則也可以使用'arpack'\ 'random_state' 是一個偽隨機數生成器，用於K-means中的特徵向量分解。\ 'Gamma' 表示的 rbf, poly, sigmoid, laplacian and chi2 kernels的核係數\ 這裡僅列舉了一部分使用的引數，完整引數可參考官方文件即【參考連結4】也可以閱讀【參考連結5】對引數的含義和原理進行理解。