譜聚類綜述

聚類

　　在瞭解譜聚類之前，首先需要知道聚類，聚類通俗的講就是將一大堆沒有標簽的數據根據相似度分為很多簇（就是一坨坨的），將相似的聚成一坨，不相似的再聚成其他很多坨。一般的聚類演算法存在的問題是k值的選擇（就是簇的數量事先不知道），相似性的度量（如何判斷兩個樣本點是否相似），如何不陷入局部最優等問題，流行的演算法有k-means等一系列演算法。

譜聚類

　　顧名思義就是一種聚類演算法，這個譜字應該指的就是譜圖的意思，簡單的來講就是將聚類問題轉化為圖的分割問題，將圖中相似的點聚在一起，但是這個圖是從哪裡來的呢？？？這就涉及到譜聚類的步驟了，以下是各種譜聚類演算法的通俗框架。

　　輸入：相似性矩陣S，簇的數量k

　　k值只能靠猜測了。

　　這個相似性矩陣怎麼得到呢？

　　假設有一堆數據x1，x2，，，x_n，s_ij = s（x_i，x_j），至於這個相似性度量函數s就有很多種選取方法了，最簡單的就是歐氏距離了，然後就構造出了一個相似性矩陣S = （s_ij）_{i，j = 1....n}

1. 根據鄰接矩陣S構造出一個有權無向圖
2. 有了圖就可以計算圖的Laplacian L（拉普拉斯矩陣）
3. 再算出L的前k個特征向量 v₁,.....v_k
4. 將特征向量作為列向量構造出特征空間V
5. 再對V的行用k-means聚類出簇C₁,.....C_n

　　輸出：簇

　　演算法可修改之處：

• 比如相似圖的構造就有knn圖，全連接圖，ε-neighborhood圖

• Laplacian矩陣也分為規範Laplacian和非規範Laplacian，其中非規範Laplacian也有兩種。

  規範Laplacian L = D - W，D為節點的度矩陣，W為節點的權重矩陣

  非規範Laplacian

  　　　L_sym = D^-1/2LD^-1/2 = I - D^-1/2WD^-1/2

  　　　L_rw = D^-1L = I - D^-1W

• 特征向量的選擇，v不一定是L的特征向量，選擇出的向量也不一定為前k個

譜聚類的引出

　　看到這裡是不是覺得一切都那麼的自然，但是這個東東為啥能被人想出來呢？？？

　　最根本的原因在於圖的最優分割問題是一個NP難的問題，在得到一個基於樣本相似度的無向加權圖G=（V，E)之後，可以有很多種基於圖論的方法來切割G，使得子圖的內部相似度最大，子圖間的相似度最小，切割的方法也有很多種，比如Ncut，Rcut，Avcut等多種切割方法，一般用來切割k=2的問題效果還不錯，但涉及到多路規範切割(k>2)的時候，優化問題就難以解決了。

　　各種切割方法的解釋詳見下述論文。

譜聚類的優勢

　　只要保證相似性圖的稀疏，譜聚類對於大數據量的樣本效率就會很高。

　　而且譜聚類的求解不涉及到凸優化問題。

譜聚類的缺點

　　缺點很明顯k值只能靠猜測

由於博主是剛開始看論文的小白，所以有什麼不足之處，歡迎大家指正。

參考文獻：

• 蔡曉妍 戴冠中 楊黎斌      譜聚類演算法綜述
• Ulrike von Luxburg          A Tutorial on Spectral Clustering