這篇日志是這個系列裡算法部分的最後一篇，關注的是幾個相對另類一點的聚類算法：PCCA、SOM和Affinity Propagation。PCCA是設計來專門用于馬爾科夫模型的一種聚類算法；SOM是基于神經網絡模型的自組織聚類；最後的Affinity Propagation則是在07年才在Science發表的一種較新穎的算法。
6、PCCA
PCCA算法的全稱是Perron Cluster Cluster Analysis，名稱裡有兩個cluster是因為這樣簡寫就可以和PCA區分開來（無語……）。PCCA并不是設計來處理傳統的聚類問題的，而是專門用于得到馬爾科夫鍊中的cluster。當然，對于一般的聚類問題，隻要根據系統特點構造出一個機率轉移矩陣，也可以使用PCCA算法。
要解釋馬爾科夫模型中的cluster，讓我們想象有一隻跳蚤在了資料點間跳躍轉移。它下一個時刻跳到特定資料點上的機率，隻跟它目前落在哪個資料點上有關，這顯然是一個經典的馬爾可夫過程。再讓我們假定，跳蚤在點與點之間的躍遷機率跟資料點的“距離”成反比。如果資料點可以分成幾個分界明顯的cluster，跳蚤大多數時間就隻會在某個cluster内部的資料點間轉移，在cluster之間的跳躍則相對罕見。
先解釋一下馬爾科夫模型的一些性質。馬爾科夫模型需要的是一個轉移矩陣A，元素A(i,j)表示系統從狀态i轉移到狀态j的機率。矩陣的每一列元素之和必須為1，這是因為轉移機率總和必須為1。轉移矩陣有一個本征值為1的本征矢量，對應着系統的穩态，亦即系統到達這個狀态後，它在各個狀态的機率分布就不會再發生變化。
為了說明PCCA的原理，我們直接來考慮最為極端的情況，也就是系統由幾個完全分離的cluster所構成。對于最為極端的情況，如果系統隻能在cluster内部轉移，而完全不會在cluster之間轉移，那麼轉移矩陣A就會是分塊矩陣的形式，比如下面的系統就可以分為兩個完全不連通的cluster，如下面的矩陣。
A=0100100000010010
這樣的一個矩陣存在着不止一個本征值為1的本征矢量，因為它的每個分塊都可以看做一個轉移矩陣，都會對應着一個穩态。比如對于上面的矩陣A，下面兩個本征矢的本征值都為1。
如果我們得到的矢量都是這樣的理想形式，那麼聚類就很簡單了，隻要得到本征值為1的全部本征矢，把對應的元素大于0的資料點歸為一類就可以。十分可惜的是，由于這兩個本征矢量是簡并的，它們線性疊加産生的矢量也是矩陣的本征值為1的本征矢量，比如這個矢量：
是以PCCA算法的思路，就是要從計算得到實際本征矢量，反推得到理想矢量，進而實作聚類。
如果将計算得到的k個本征值為1的本征列矢量并排合并，成為一個N*k的矩陣，那麼矩陣的每一行可以看成對應與資料點的一個坐标。對于理想本征矢（對應下圖藍色基矢），資料點都是落在坐标軸上（因為除了所屬的cluster所對應的那個本征值，其餘的次元都是0），比如下圖的紅色和黃色的資料點。但是由于實際得到的本征矢量是理想本征矢的線性疊加，是以基矢就發生了旋轉（對應黑色基矢）。
盡管如此，每個cluster的資料點落在一條直線上的性質并沒有發生改變。現在的問題就變成了如何找到這些直線的方向。PCCA首先找到離原點最遠的資料點，這個點相對于原點的矢量，就對應了一個理想本征矢。然後每一次都找與已知的理想矢量垂直（相對原點），而又離原點最遠的資料點。隻要找k次，就能找到所有的理想矢量。最後看資料點落在哪個方向上，就可以知道它們屬于哪個cluster。實際情況下，矩陣并不會是完全的分塊矩陣，是以除了第一個本征矢，其餘本征矢量對應的本征值不會完全為1，而是接近于1。cluster之間的轉移幾率越小，這個算法的準确性自然越高。
聚類結果
PCCA算法的一個優點就是，它可以根據本征值來直接得到cluster的數目，有多少個接近于1的本征值就應該分多少個cluster。當然這也是一個限制，聚類數目不能随意給定，完全由資料性質決定，如果cluster的分界不明顯，那麼可能聚類就完全無效。
下面是PCCA對樣品1的聚類結果。第一幅圖是由算法自動判定聚類數目，正好為3，聚類十分成功；第二幅圖是人為地要求分為4個cluster，結果算法就基本失效了。
PCCA是除了Chameleon算法外，對樣品2聚類結果最好的一個算法。不過它并不能正确地判斷出cluster的數目，總共劃分出了7個cluster，這裡顯示了前5個。
PCCA可以自動判定cluster數目，而且也能得到非凸型的cluster，還可以适用于機率轉移矩陣的聚類，看上去确實是一個性能比較好的聚類算法。不過，PCCA對資料的性質特征有比較強的預設，當資料性質偏離理想狀況較遠時，算法的穩定性有待考驗。
7、SOM
之是以嘗試SOM聚類，主要是因為這是基于神經網絡的一種算法，而神經網絡本身又是機器學習中的一個重要方法。
所謂SOM指的是Kohonen提出的競争網絡，全稱是self-organizing map。這個算法有着非常多的改進和變種，在網絡的拓撲結構、節點之間的回報方式等方面各有不同。更一般地說，SOM應該是一個降維算法，它可以将高維的資料投影到節點平面上，實作高維資料可視化，然後也可以繼續根據降維之後的資料再進行聚類，就像譜聚類一樣。不過，因為這裡僅僅是個人的算法嘗試，是以我就使用最簡單的方式，直接使用SOM進行聚類。
競争網絡，顧名思義就是網絡節點互相競争。對于每一個輸入的資料點，網絡節點都要進行競争，最後隻有一個節點獲勝。獲勝節點會根據赢得的資料點進行演化，變得與這個資料點更比對。如果資料可以明顯地分為多個cluster，節點變得跟某個cluster内的資料點更為比對，一般而言就會跟其它cluster不太比對，這樣其它節點就會赢得了其它cluster的資料點。如此反複學習，每個節點就會變得隻跟特定的一個cluster比對，這樣就完成了資料點的聚類。
SOM需要輸入資料點的坐标矩陣，對應的，每個網絡節點也有一個坐标，初始時刻随機指派。每次輸入一個資料點，與這個資料距離最近的節點獲勝，獲勝點的坐标向着這個資料點的方向偏移。聰明的看官們肯定發現了，這個簡單化的SOM算法跟K-means算法思路基本一緻，确實一些文章也提到，在節點數目偏少的情況下SOM的結果就類似于K-means。
聚類結果
SOM的聚類結果确實跟K-means比較類似，不過當聚類數目取為4時，經常也能正确的結果，而不會聚成4個cluster，這個跟學習時間以及節點的初始值有關。這應該是因為SOM的學習方式與K-means直接求平均不同。至于對樣品2的聚類，SOM也跟K-means類似，就不貼出來了。
8、Affinity Propagation
Affinity Propagation（簡稱AP）是一個比較新的算法，在07年發表在Science上面，可見肯定是有一些獨到之處的。
個人認為，AP算法的具體實作步驟沒有很直覺的實體意義，大緻上就是一個網絡自動演化的過程，實作起來也并不複雜。感興趣的童鞋可以直接到算法作者的網頁，上面也提供了各個版本的實作程式，可以直接拿來使用。
這裡我就不詳細地叙述算法的實作步驟了，隻是介紹一下這個算法的一些特點。
1）AP隻要求輸入資料點之間相似性矩陣，而且還不需要是對稱陣。從這個角度來說，适用範圍非常大。
2）AP算法的核心是對于每個cluster找到一個代表資料點exemplar，使得cluster内其它資料點到這個點的距離平方和最小。這是AP算法的一個很大的優點，因為它不僅能完成聚類，還可以給出這個類别的代表。很多時候我們聚類也就是為了找出代表而已。
3）相比起有着同樣目标的K-centers算法，AP的收斂速度可謂極快。但是，AP算法的速度相比起K-means之類，速度還是非常慢，據稱是O(N*N*logN)的複雜度……
4）AP算法不能直接知道聚類的數目，它不僅不能判定合适的聚類數目，甚至在聚類完成前，使用者都不知道這次會聚出多少個cluster來，隻能自己慢慢調整參數，多次嘗試……
AP算法的目标函數跟K-means類似，不過中心點不是平均值，而是真實的一個資料點。其實這個算法可以說是K-centers的一個高效實作，但歸根到底得到的也就是K-centers最佳情況下的結果而已，跟K-means也類似，都是大小接近的凸型cluster，是以我就不貼結果了。可以說，當你想得到K-centers的結果時，AP算法是你的最佳選擇，但如果你的目标不在于此，那就不要用這個方法了。