如果說(shuō) K-means 和 GMM 這些聚類(lèi)的方法是古代流行的算法的話(huà)，那么這次要講的 Spectral Clustering 就可以算是現代流行的算法了，中文通常稱(chēng)為“譜聚類(lèi)”。由于使用的矩陣的細微差別，譜聚類(lèi)實(shí)際上可以說(shuō)是一“類(lèi)”算法。
Spectral Clustering 和傳統的聚類(lèi)方法（例如 K-means）比起來(lái)有不少優(yōu)點(diǎn)：
和 K-medoids 類(lèi)似，Spectral Clustering 只需要數據之間的相似度矩陣就可以了，而不必像 K-means 那樣要求數據必須是 N 維歐氏空間中的向量。
由于抓住了主要矛盾，忽略了次要的東西，因此比傳統的聚類(lèi)算法更加健壯一些，對于不規則的誤差數據不是那么敏感，而且 performance 也要好一些。許多實(shí)驗都證明了這一點(diǎn)。事實(shí)上，在各種現代聚類(lèi)算法的比較中，K-means 通常都是作為 baseline 而存在的。
計算復雜度比 K-means 要小，特別是在像文本數據或者平凡的圖像數據這樣維度非常高的數據上運行的時(shí)候。
突然冒出這么一個(gè)要求比 K-means 要少，結果比 K-means 要好，算得還比 K-means 快的東西，實(shí)在是讓人不得不懷疑是不是江湖騙子啊。所以，是騾子是馬，先拉出來(lái)溜溜再說(shuō)。不過(guò)，在 K-medoids 那篇文章中曾經(jīng)實(shí)際跑過(guò) K-medoids 算法，最后的結果也就是一個(gè) accuracy ，一個(gè)數字又不能畫(huà)成圖表之類(lèi)的，看起來(lái)實(shí)在是沒(méi)意思，而且 K-means 跑起來(lái)實(shí)在是太慢了，所以這里我還是稍微偷懶一下，直接引用一下一篇論文里的結果吧。
結果來(lái)自論文 Document clustering using locality preserving indexing 這篇論文，這篇論文實(shí)際上是提的另一種聚類(lèi)方法（下次如果有機會(huì )也會(huì )講到），不過(guò)在它的實(shí)驗中也有 K-means 和 Spectral Clustering 這兩組數據，抽取出來(lái)如下所示：
kTDT2Reuters-21578K-meansSCK-meansSC20.9890.9980.8710.92330.9740.9960.7750.81640.9590.9960.7320.793…90.8520.9840.5530.625100.8350.9790.5450.615其中 TDT2 和 Reuters-21578 分別是兩個(gè)被廣泛使用的標準文本數據集，雖然在不同的數據集上得出來(lái)的結果并不能直接拿來(lái)比較，但是在同一數據集上 K-means 和 SC (Spectral Clustering) 的結果對比就一目了然了。實(shí)驗中分別抽取了這兩個(gè)數據集中若干個(gè)類(lèi)別（從 2 類(lèi)到 10 類(lèi)）的數據進(jìn)行聚類(lèi)，得出的 accuracy 分別在上表中列出（我偷懶沒(méi)有全部列出來(lái)）?？梢钥吹?，Spectral Clustering 這里完勝 K-means 。
這么強大的算法，再戴上“譜聚類(lèi)”這么一個(gè)高深莫測的名號，若不是模型無(wú)比復雜、包羅宇宙，就肯定是某鎮山之寶、不傳秘籍吧？其實(shí)不是這樣，Spectral Clustering 不管從模型上還是從實(shí)現上都并不復雜，只需要能求矩陣的特征值和特征向量即可──而這是一個(gè)非?；镜倪\算，任何一個(gè)號稱(chēng)提供線(xiàn)性代數運算支持的庫都理應有這樣的功能。而關(guān)于 Spectral Clustering 的秘籍更是滿(mǎn)街都是，隨便從地攤上找來(lái)一本，翻開(kāi)便可以看到 Spectral Clustering 算法的全貌：
根據數據構造一個(gè) Graph ，Graph 的每一個(gè)節點(diǎn)對應一個(gè)數據點(diǎn)，將相似的點(diǎn)連接起來(lái)，并且邊的權重用于表示數據之間的相似度。把這個(gè) Graph 用鄰接矩陣的形式表示出來(lái)，記為
把
求出
把這
就是這么幾步，把數據做了一些詭異的變換，然后還在背后偷偷地調用了 K-means 。到此為止，你已經(jīng)可以拿著(zhù)它上街去招搖撞騙了。不過(guò)，如果你還是覺(jué)得不太靠譜的話(huà)，不妨再接著(zhù)往下看，我們再來(lái)聊一聊 Spectral Clustering 那幾個(gè)“詭異變換”背后的道理何在。
其實(shí)，如果你熟悉 Dimensional Reduction （降維）的話(huà)，大概已經(jīng)看出來(lái)了，Spectral Clustering 其實(shí)就是通過(guò) Laplacian Eigenmap 的降維方式降維之后再做 K-means 的一個(gè)過(guò)程──聽(tīng)起來(lái)土多了。不過(guò)，為什么要剛好降到
在 Image Processing （我好像之前有聽(tīng)說(shuō)我對這個(gè)領(lǐng)域深?lèi)和唇^？）里有一個(gè)問(wèn)題就是對圖像進(jìn)行Segmentation （區域分割），也就是讓相似的像素組成一個(gè)區域，比如，我們一般希望一張照片里面的人（前景）和背景被分割到不同的區域中。在 Image Processing 領(lǐng)域里已經(jīng)有許多自動(dòng)或半自動(dòng)的算法來(lái)解決這個(gè)問(wèn)題，并且有不少方法和 Clustering 有密切聯(lián)系。比如我們在談 Vector Quantization 的時(shí)候就曾經(jīng)用 K-means 來(lái)把顏色相似的像素聚類(lèi)到一起，不過(guò)那還不是真正的 Segmentation ，因為如果僅僅是考慮顏色相似的話(huà)，圖片上位置離得很遠的像素也有可能被聚到同一類(lèi)中，我們通常并不會(huì )把這樣一些“游離”的像素構成的東西稱(chēng)為一個(gè)“區域”，但這個(gè)問(wèn)題其實(shí)也很好解決：只要在聚類(lèi)用的 feature 中加入位置信息（例如，原來(lái)是使用 R、G、B 三個(gè)值來(lái)表示一個(gè)像素，現在加入 x、y 兩個(gè)新的值）即可。
另一方面，還有一個(gè)經(jīng)常被研究的問(wèn)題就是 Graph Cut ，簡(jiǎn)單地說(shuō)就是把一個(gè) Graph 的一些邊切斷，讓他被打散成一些獨立聯(lián)通的 sub-Graph ，而這些被切斷的邊的權值的總和就被稱(chēng)為 Cut 值。如果用一張圖片中的所有像素來(lái)組成一個(gè) Graph ，并把（比如，顏色和位置上）相似的節點(diǎn)連接起來(lái)，邊上的權值表示相似程度，那么把圖片分割為幾個(gè)區域的問(wèn)題實(shí)際上等價(jià)于把 Graph 分割為幾個(gè) sub-Graph 的問(wèn)題，并且我們可以要求分割所得的 Cut 值最小，亦即：那些被切斷的邊的權值之和最小，直觀(guān)上我們可以知道，權重比較大的邊沒(méi)有被切斷，表示比較相似的點(diǎn)被保留在了同一個(gè) sub-Graph 中，而彼此之間聯(lián)系不大的點(diǎn)則被分割開(kāi)來(lái)。我們可以認為這樣一種分割方式是比較好的。
實(shí)際上，拋開(kāi)圖像分割的問(wèn)題不談，在 Graph Cut 相關(guān)的一系列問(wèn)題中，Minimum cut （最小割）本身就是一個(gè)被廣泛研究的問(wèn)題，并且有成熟的算法來(lái)求解。只是單純的最小割在這里通常并不是特別適用，很多時(shí)候只是簡(jiǎn)單地把和其他像素聯(lián)系最弱的那一個(gè)像素給分割出去了，相反，我們通常更希望分割出來(lái)的區域（的大?。┮鄬鶆蛞恍?，而不是一些很大的區塊和一些幾乎是孤立的點(diǎn)。為此，又有許多替代的算法提出來(lái)，如 Ratio Cut 、Normalized Cut 等。
不過(guò)，在繼續討論之前，我們還是先來(lái)定義一下符號，因為僅憑文字還是很難表述清楚。將 Graph 表示為鄰接矩陣的形式，記為
先考慮最簡(jiǎn)單的情況，如果把一個(gè) Graph 分割為兩個(gè)部分的話(huà)，那么 Minimum cut 就是要最小化
以及 NormalizedCut ：
其中
搬出 RatioCut 和 NormalizedCut 是因為它們和這里的 Spectral Clustering 實(shí)際上有非常緊密的聯(lián)系?？纯?RatioCut ，式子雖然簡(jiǎn)單，但是要最小化它卻是一個(gè) NP 難問(wèn)題，不方便求解，為了找到解決辦法，讓我們先來(lái)做做變形。
令
再回憶一下我們最開(kāi)始定義的矩陣
Usually, every author just calls “his” matrix the graph Laplacian.
其實(shí)也可以理解，就好象現在所有的廠(chǎng)家都說(shuō)自己的技術(shù)是“云計算”一樣。這個(gè)
這個(gè)是對任意向量
另外，如果令
問(wèn)題轉化到這個(gè)樣子就好求了，因為有一個(gè)叫做 Rayleigh quotient 的東西：
他的最大值和最小值分別等于矩陣
到這一步，我們看起來(lái)好像是很容易地解決了前面那個(gè) NP 難問(wèn)題，實(shí)際上是我們耍了一個(gè)把戲：之前的問(wèn)題之所以 NP 難是因為向量
到此為止，已經(jīng)有 Spectral Clustering 的影子了：求特征值，再對特征向量進(jìn)行 K-means 聚類(lèi)。實(shí)際上，從兩類(lèi)的問(wèn)題推廣到 k 類(lèi)的問(wèn)題（數學(xué)推導我就不再詳細寫(xiě)了），我們就得到了和之前的 Spectral Clustering 一模一樣的步驟：求特征值并取前 k 個(gè)最小的，將對應的特征向量排列起來(lái)，再按行進(jìn)行 K-means 聚類(lèi)。分毫不差！
用類(lèi)似的辦法，NormalizedCut 也可以等價(jià)到 Spectral Clustering 不過(guò)這次我就不再講那么多了，感興趣的話(huà)（還包括其他一些形式的 Graph Laplacian 以及 Spectral Clustering 和 Random walk 的關(guān)系），可以去看這篇 Tutorial ：A Tutorial on Spectral Clustering 。
為了緩和一下氣氛，我決定貼一下 Spectral Clustering 的一個(gè)簡(jiǎn)單的 Matlab 實(shí)現：
最后，我們再來(lái)看一下本文一開(kāi)始說(shuō)的 Spectral Clustering 的幾個(gè)優(yōu)點(diǎn)：
只需要數據的相似度矩陣就可以了。這個(gè)是顯然的，因為 Spectral Clustering 所需要的所有信息都包含在
抓住了主要矛盾，忽略了次要的東西，Performance 比傳統的 K-means 要好。實(shí)際上 Spectral Clustering 是在用特征向量的元素來(lái)表示原來(lái)的數據，并在這種“更好的表示形式”上進(jìn)行 K-means 。實(shí)際上這種“更好的表示形式”是用 Laplacian Eigenmap 進(jìn)行降維的后的結果，如果有機會(huì )，下次談 Dimensionality Reduction 的時(shí)候會(huì )詳細講到。而降維的目的正是“抓住主要矛盾，忽略次要的東西”。
計算復雜度比 K-means 要小。這個(gè)在高維數據上表現尤為明顯。例如文本數據，通常排列起來(lái)是維度非常高（比如，幾千或者幾萬(wàn)）的稀疏矩陣，對稀疏矩陣求特征值和特征向量有很高效的辦法，得到的結果是一些 k 維的向量（通常 k 不會(huì )很大），在這些低維的數據上做 K-means 運算量非常小。但是對于原始數據直接做 K-means 的話(huà)，雖然最初的數據是稀疏矩陣，但是 K-means 中有一個(gè)求 Centroid 的運算，就是求一個(gè)平均值：許多稀疏的向量的平均值求出來(lái)并不一定還是稀疏向量，事實(shí)上，在文本數據里，很多情況下求出來(lái)的 Centroid 向量是非常稠密，這時(shí)再計算向量之間的距離的時(shí)候，運算量就變得非常大，直接導致普通的 K-means 巨慢無(wú)比，而 Spectral Clustering 等工序更多的算法則迅速得多的結果。
說(shuō)了這么多，好像有些亂，不過(guò)也只能到此打住了。最后再多嘴一句，Spectral Clustering 名字來(lái)源于Spectral theory ，也就是用特征分解來(lái)分析問(wèn)題的理論了。
=================================================================
什么叫Spectral Algorithm?
廣義上來(lái)說(shuō)，任何在演算法中用到SVD/特征值分解的，都叫Spectral Algorithm。 從很老很老的PCA/LDA，到比較近的Spectral Embedding/Clustering，都屬于這類(lèi)。
為什么要用SVD/特征值分解?
其實(shí)并不是為用而用，而是不得不用。 目前在研究領(lǐng)域碰到的很多基礎問(wèn)題都是NP-hard的，找一個(gè)比較好的近似演算法要費很大的精力；就算找到多項式的近似方法，也會(huì )出現實(shí)際使用上仍然太慢/解陷入局部極小等問(wèn)題。
比如說(shuō)用K-means聚類(lèi)，建模本身已經(jīng)夠簡(jiǎn)單了，但它是NP-hard的，用傳統的EM迭代作近似解會(huì )陷入局部極小。
反之，SVD理論上只有唯一解，演算法速度相對又快，并且有大量理論結果及周邊性質(zhì)支持，可以算是一個(gè)很理想地能將NP-hard問(wèn)題“靠”上去的模型；它的另一個(gè)好處是，作為帶約束二次規劃的一種特殊情況，它對運算式為二次的目標函數的“相容性”比較好，“靠”所要求的數學(xué)技巧不高，任何人，任何方向都能拿來(lái)試試。
Spectral Algorithm的幾個(gè)方向:
傳統的如PCA/LDA用來(lái)做線(xiàn)性降維，2000年左右的一些Spectral Embedding及Spectral Clustering，還有周邊的一些，如Low-rank approximation等等。
Spectral Clustering，中文通常稱(chēng)為“譜聚類(lèi)”。由于使用的矩陣的細微差別，譜聚類(lèi)實(shí)際上可以說(shuō)是一“類(lèi)”算法。
Spectral Clustering 和傳統的聚類(lèi)方法（例如 K-means）比起來(lái)有不少優(yōu)點(diǎn)：
1）和 K-medoids 類(lèi)似，Spectral Clustering 只需要數據之間的相似度矩陣就可以了，而不必像 K-means 那樣要求數據必須是 N 維歐氏空間中的向量。
2）由于抓住了主要矛盾，忽略了次要的東西，因此比傳統的聚類(lèi)算法更加健壯一些，對于不規則的誤差數據不是那么敏感，而且 performance 也要好一些。許多實(shí)驗都證明了這一點(diǎn)。事實(shí)上，在各種現代聚類(lèi)算法的比較中，K-means 通常都是作為 baseline 而存在的。
3）計算復雜度比 K-means 要小，特別是在像文本數據或者平凡的圖像數據這樣維度非常高的數據上運行的時(shí)候。
Spectral Clustering 算法的全貌：
1）根據數據構造一個(gè) Graph ，Graph 的每一個(gè)節點(diǎn)對應一個(gè)數據點(diǎn)，將相似的點(diǎn)連接起來(lái)，并且邊的權重用于表示數據之間的相似度。把這個(gè) Graph 用鄰接矩陣的形式表示出來(lái)，記為 W 。
2)把每一列元素加起來(lái)得到N 個(gè)數，把它們放在對角線(xiàn)上（其他地方都是零），組成一個(gè)N*N的矩陣，記為D 。并令L = D - W 。
3)求出L的前k個(gè)特征值（在本文中，除非特殊說(shuō)明，否則“前k個(gè)”指按照特征值的大小從小到大的順序）以及對應的特征向量。
4)把這k個(gè)特征（列）向量排列在一起組成一個(gè)N*k的矩陣，將其中每一行看作k維空間中的一個(gè)向量，并使用 K-means 算法進(jìn)行聚類(lèi)。聚類(lèi)的結果中每一行所屬的類(lèi)別就是原來(lái) Graph 中的節點(diǎn)亦即最初的N個(gè)數據點(diǎn)分別所屬的類(lèi)別。
下面是Spectral Clustering 的一個(gè)簡(jiǎn)單的 Matlab 實(shí)現：
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
最后，我們再來(lái)看一下本文一開(kāi)始說(shuō)的 Spectral Clustering 的幾個(gè)優(yōu)點(diǎn)：
1）只需要數據的相似度矩陣就可以了。這個(gè)是顯然的，因為 Spectral Clustering 所需要的所有信息都包含在W中。不過(guò)一般W并不總是等于最初的相似度矩陣——回憶一下， 是我們構造出來(lái)的 Graph 的鄰接矩陣表示，通常我們在構造 Graph 的時(shí)候為了方便進(jìn)行聚類(lèi)，更加強到“局部”的連通性，亦即主要考慮把相似的點(diǎn)連接在一起，比如，我們設置一個(gè)閾值，如果兩個(gè)點(diǎn)的相似度小于這個(gè)閾值，就把他們看作是不連接的。另一種構造 Graph 的方法是將 n 個(gè)與節點(diǎn)最相似的點(diǎn)與其連接起來(lái)。
2)抓住了主要矛盾，忽略了次要的東西，Performance 比傳統的 K-means 要好。實(shí)際上 Spectral Clustering 是在用特征向量的元素來(lái)表示原來(lái)的數據，并在這種“更好的表示形式”上進(jìn)行 K-means 。
3)計算復雜度比 K-means 要小。這個(gè)在高維數據上表現尤為明顯。例如文本數據，通常排列起來(lái)是維度非常高（比如，幾千或者幾萬(wàn)）的稀疏矩陣，對稀疏矩陣求特征值和特征向量有很高效的辦法，得到的結果是一些 k 維的向量（通常 k 不會(huì )很大），在這些低維的數據上做 K-means 運算量非常小。但是對于原始數據直接做 K-means 的話(huà)，雖然最初的數據是稀疏矩陣，但是 K-means 中有一個(gè)求 Centroid 的運算，就是求一個(gè)平均值：許多稀疏的向量的平均值求出來(lái)并不一定還是稀疏向量，事實(shí)上，在文本數據里，很多情況下求出來(lái)的 Centroid 向量是非常稠密，這時(shí)再計算向量之間的距離的時(shí)候，運算量就變得非常大，直接導致普通的 K-means 巨慢無(wú)比，而 Spectral Clustering 等工序更多的算法則迅速得多的結果。
作者：洞庭散人
出處：http://phinecos.cnblogs.com/
為什么先做降維再做K-means，效果會(huì )更好呢？
另外，有趣的是K-means可以用PCA來(lái)做近似解。 K-means是說(shuō)找到K個(gè)點(diǎn)，使得所有點(diǎn)到這K個(gè)點(diǎn)的距離平方和最??；
而SVD是說(shuō)找到一個(gè)子空間，使得所有點(diǎn)到這個(gè)子空間的距離平方和最小。 于是這兩者就建立了聯(lián)系，K-means便relax到SVD上去了。
Spectral Clustering/Embedding:
Spectral Clustering可算是Spectral Algorithm的重頭戲。
所謂Clustering，就是說(shuō)聚類(lèi)，把一堆東西（合理地）分成兩份或者K份。 從數學(xué)上來(lái)說(shuō)，聚類(lèi)的問(wèn)題就相當于Graph Partition的問(wèn)題，即給定一個(gè)圖G = (V, E)，如何把它的頂點(diǎn)集劃分為不相交的子集，使得這種劃分最好。 其難點(diǎn)主要有兩個(gè)：
1.這個(gè)“合理”其實(shí)相當難達到，隨便設一個(gè)目標函數可能達不到希望的結果。 大家可以看了看[1] Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral，這里詳細地討論了一下準則的選擇問(wèn)題。
2.即使我們定義了一個(gè)相當好的聚類(lèi)準則，如何優(yōu)化它又是一個(gè)問(wèn)題。
對于1，在Spectral Clustering這一塊，各家有各家的想法。 主要有以下幾種：
a)大名鼎鼎的Normalized Cut[2]，還有一些變種如Ratio Cut/Minmax cut.
b)和代數圖論緊密相聯(lián)的Minimum conductance[1].
c)沒(méi)有準則，但有證明的演算法[3]
d)不基于圖，而是reformulate原來(lái)的聚類(lèi)方法，使之變成SVD能解的問(wèn)題[4]。
2則完全被1的選取所決定。
Normalized Cut:
在圖上，定義什么樣的聚類(lèi)最好，最簡(jiǎn)單的方法是圈定K個(gè)不相交頂點(diǎn)集之后，希望頂點(diǎn)集之間的邊，其權值的和最小。 (邊上的權值代表的是兩頭的頂點(diǎn)鄰近的程度，或者說(shuō)相似度）這就是所謂MinCut（最小割）問(wèn)題。 二類(lèi)分類(lèi)的最小割不是NP-hard的，但是這不能讓人感到開(kāi)心，因為MinCut這個(gè)準則對于聚類(lèi)不好。
具體來(lái)說(shuō)，Mincut完全可能將離大部隊過(guò)遠的單個(gè)頂點(diǎn)與其他頂點(diǎn)分開(kāi),形成兩類(lèi)。
事實(shí)上，我們不僅僅要讓割邊的權和最小，而且要讓這K個(gè)頂點(diǎn)集都差不多大，這樣才符合聚類(lèi)給人的直觀(guān)感覺(jué)。
于是在MinCut的基礎上，出現了Normalized Cut.思路很簡(jiǎn)單，將Cut normalize一下，除以表現頂點(diǎn)集大小的某種量度(如vol A =所有A中頂點(diǎn)集的度之和)。
也就是Normalize Cut(A, B) = Cut(A, B) / volA + cut(A, B) / volB
然而這樣一改，NP-hard就來(lái)了。 這幾乎是所有組合優(yōu)化問(wèn)題的惡夢(mèng)。
怎么辦呢？ 把組合優(yōu)化問(wèn)題連續化，即所謂減少約束，進(jìn)行適當的relax。 那么為什么會(huì )和SVD扯上的呢？
很簡(jiǎn)單，聚類(lèi)是東西分成不相交集，也就是有正交的含義在里面；只是分東西必須是0-1式的，這種離散化，就是np-hard的原因。 我們把正交約束保留，但把離散變成連續的，聚類(lèi)就變成了尋找（列）正交陣的優(yōu)化問(wèn)題，那正是SVD的火力所在！
就這樣，通過(guò)這種巧妙的relax，NP-hard問(wèn)題有了近似解。 且不說(shuō)這近似解的質(zhì)量如何，這種方法是相當令人振奮的。 （關(guān)于Normalized Cut近似解的質(zhì)量,似乎沒(méi)有什么文章能夠給出嚴格的證明，只是實(shí)際效果不錯就是了。）
值得一提的是，Normalized Cut還和圖上的Markov chain有緊密的關(guān)系[5]。 Normalized Cut這個(gè)量度，換成Markov chain的語(yǔ)言就是在圖上隨機游走，子集間相互“串門(mén)”的概率大小。 相當有趣。
