前言如下：

以下解釋性內(nèi)容來自于CN博客：https://www.cnblogs.com/magle/p/7672957.html，代碼實(shí)踐屬UP原創(chuàng)

聚類算法——MCL

最近在看聚類方面的論文，接觸到了MCL聚類，在網(wǎng)上找了許久，沒什么中文的資料，可能寫的最具體的便是GatsbyNewton寫的?馬爾可夫聚類算法（MCL）?這篇博客了。但是，其中仍有一些不詳細(xì)的地方。而MCL這一方法是在作者在其博士論文中提出的，篇幅太長，難以細(xì)讀，也不適合作為用來學(xué)習(xí)MCL這一算法的文獻(xiàn)。找來找去，終于找到一篇可以看的PDF文檔，但每中不足的是此文檔是英文的。趁此機(jī)會(huì)，結(jié)合上述材料，總結(jié)了一下MCL的基本思想，也為了往個(gè)人博客里添加些實(shí)質(zhì)性的內(nèi)容，便整理了這一文檔。文章中可能會(huì)有不對(duì)的地方，希望大家相互交流 ?????

Background

Different Clustering

Vector Clustering

我們?cè)诿枋鲆粋€(gè)人時(shí)，常常會(huì)使用他所擁有的特點(diǎn)來表示，比如說：張三，男，高個(gè)子，有點(diǎn)壯。那么，這就可以用四維向量來表示，如果再復(fù)雜一些，就是更高維的向量空間了。下圖是在二維空間之中的分布情況，可以較為直觀的看出，以紅色虛線為界，可以分為兩個(gè)類別。

Graph Clustering

和特征聚類不同，圖聚類比較難以觀察，整個(gè)算法以各點(diǎn)之間的距離作為突破口，可以這樣形容：張三，是王五的好朋友，剛認(rèn)識(shí)李四，對(duì)趙六很是反感。那么，對(duì)于該節(jié)點(diǎn)，我們無法直接得出他的特征，但能知道他的活動(dòng)圈。利用圖聚類，可以將同一社交范圍的人聚合到一起。MCL就是屬于圖聚類的一種。

Random Walks

首先看下圖：

從圖中，我們可以看到，不同的簇，應(yīng)當(dāng)具有以下的特點(diǎn)：

• 位于同一簇的點(diǎn)，其內(nèi)部的聯(lián)系應(yīng)當(dāng)緊密，而和外部的聯(lián)系則比較少（惺惺相惜）

也就是說：如果你從一個(gè)點(diǎn)出發(fā)，到達(dá)其中的一個(gè)鄰近點(diǎn)，那么你在簇內(nèi)的可能性遠(yuǎn)大于離開當(dāng)前簇，到達(dá)新簇的可能性——這就是MCL的核心思想。如果在一張圖上進(jìn)行多次的“Random Walks”，那么就有很大可能發(fā)現(xiàn)簇群，達(dá)到聚類的目的。而“Random Walks”的實(shí)現(xiàn)則是通過“Markov Chains”（馬爾柯夫鏈）。

Markov Chains

為了說明?Markov Chain?，我們使用如下的簡單例子：

在此圖中，我們可以分為兩個(gè)子圖：V(1,2,3,4)和V(5,6,7)，其中，V1是一簇，V2是另一簇。在同一簇群中，各點(diǎn)之間完全連接，在不同簇之間，僅有(2,5)一條邊。

• 現(xiàn)在，我們從V1出發(fā)，假設(shè)每條邊都一樣，那么則一步之后我們有1/3的概率到達(dá)V2，1/3的概率到達(dá)V3，1/3的概率到達(dá)V4，同時(shí)，有0的概率到達(dá)V5,V6,V7。

• 對(duì)于V2，則有1/4的概率到達(dá)V1,V3,V4,V5有0的概率到達(dá)V6,V7。

通過計(jì)算每個(gè)點(diǎn)到達(dá)其余點(diǎn)的概率，我們可以得到如下的概率矩陣：

為了計(jì)算簡單，我們使用一個(gè)更簡單的矩陣進(jìn)行接下來的說明：

這表示的是從任意點(diǎn)出發(fā)，經(jīng)過一步之后到達(dá)其它點(diǎn)的概率矩陣，那么，經(jīng)過兩次之后、三次以及最終的概率矩陣為：

根據(jù)上述例子，我們已經(jīng)接觸到了?Markov Chain?，那么現(xiàn)在就給其下一個(gè)定義：

Markov Process——在給定當(dāng)前知識(shí)或信息的情況下，過去（即當(dāng)期以前的歷史狀態(tài)）對(duì)于預(yù)測將來（即當(dāng)期以后的未來狀態(tài)）是無關(guān)的。

Markov Chain——如果有由隨機(jī)變量X1,X2,X3?組成的數(shù)列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態(tài)空間”。而Xn的值則是在時(shí)間nn的狀態(tài)，如果Xn+1對(duì)于過去狀態(tài)的條件概率分布滿足：P(Xn+1=x|X0,X1,X2,?,Xn)=P(Xn+1=x|Xn)，則我們稱其是一條Markov Chain

Weighted Graphs

之前的例子中，圖的邊是沒有權(quán)值的，也就是所有的邊都是一樣的?，F(xiàn)在，為每條邊添加一個(gè)權(quán)重（可以理解為親密程度），那么，就需要重新計(jì)算到達(dá)每個(gè)點(diǎn)的概率了。

假設(shè)有如下的圖：

那么，其概率矩陣怎么計(jì)算？

首先，我們要計(jì)算得到鄰接矩陣，即：

通過鄰接矩陣，我們就可以計(jì)算得到概率矩陣了，具體計(jì)算公式如下：

最后的概率矩陣如下：

之后的計(jì)算相同。

Self Loops

在上述的例子中均未考慮一個(gè)重要的問題，我們先來看一個(gè)例子：

很簡單，就兩個(gè)點(diǎn)，一條邊。那么，它的概率矩陣呢：

仔細(xì)觀察可以發(fā)現(xiàn)，這個(gè)概率矩陣不管進(jìn)行幾次計(jì)算，都不會(huì)收斂，而且，對(duì)于P11和P22而言，僅在奇數(shù)步后到達(dá)，在偶數(shù)步時(shí)，永遠(yuǎn)不可達(dá)。因此，無法進(jìn)行隨機(jī)游走（本來它就沒有隨機(jī)項(xiàng)供人選擇）

為了解決這個(gè)問題，我們可以為其添加自環(huán)來消除奇偶冪次帶來的影響：

MCL

Markov Chain Cluster Structure

利用?Random Walks?可以求出最終的概率矩陣，但是，在求的過程中，也丟失了大量的信息。

還是這張圖，它的概率矩陣和最終的概率矩陣如下：

從最終的矩陣可以看出，其最終概率和起始點(diǎn)的位置無關(guān)！對(duì)于聚類，這并不是一個(gè)好消息，因?yàn)槲覀兿胍玫降氖且粋€(gè)有明顯區(qū)分度的矩陣來表示不同的類別。因此，我們需要對(duì)其進(jìn)行一定的修改，這也是MCL主要要解決的問題。

Inflation

如果說，前面的內(nèi)容在介紹?Markov Chain?如何進(jìn)行?Expansion?的話，那么，現(xiàn)在就添加一個(gè)新的過程：?Inflation?。這個(gè)過程就是為了解決?Expansion所導(dǎo)致的概率趨同問題的。

簡單的說，Inflation?就是將概率矩陣中的每個(gè)值進(jìn)行了一次冪次擴(kuò)大，這樣就能使得強(qiáng)化緊密的點(diǎn)，弱化松散的點(diǎn)。（強(qiáng)者恒強(qiáng)，弱者恒弱）

假設(shè)有矩陣Mk×l，和一個(gè)給定的非負(fù)實(shí)數(shù)r，經(jīng)過?Inflation?強(qiáng)化后的矩陣為ΓrM，那么它的強(qiáng)化公式如下：

為了更直觀的說明，我們來看下面的一個(gè)例子：

在?Inflation?之前，向量AA?就是一個(gè)正常的概率向量。為了令其具有更明顯的區(qū)分度，對(duì)其進(jìn)行?Inflation?強(qiáng)化。

假設(shè)r的取值為2，A2如下：

對(duì)該向量進(jìn)行標(biāo)準(zhǔn)化，保證∑i=1nAi=1。

可以看出，進(jìn)過一次變換后，區(qū)分度進(jìn)一步的增加，這就為之后的聚類提供了保證。在這里要注明的是Inflation?的參數(shù)r會(huì)影響聚簇的粒度，這個(gè)在之后會(huì)有說明。

MCL Algorithm

在MCL中，?Expansion?和?Inflation?將不斷的交替進(jìn)行，Expansion?使得不同的區(qū)域之間的聯(lián)系加強(qiáng)，而?Inflation?則不斷的分化各點(diǎn)之間的聯(lián)系。經(jīng)過多次迭代，將漸漸出現(xiàn)聚集現(xiàn)象，以此便達(dá)到了聚類的效果。

MCL的算法流程具體如下：

1. 輸入：一個(gè)非全連通圖，Expansion?時(shí)的參數(shù)ee和?Inflation?的參數(shù)rr。

e=2,r=2

2.建立鄰接矩陣

? 3.添加自環(huán)

4.標(biāo)準(zhǔn)化概率矩陣

5.Expansion操作，每次對(duì)矩陣進(jìn)行e次冪方

6.Inflation操作，每次對(duì)矩陣內(nèi)元素進(jìn)行r次冪方，再進(jìn)行標(biāo)準(zhǔn)化

7.重復(fù)步驟5和6，直到達(dá)到穩(wěn)定

8.將結(jié)果矩陣轉(zhuǎn)化為聚簇

MCL Algorithm Convergence

在作者的論文中，并沒有證明MCL算法的收斂性。但是，在實(shí)驗(yàn)過程中，總是能夠達(dá)到最終的收斂狀態(tài)。下圖是一個(gè)達(dá)到收斂的例子：

為了方便區(qū)分不同聚簇，我們將圖上的點(diǎn)分為兩類：Attractor?和?Vertex?。Attractor?代表了那些有著主導(dǎo)地位的點(diǎn)，這些點(diǎn)吸引著其它的點(diǎn)，將它們牢牢的聚集在周圍；Vertex?則表示那些被吸引的點(diǎn)，它們沒有主導(dǎo)地位，被?Attractor?所吸引著。其中，Attractor?所在的行必須至少有一個(gè)正值，聚集著它所在行中所有正值的點(diǎn)?？梢钥闯?，在這個(gè)例子中，總共有三個(gè)聚簇：{1，6，7，10}，{2，3，5}，{4，8，9，11，12}。

當(dāng)然，在MCL中也會(huì)存在著重疊的聚簇。如下圖，當(dāng)且僅當(dāng)簇與簇是同構(gòu)的時(shí)才出現(xiàn)一個(gè)點(diǎn)被多個(gè)聚簇所吸引。

Inflation Parameter

在之前有提到過Inflation?參數(shù)會(huì)對(duì)聚簇產(chǎn)生影響。一般的，隨著rr的增大，其粒度將減小。

從上圖中還可以看出，聚簇的多少和ee有著很大的關(guān)系，在大直徑的圖中就更為明顯了。因?yàn)槠h(yuǎn)地區(qū)的點(diǎn)和簇群中心的聯(lián)系越來越少，便很可能出現(xiàn)“挖墻腳”的可能，以及簇群內(nèi)部分化問題。

Analysis of MCL

MCL有著較為優(yōu)良的性能，總的來說，它的優(yōu)缺點(diǎn)如下：

• 隨著圖大小的擴(kuò)張，MCL有著良好的刻度

• 可以在有權(quán)或無權(quán)的圖上運(yùn)行

• 最后的聚類結(jié)果令人滿意

• 可以較好的處理噪聲數(shù)據(jù)

• 不需要人為規(guī)定簇群數(shù)量，而是可以根據(jù)參數(shù)自行確定

• 不能發(fā)現(xiàn)發(fā)生重疊的點(diǎn)

• 不適合在大圖上使用（它的算法復(fù)雜度是O(N3)O(N3)）

附【無權(quán)重的馬爾科夫聚類示例】

圖例：

代碼：

【有權(quán)重的馬爾科夫代碼示例】

注：有屬性值的，經(jīng)過計(jì)算，可以用一個(gè)標(biāo)量表示一個(gè)“點(diǎn)”，例如A點(diǎn)的綜合屬性值為x1，B為X2，那么兩者邊的權(quán)重為exp(-1*abs(x1-x2));當(dāng)然，這僅僅只是一種表示方法。這里我們直接指定權(quán)重值，通過計(jì)算該點(diǎn)占其所在列之和的比例，作為其轉(zhuǎn)移的概率，示例如下：

通過查看cluster_table變量，便可查看各個(gè)點(diǎn)所屬類別：

第一行代表第一類，以此類推，第一列代表第一個(gè)點(diǎn)，和我們從圖中所看的一致，A,B,C,D屬于第一類，E，F(xiàn)，G屬于第二類