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