4、譜聚類

      一般說到譜聚類,，都是從降維(Dimensionality Reduction)或者是圖分割(Graph Cut)的角度來理解,。但是實際上，從物理學(xué)的簡正模式的角度,，可以更為直觀地理解這個算法的本質(zhì),。

      這里先把基本的算法步驟寫出來，然后再討論算法的原理。

譜聚類基本步驟：

1,、給出N個數(shù)據(jù)點兩兩之間的相似性,。也就是一個N*N的相似性矩陣A，A(i,j)代表i和j兩個數(shù)據(jù)點的相似度,，數(shù)值越大則表示越相似,。注意A(i,j)=A(j,i)，A(i,i)=0,。

2,、計算矩陣D，使它的對角元是A矩陣的對應(yīng)的那一列（或行）的值之和,，其余地方為0,。也就是使得

3、令B=D-A

4,、求B矩陣的前k個本征值和本征矢,，將數(shù)據(jù)點投影到一個k維空間。第i本征矢的第j個值,，就表示第j個數(shù)據(jù)點在k維空間中第i維的投影,。就是說如果把k個特征矢量并成一個N*k的矩陣，則每一行代表一個數(shù)據(jù)點在k維空間的坐標(biāo),。

5,、根據(jù)每個數(shù)據(jù)點的k維空間坐標(biāo)，使用K-means或者其它聚類算法在k維空間對數(shù)據(jù)進(jìn)行聚類,。

      從算法的第4,、5步就可以看出，譜聚類的本質(zhì)實際上就類似于PCA,，先將數(shù)據(jù)點投影到一個更能反映數(shù)據(jù)特征的空間,，然后再用其它辦法進(jìn)行聚類。這也就是一種降維的思想（實際上也可能是升維）,。那么問題的關(guān)鍵就在于,，它把數(shù)據(jù)點投影到什么空間去了？為什么這個空間更能反映數(shù)據(jù)特征,？這個問題可以從圖分割的角度來理解（看這里）,，不過我這里要從簡諧振動的角度來討論這個問題，這也是一個更為直觀的理解,。

簡正模式

      說起簡諧振動,，學(xué)過高中物理的童鞋都不會陌生：兩個小球連上一根彈簧，就是最簡單的簡諧振動模型,。為了簡單起見,，寫成一維的形式,，而且彈簧的平衡距離設(shè)為0，于是,，當(dāng)小球的坐標(biāo)給定時,，彈性勢能就是

      我們把上面那個算法套用在這個例子上試試，兩個小球的“相似度”就看成是它們之間彈簧的彈性系數(shù)k,，k越大,，小球之間的關(guān)系自然就越緊密了。這樣上面要求的矩陣就是

      給出整個系統(tǒng)的坐標(biāo)矢量,，容易證明

      B只有兩個本征矢量,，分別是

       這兩個本征向量就代表了體系的兩個簡正運動模式，向量中的值表示對應(yīng)的小球在這個運動模式中的運動方向,。比如p1之中兩個小球往同一個方向運動,，這其實是系統(tǒng)的整體平動，對應(yīng)的本征值為0,；p2則表示兩個小球往相反方向運動,，這就符合我們想象中這兩個小球的簡諧振動了。

       究竟什么是簡正運動模式,？為什么用上面的方法就能得到系統(tǒng)的簡正運動模式呢？其實所謂的簡正模式,，就類似于傅立葉分析里面,，用來將原函數(shù)展開的那組相互正交的基函數(shù)組。這里所使用的,，就是簡諧振動這樣的一種基組,，將整個系統(tǒng)的復(fù)雜運動表示為這些簡正模式的疊加。

       無論我們有多少個小球,，只要小球之間是以彈簧相連的,，那么根據(jù)它們之間的連接方式，總是可以將系統(tǒng)的勢能表示為

       但是,，我們希望的是將運動方式去耦合,，寫成多個簡正模式之和，也就是

所以需要對原來的B矩陣對角化,，而對角化過程中得到的本征矢量和本征值,，也就是所要求的簡正模式以及它們的頻率的平方值。

      上面說了那么多關(guān)于簡正模的東西,，可是到底為什么要求簡正模呢,？這是因為譜聚類的目的是要找到一個能很好地反映數(shù)據(jù)點特征的空間，然后在新空間中進(jìn)行聚類,。試著想象一下,，如果兩個數(shù)據(jù)之間相似性很大,，那么也就是說它們之間的“彈簧”彈性系數(shù)很大，就跟用一個棒子連起來一樣,，那么自然在運動的時候,，它們就會傾向于往同一個方向運動。類似地,，如果一堆數(shù)據(jù)點之間很相似,，那么它們就會形成一個rigid的整體，就像一個剛體一樣,，剛體內(nèi)部的小球喜歡一起動,。而兩個剛體之間，則會產(chǎn)生簡諧運動,，傾向于往不同的方向運動,。

       用一個簡單的例子來說明這個現(xiàn)象，我們可以想象6個小球,，分成對稱的兩組123和456,，組內(nèi)小球兩兩之間連在一起，兩組之間則在3和4間有一根彈簧相連,。這樣一個結(jié)構(gòu),，很明顯應(yīng)該是分為123和456兩組。如果我們使用譜聚類,，那么相似矩陣和求得的本征矢量如下

這里只列出本征值最小的前4個本征矢量：第一個一樣是整體平動,，沒有什么意義；第二個表示兩組小球之間的相對運動,，兩組小球往不同方向運動,，這是我們想要得到的結(jié)果；第三,、四個表示每組小球內(nèi)部的相對運動,。

       在這個結(jié)構(gòu)里，組內(nèi)部的相對運動相比起組間運動是很弱的,，這可以從它們對應(yīng)的本征值看出來,。根據(jù)能均分定理，能量應(yīng)該在每個簡正模式之間均分,，所以模式的振幅反比于它們的頻率,，也就是跟本征值的開方的倒數(shù)成正比，這里A2:A3:A4~3:1:1,。這其實也就告訴了我們,，對傳統(tǒng)的譜聚類算法可以根據(jù)它的物理意義進(jìn)行改進(jìn)，根據(jù)本征值對本征矢量進(jìn)行加權(quán),，而不是同一對待,。這樣,，不重要的模式即便被考慮進(jìn)來，因為振幅很小,，所以也不會對結(jié)果產(chǎn)生什么影響,。這樣，我們在算法的第4步,，考慮k個本征矢量來進(jìn)行投影時,，就不用擔(dān)心會多取了多余的本征矢了，而且也可以根據(jù)本征值譜的變化來判斷k的合理取值,，就像在層次聚類中那樣,。

       對PCA比較熟悉的童鞋，會發(fā)現(xiàn)這個方法在形式上跟主元分析有類似的地方,。其實簡正模分析和PCA是兩個相反的思路,，簡正模是根據(jù)系統(tǒng)的性質(zhì)來推斷系統(tǒng)的特征運動模式，而PCA則是根據(jù)系統(tǒng)的運動結(jié)果來得到特征方向,。一個是從原理來進(jìn)行推斷,，一個則是從結(jié)果來進(jìn)行反推。

聚類結(jié)果

       使用譜聚類對樣品1進(jìn)行聚類,，可以得到下圖,。兩個結(jié)果分別對應(yīng)聚類數(shù)目k取為3和8的情況，可以看到并不會像K-means那樣把大的cluster分離,，只會把少量異常點分離出去,，總體的聚類結(jié)果十分穩(wěn)定。因為算法最后還是使用了K-means進(jìn)行聚類,，所以我們可以想象譜聚類在投影到新空間的時候,，應(yīng)該是很好地把不同的cluster遠(yuǎn)遠(yuǎn)地分離了開來,。

       可惜,，譜聚類對特殊形狀的cluster的聚類效果依然不盡如人意。不過相比起K-means這樣的算法,，譜聚類已經(jīng)辨認(rèn)出一些形狀信息了（有成環(huán)狀的cluster,，而不是都是球型的）。

       譜聚類聚類的效果比較好,，性能也比較穩(wěn)定,。算法需要的輸入只是相似矩陣，不需要數(shù)據(jù)點的坐標(biāo)矩陣,，適用性也較廣,。一個潛在的問題是，如果數(shù)據(jù)量很大的話,，對大矩陣的對角化可能會導(dǎo)致算法效率低下,。但是如果是稀疏矩陣的情況,，只計算前k個本征矢量和本征值的效率還是很高的。所以譜聚類算法總體而言是一個不錯的選擇,。

5,、Chameleon聚類

      之前介紹的三個算法都沒辦法分辨出樣品2的甜甜圈，而這次介紹的chameleon算法則可以說是專門用來干這活的,。下面是算法的提出者在他們的文獻(xiàn)中給出的一些測試組,，可以看到這個算法就是對各類奇葩形狀都應(yīng)對自如……

       我們不妨來想當(dāng)然地考慮一下，怎樣才能識別出甜甜圈結(jié)構(gòu)的cluster,。簡單起見,，考慮最極端的情況，假設(shè)數(shù)據(jù)的噪聲不是像樣品2那么大,，而是分界很明顯的三個環(huán)帶,。想象我們把一只甲蟲放在了其中一個環(huán)帶上，甲蟲的視野很小,，而且它會隨機地走到它能看到的數(shù)據(jù)點上,。如果環(huán)帶之間的間距足夠大，那么甲蟲就不會走到其它環(huán)帶上,。最后,，甲蟲能走到的區(qū)域就是一個環(huán)形的cluster。

       上面這個問題的關(guān)鍵就在于,，要主動地把甲蟲的視野變小,，也就是根據(jù)近鄰數(shù)據(jù)來進(jìn)行聚類，然后不斷延伸,。這其實也就類似于層次聚類中的single-linkage,，實際上single-linkage也確實可以識別出樣品2。

       但是這樣會帶來新的問題,，比如對于下面的情況,。在fig 4中，如果只看最近鄰的連接,，算法會傾向于合并c,、d而不是a、b,，又或者說,，如果甲蟲的視野足夠大到會合并a和b，那么c和d也就一定會被看作一個cluster,。但事實上,，a、b的鄰接區(qū)域較大,，距離也不遠(yuǎn)（相對于a,、b內(nèi)部）,，所以是應(yīng)該被認(rèn)為是屬于同一個cluster，而c,、d則顯然不應(yīng)該被看作一類,。fig 5則表示另外一種情況，就是過分強調(diào)鄰接區(qū)域的大小,，這樣就會傾向于把a與c進(jìn)行合并,，而不是與b合并。

       Chameleon算法就是努力在這兩種情況之間保持平衡,，既考慮Closeness,，即近鄰節(jié)點的靠近程度，也考慮Inter-Connectivity,，即鄰接區(qū)域的大小,。

       Chameleon本質(zhì)上也是一個從下而上的層次聚類算法，不過它只考慮每個節(jié)點鄰近的K個節(jié)點（K由用戶給定）,，也就是說,，只有最接近節(jié)點的其它K個節(jié)點會被認(rèn)為與節(jié)點存在連接。兩個節(jié)點越“接近”,，連接強度越強,。兩個cluster的“距離”由兩個參量決定：relative inter-connectivity和relative closeness。

Relative Inter-Connectivity

cluster i和j的relative inter-connectivity表征了他們之間鄰接區(qū)域的大小,，其中EC{Ci,Cj}表示跨越i和j的所有連接的強度之和,，EC{Ci}表示將cluster i分割為大小接近的兩部分所需要切斷的連接的強度值和。

Relative Closeness

cluster i和j的relative closeness表征了他們之間近鄰連接的強度,，其中SEC{Ci,Cj}表示跨越i和j的所有連接的強度平均值,，SEC{Ci}表示將cluster i分割為大小接近的兩部分所需要切斷的連接的強度平均值。

最后,，兩個cluster之間的距離為

a是用來調(diào)節(jié)兩個參量的比重的參數(shù),。

聚類結(jié)果

       因為原算法需要使用一些額外的算法來進(jìn)行圖分割，我這里只是使用了一個簡化版本的Chameleon算法,，使用了絕對的inter-connectivity和closeness,，沒有對cluster的大小進(jìn)行normalization（也就是沒有考慮上面兩條式子中的分母）,。

       對樣品1進(jìn)行聚類,，分別取聚類數(shù)目k=5和8。類似于譜聚類,，Chameleon算法也可以穩(wěn)定地對數(shù)據(jù)進(jìn)行聚類,，不會對k的選擇過分敏感。

       經(jīng)過多次的調(diào)整參數(shù),，我也終于把樣品2的cluster給識別了出來……

       從算法的角度來說,，Chameleon可以用于識別形狀特別的cluster,，但是實際上調(diào)整參數(shù)殊為不易（當(dāng)然這也跟我使用簡化版算法有關(guān)），而且關(guān)鍵是層次聚類的效率終歸不高,。所以Chameleon可以在一些特殊的場合使用,，個人認(rèn)為不是一個十分通用的算法。