聚類算法實踐（2）——譜聚類、Chameleon聚類

男人海洋?發表于 2013-08-30 14:34 來源：數據之城

? ? ? 上一篇文章里說到的層次聚類和K-means聚類，可以說是聚類算法里面最基本的兩種方法（wiki的cluster?analysis頁面都把它們排前兩位）。這次要探討的，則是兩個相對“高級”一點的方法：譜聚類和chameleon聚類。

4、譜聚類

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

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

譜聚類基本步驟：

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

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

3、令B=D-A

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

5、根據每個數據點的k維空間坐標，使用K-means或者其它聚類算法在k維空間對數據進行聚類。

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

簡正模式

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

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

??????????←有誤( A和D應該寫反了 )

??????給出整個系統的坐標矢量，容易證明

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

????

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

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

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

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

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

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

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

????????

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

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

???????對PCA比較熟悉的童鞋，會發現這個方法在形式上跟主元分析有類似的地方。其實簡正模分析和PCA是兩個相反的思路，簡正模是根據系統的性質來推斷系統的特征運動模式，而PCA則是根據系統的運動結果來得到特征方向。一個是從原理來進行推斷，一個則是從結果來進行反推。

聚類結果

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

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

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

5、Chameleon聚類

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

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

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

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

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

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

Relative?Inter-Connectivity

cluster?i和j的relative?inter-connectivity表征了他們之間鄰接區域的大小，其中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是用來調節兩個參量的比重的參數。

聚類結果

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

???????對樣品1進行聚類，分別取聚類數目k=5和8。類似于譜聚類，Chameleon算法也可以穩定地對數據進行聚類，不會對k的選擇過分敏感。

???????經過多次的調整參數，我也終于把樣品2的cluster給識別了出來……

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

(責任編輯：中國統計網)

總結

以上是生活随笔為你收集整理的聚类算法实践（2）——谱聚类、Chameleon聚类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。