Spectral Clustering方法的總結

什麼叫Spectral Algorithm?

 廣義上來說，任何在演算法中用到SVD/特征值分解的，都叫Spectral Algorithm。  從很老很老的PCA/LDA，到比較近的Spectral Embedding/Clustering，都屬于這類。

 為什麼要用SVD/特征值分解?

 其實并不是為用而用，而是不得不用。  目前在研究領域碰到的很多基礎問題都是NP-hard的，找一個比較好的近似演算法要費很大的精力；就算找到多項式的近似方法，也會出現實際使用上仍然太慢/解陷入局部極小等問題。

 比如說用K-means聚類，模組化本身已經夠簡單了，但它是NP-hard的，用傳統的EM疊代作近似解會陷入局部極小。

 反之，SVD理論上隻有唯一解，演算法速度相對又快，并且有大量理論結果及周邊性質支援，可以算是一個很理想地能将NP-hard問題“靠”上去的模型；它的另一個好處是，作為帶限制二次規劃的一種特殊情況，它對運算式為二次的目标函數的“相容性”比較好，“靠”所要求的數學技巧不高，任何人，任何方向都能拿來試試。

 Spectral Algorithm的幾個方向:

 傳統的如PCA/LDA用來做線性降維，2000年左右的一些Spectral Embedding及Spectral Clustering，還有周邊的一些，如Low-rank approximation等等。

Spectral Clustering，中文通常稱為“譜聚類”。由于使用的矩陣的細微差别，譜聚類實際上可以說是一“類”算法。

Spectral Clustering 和傳統的聚類方法（例如 K-means）比起來有不少優點：

1）和 K-medoids 類似，Spectral Clustering 隻需要資料之間的相似度矩陣就可以了，而不必像 K-means 那樣要求資料必須是 N 維歐氏空間中的向量。

2）由于抓住了主要沖突，忽略了次要的東西，是以比傳統的聚類算法更加健壯一些，對于不規則的誤差資料不是那麼敏感，而且 performance 也要好一些。許多實驗都證明了這一點。事實上，在各種現代聚類算法的比較中，K-means 通常都是作為 baseline 而存在的。

3）計算複雜度比 K-means 要小，特别是在像文本資料或者平凡的圖像資料這樣次元非常高的資料上運作的時候。

Spectral Clustering 算法的全貌：

1）根據資料構造一個 Graph ，Graph 的每一個節點對應一個資料點，将相似的點連接配接起來，并且邊的權重用于表示資料之間的相似度。把這個 Graph 用鄰接矩陣的形式表示出來，記為 W 。

2)把每一列元素加起來得到N 個數，把它們放在對角線上（其他地方都是零），組成一個N*N的矩陣，記為D 。并令L = D - W 。

3)求出L的前k個特征值（在本文中，除非特殊說明，否則“前k個”指按照特征值的大小從小到大的順序）以及對應的特征向量。

4)把這k個特征（列）向量排列在一起組成一個N*k的矩陣，将其中每一行看作k維空間中的一個向量，并使用 K-means 算法進行聚類。聚類的結果中每一行所屬的類别就是原來 Graph 中的節點亦即最初的N個資料點分别所屬的類别。

下面是Spectral Clustering 的一個簡單的 Matlab 實作：

function idx = spectral_clustering(W, k)

    D = diag(sum(W));

    L = D-W;

    opt = struct('issym', true, 'isreal', true);

    [V dummy] = eigs(L, D, k, 'SM', opt);

    idx = kmeans(V, k);

end

      最後，我們再來看一下本文一開始說的 Spectral Clustering 的幾個優點：

1）隻需要資料的相似度矩陣就可以了。這個是顯然的，因為 Spectral Clustering 所需要的所有資訊都包含在W中。不過一般W并不總是等于最初的相似度矩陣——回憶一下， 是我們構造出來的 Graph 的鄰接矩陣表示，通常我們在構造 Graph 的時候為了友善進行聚類，更加強到“局部”的連通性，亦即主要考慮把相似的點連接配接在一起，比如，我們設定一個門檻值，如果兩個點的相似度小于這個門檻值，就把他們看作是不連接配接的。另一種構造 Graph 的方法是将 n 個與節點最相似的點與其連接配接起來。

2)抓住了主要沖突，忽略了次要的東西，Performance 比傳統的 K-means 要好。實際上 Spectral Clustering 是在用特征向量的元素來表示原來的資料，并在這種“更好的表示形式”上進行 K-means 。

3)計算複雜度比 K-means 要小。這個在高維資料上表現尤為明顯。例如文本資料，通常排列起來是次元非常高（比如，幾千或者幾萬）的稀疏矩陣，對稀疏矩陣求特征值和特征向量有很高效的辦法，得到的結果是一些 k 維的向量（通常 k 不會很大），在這些低維的資料上做 K-means 運算量非常小。但是對于原始資料直接做 K-means 的話，雖然最初的資料是稀疏矩陣，但是 K-means 中有一個求 Centroid 的運算，就是求一個平均值：許多稀疏的向量的平均值求出來并不一定還是稀疏向量，事實上，在文本資料裡，很多情況下求出來的 Centroid 向量是非常稠密，這時再計算向量之間的距離的時候，運算量就變得非常大，直接導緻普通的 K-means 巨慢無比，而 Spectral Clustering 等工序更多的算法則迅速得多的結果。

作者：洞庭散人

出處：http://phinecos.cnblogs.com/

 為什麼先做降維再做K-means，效果會更好呢？

 另外，有趣的是K-means可以用PCA來做近似解。  K-means是說找到K個點，使得所有點到這K個點的距離平方和最小；

 而SVD是說找到一個子空間，使得所有點到這個子空間的距離平方和最小。  于是這兩者就建立了聯系，K-means便relax到SVD上去了。

 Spectral Clustering/Embedding:

 Spectral Clustering可算是Spectral Algorithm的重頭戲。

 所謂Clustering，就是說聚類，把一堆東西（合理地）分成兩份或者K份。  從數學上來說，聚類的問題就相當于Graph Partition的問題，即給定一個圖G = (V, E)，如何把它的頂點集劃分為不相交的子集，使得這種劃分最好。  其難點主要有兩個：

 1.這個“合理”其實相當難達到，随便設一個目标函數可能達不到希望的結果。  大家可以看了看[1] Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral，這裡詳細地讨論了一下準則的選擇問題。

 2.即使我們定義了一個相當好的聚類準則，如何優化它又是一個問題。

 對于1，在Spectral Clustering這一塊，各家有各家的想法。  主要有以下幾種：

 a)大名鼎鼎的Normalized Cut[2]，還有一些變種如Ratio Cut/Minmax cut.

 b)和代數圖論緊密相聯的Minimum conductance[1].

 c)沒有準則，但有證明的演算法[3]

 d)不基于圖，而是reformulate原來的聚類方法，使之變成SVD能解的問題[4]。

 2則完全被1的選取所決定。

 Normalized Cut:

 在圖上，定義什麼樣的聚類最好，最簡單的方法是圈定K個不相交頂點集之後，希望頂點集之間的邊，其權值的和最小。  (邊上的權值代表的是兩頭的頂點鄰近的程度，或者說相似度）這就是所謂MinCut（最小割）問題。  二類分類的最小割不是NP-hard的，但是這不能讓人感到開心，因為MinCut這個準則對于聚類不好。

 具體來說，Mincut完全可能将離大部隊過遠的單個頂點與其他頂點分開,形成兩類。

 事實上，我們不僅僅要讓割邊的權和最小，而且要讓這K個頂點集都差不多大，這樣才符合聚類給人的直覺感覺。

 于是在MinCut的基礎上，出現了Normalized Cut.思路很簡單，将Cut normalize一下，除以表現頂點集大小的某種量度(如vol A =所有A中頂點集的度之和)。

 也就是Normalize Cut(A, B) = Cut(A, B) / volA + cut(A, B) / volB

 然而這樣一改，NP-hard就來了。  這幾乎是所有組合優化問題的惡夢。

 怎麼辦呢？  把組合優化問題連續化，即所謂減少限制，進行适當的relax。  那麼為什麼會和SVD扯上的呢？

 很簡單，聚類是東西分成不相交集，也就是有正交的含義在裡面；隻是分東西必須是0-1式的，這種離散化，就是np-hard的原因。  我們把正交限制保留，但把離散變成連續的，聚類就變成了尋找（列）正交陣的優化問題，那正是SVD的火力所在！

 就這樣，通過這種巧妙的relax，NP-hard問題有了近似解。  且不說這近似解的品質如何，這種方法是相當令人振奮的。  （關于Normalized Cut近似解的品質,似乎沒有什麼文章能夠給出嚴格的證明，隻是實際效果不錯就是了。）

 值得一提的是，Normalized Cut還和圖上的Markov chain有緊密的關系[5]。  Normalized Cut這個量度，換成Markov chain的語言就是在圖上随機遊走，子集間互相“串門”的機率大小。  相當有趣。

Ref http://blog.sina.com.cn/s/blog_4b9b714a0100is5k.html