基于消息傳遞的譜聚類算法

王麗娟 丁世飛 賈洪杰

（1.中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，徐州，221116；2.徐州工業(yè)職業(yè)技術(shù)學(xué)院信息與電氣工程學(xué)院，徐州，221400；3.江蘇大學(xué)計(jì)算機(jī)與通信工程學(xué)院，鎮(zhèn)江，212013）

引 言

聚類分析的一般過程是根據(jù)數(shù)據(jù)之間的相似度將其劃分到不同的簇集中,使同一簇中的數(shù)據(jù)相似度較大,不同簇間數(shù)據(jù)的相似度較小。傳統(tǒng)的聚類方法，如k-means算法等,缺乏處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力,當(dāng)樣本空間非凸時,算法容易陷入局部最優(yōu)[1]。

近年來,譜聚類由于其良好的表現(xiàn),易于實(shí)現(xiàn)的特點(diǎn),引起了學(xué)術(shù)界的關(guān)注[2]。譜聚類能在任意形狀的樣本空間上聚類,且收斂于全局最優(yōu),特別適用非凸數(shù)據(jù)集[3]。譜聚類算法將數(shù)據(jù)集中的每個點(diǎn)都作為圖的頂點(diǎn),任意兩點(diǎn)之間的相似性值作為連接兩頂點(diǎn)的邊的權(quán)值,這樣就構(gòu)造了一個無向加權(quán)圖。然后根據(jù)某種圖劃分方法將圖分割為若干不連通的子圖,子圖中包含的點(diǎn)集就是聚類后生成的簇[4]。

傳統(tǒng)的圖劃分方法有很多種,如最小割集法、比例割集法、規(guī)范割集法和最小最大割集法等[5]。通過最大化或最小化圖割方法的目標(biāo)函數(shù)得到最優(yōu)割值,來獲得聚類結(jié)果。但對于各種圖分割方法來說,求目標(biāo)函數(shù)的最優(yōu)解往往是NP-hard的。根據(jù)瑞利熵理論,將原問題的離散最優(yōu)化問題松弛到實(shí)數(shù)域,即可在多項(xiàng)式時間內(nèi)解決[6]。對于圖的劃分,可以認(rèn)為某個點(diǎn)的一部分屬于子集A,另一部分屬于子集B,而不是非此即彼。一般,在聚類過程中充分利用圖的拉普拉斯矩陣的特征值和特征向量所包含頂點(diǎn)的分類信息,就可得到良好的聚類結(jié)果[7]。由于算法是基于矩陣譜分析理論來聚類的,因此稱為譜聚類。目前,譜聚類已廣泛應(yīng)用在計(jì)算機(jī)視覺、數(shù)據(jù)分析、圖像處理、視頻監(jiān)控以及自動控制等領(lǐng)域[8-10]。

譜聚類算法盡管在實(shí)踐中取得了很好的效果,但是作為一種新型的聚類方法,仍處于發(fā)展階段,還有很多問題值得進(jìn)一步深入研究。例如,傳統(tǒng)的譜聚類對初始值敏感,而且無法有效處理多尺度的聚類問題[11]。為了處理多重尺度的數(shù)據(jù)集,Zelnik-Manor等[12]提出了自適應(yīng)的譜聚類。它不再指定統(tǒng)一的參數(shù)σ,而是根據(jù)每個點(diǎn)自身的鄰域信息,為每個點(diǎn)xi計(jì)算一個自適應(yīng)的參數(shù)σi,其中σi為點(diǎn)xi到其第p個近鄰的歐式距離,該相似度度量稱為自適應(yīng)的高斯核函數(shù)。由于考慮了每個點(diǎn)鄰域的數(shù)據(jù)分布,自調(diào)節(jié)的譜聚類能夠有效分離出稀疏背景簇中包含的緊密簇。劉馨月等[13]通過局部密度獲得數(shù)據(jù)中隱含的簇結(jié)構(gòu)特征，再與自調(diào)節(jié)的高斯核函數(shù)結(jié)合，提出了一種基于共享近鄰的自適應(yīng)相似度的譜聚類算法。陶新民等[14]提出了一種在流形結(jié)構(gòu)數(shù)據(jù)點(diǎn)間相似度計(jì)算方法,提高算法的聚類性能。為了解決傳統(tǒng)譜聚類算法對尺度參數(shù)和聚類中心初始化敏感的問題,本文提出一種基于消息傳遞的譜聚類算法(Spectral clustering algorithm based on message passing,MPSC)。

1 譜聚類算法的初始化敏感分析

譜聚類算法是將數(shù)據(jù)聚類問題轉(zhuǎn)化為圖的最優(yōu)分割問題。最小化或最大化圖割方法的目標(biāo)函數(shù),均為NP離散最優(yōu)化問題。幸運(yùn)的是,譜方法可以為該最優(yōu)化問題提供一種多項(xiàng)式時間內(nèi)的寬松解[15]。這里的“寬松”指的是將離散最優(yōu)化問題寬松到實(shí)數(shù)域,然后利用某種啟發(fā)式方法將其重新轉(zhuǎn)換為離散解。圖分割的本質(zhì)可以歸結(jié)為矩陣的跡最小化或最大化問題,而完成該最小化或最大化的任務(wù)需要依靠譜聚類算法。

通常任何譜聚類算法都由3個部分組成：預(yù)處理、譜表示和聚類[16]。先構(gòu)造相似圖來描述數(shù)據(jù)集;然后建立相關(guān)的拉普拉斯矩陣,計(jì)算拉普拉斯矩陣的特征值和特征向量,基于一個或多個向量,把每個數(shù)據(jù)點(diǎn)映射到一個低維的代表點(diǎn);最后,基于新的代表點(diǎn),將數(shù)據(jù)點(diǎn)劃分成兩個或多個類。

在劃分?jǐn)?shù)據(jù)集或圖時,有兩個基本的方法：遞歸2-way劃分法和k-way劃分法[17]。遞歸2-way劃分法是以一個層次的方式遞歸地調(diào)用2-way劃分算法,當(dāng)把圖劃分成兩部分之后,再對子圖應(yīng)用相同的過程,直到聚類數(shù)目滿足要求或不再符合遞歸條件為止;k-way劃分法首先按照某種策略,將拉普拉斯矩陣的含有聚類信息的特征向量挑選出來,然后直接利用這些特征向量對數(shù)據(jù)集進(jìn)行k-way劃分。k-way劃分的一個典型的譜聚類算法是由文獻(xiàn)[18]提出的NJW算法。下面是汪中等[19]就譜聚類算法中初始值敏感進(jìn)行的分析。

命題1設(shè)數(shù)據(jù)集X={x1,x2,…,xn}，以不同順序輸入得到的相似矩陣為W1,W2,對角矩陣為D1,D2,拉普拉斯矩陣為L1,L2,生成矩陣為Y1,Y2,則W1和W2相似,D1和D2相似,L1和L2相似,Y1和Y2相似。

證明：設(shè)數(shù)據(jù)集以x1,x2,…,xn的順序輸入得到矩陣W1，以xn,xn-1,…,x2,x1的順序輸入得到矩陣W2，矩陣W1經(jīng)過若干次初等變換可得到矩陣W2,可證矩陣W1和W2相似。同理推出以任意順序輸入得到的矩陣W2均與W1相似。由于矩陣D1為對角矩陣,其主對角元素為相似矩陣W1的相應(yīng)各行元素之和,故矩陣D1和D2相似。又因,且D1,D2為對角矩陣,由矩陣W1和W2相似、L1和L2相似,其對應(yīng)的特征向量x1經(jīng)過若干次初等變換可以得到特征向量x2，可證生成矩陣Y1和Y2亦相似。故結(jié)論成立。

由命題1可知,以不同的順序輸入數(shù)據(jù)點(diǎn),得到的相似矩陣W和最終的生成矩陣Y都是相似的,所以譜聚類算法對聚類中心的初始化敏感,本質(zhì)上是因?yàn)樵谧詈缶垲愲A段使用了k-means算法。為了解決這個問題,將AP聚類中的“消息傳遞”機(jī)制引入到譜聚類中,用來確定聚類中心,以改善譜聚類算法的性能。

2 AP聚類算法

近鄰傳播(Affinity propagation,AP)聚類是文獻(xiàn)[20]提出的一種新的聚類算法。AP算法不需要事先指定初始聚類中心。實(shí)驗(yàn)表明,AP算法具有很高的效率,例如,對數(shù)千個手寫的郵政編碼的圖片,AP算法只花費(fèi)5 min就可以找出能準(zhǔn)確解釋各種筆跡類型的少量圖片,而k-means算法要達(dá)到同樣的精度需要耗費(fèi)500萬年。

AP算法以數(shù)據(jù)點(diǎn)之間的相似關(guān)系矩陣S為基礎(chǔ),將S的對角線上的數(shù)值S(k,k)作為點(diǎn)k能否成為聚類中心的評判標(biāo)準(zhǔn),這個值稱作偏向參數(shù),用p(k)表示。如若p(k)越小,則點(diǎn)k成為聚類中心的可能性就越小。然后通過在數(shù)據(jù)點(diǎn)之間傳遞消息,經(jīng)過數(shù)次迭代來尋找最優(yōu)的類代表點(diǎn)集合,使網(wǎng)絡(luò)能量函數(shù)達(dá)到最小[21]。即有式中：n表示數(shù)據(jù)的個數(shù)；ci表示點(diǎn)i所在類的聚類中心點(diǎn)；S(i,ci)表示點(diǎn)i與聚類中心點(diǎn)ci之間的相似度。

在AP算法中數(shù)據(jù)點(diǎn)之間相互傳播的信息有兩種：一種信息被稱為“吸引度”(Responsibility),簡寫為R;另一種信息被稱為“歸屬度”(Availability),簡寫為A。

R(i,k)是數(shù)據(jù)點(diǎn)i向其備選代表點(diǎn)k發(fā)出的信息,定義為

它反映了在考慮數(shù)據(jù)點(diǎn)i的其他備選代表點(diǎn)的情況下,數(shù)據(jù)點(diǎn)k點(diǎn)適合作為i點(diǎn)的代表點(diǎn)的累積證據(jù)。

A(i,k)是備選代表點(diǎn)k向數(shù)據(jù)點(diǎn)i發(fā)出的信息,定義為

它反映了在考慮了其他數(shù)據(jù)點(diǎn)是否選擇點(diǎn)k作為自己的代表點(diǎn)的情況下,數(shù)據(jù)點(diǎn)i選擇點(diǎn)k作為其代表點(diǎn)的累積證據(jù)。

R(i,k)與A(i,k)的和越大,則k點(diǎn)作為聚類中心的可能性就越大,并且i點(diǎn)隸屬于以k點(diǎn)為聚類中心的聚類的可能性也越大[22]。這兩種信息中包含了不同的競爭機(jī)制,在任何一個階段根據(jù)這些信息可以判斷出哪些數(shù)據(jù)點(diǎn)是代表點(diǎn),以及每個數(shù)據(jù)點(diǎn)被劃分到哪個數(shù)據(jù)類。

另外,為了平衡前后兩次迭代的吸引度和歸屬度,AP算法引入了阻尼系數(shù)(Damping factor,即damp)來調(diào)整吸引度R(i,k)和歸屬度A(i,k),從而得到本次迭代最終的吸引度和歸屬度

式中：RT-1,AT-1表示第T-1次迭代的吸引度和歸屬度;RT,AT表示第T次迭代的吸引度和歸屬度;阻尼系數(shù)damp的取值范圍是[0.5,l)。

AP算法聚類的過程如圖1所示,從圖中可以看到n個樣本點(diǎn)x1,x2,…,xn,初始時都被當(dāng)作潛在的聚類中心。AP算法在迭代過程中,根據(jù)相似關(guān)系矩陣S(i,i)不斷更新每個點(diǎn)的吸引度和歸屬度值,并且在網(wǎng)絡(luò)節(jié)點(diǎn)之間不斷地傳遞這兩個信息量,直到產(chǎn)生m個高質(zhì)量的聚類中心為止(滿足停止條件)。

圖1 AP算法聚類過程Fig.1 Clustering process of AP algorithm

3 本文算法

譜聚類的關(guān)鍵是選擇一個恰當(dāng)?shù)木嚯x度量方法,將數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)真實(shí)地描述出來。相同類中的數(shù)據(jù)點(diǎn)應(yīng)該具有較高的相似性,并且要保持空間一致性。因此相似矩陣的構(gòu)造非常重要,其優(yōu)劣會在很大程度上影響譜聚類的性能[23]。度量數(shù)據(jù)點(diǎn)相似性的方法常用高斯核函數(shù)，但是在高斯核函數(shù)中,尺度參數(shù)σ通常是固定的,這樣兩個數(shù)據(jù)點(diǎn)之間的相似度只取決于它們的歐氏距離,而對其周圍的點(diǎn)沒有適應(yīng)性[24]。當(dāng)處理復(fù)雜數(shù)據(jù)集時,簡單的基于歐氏距離的相似性無法準(zhǔn)確地反映數(shù)據(jù)的分布情況,會顯著降低譜聚類的性能,導(dǎo)致較差的聚類結(jié)果。

Yang等[25]提出了基于密度敏感的相似性度量方法,該方法可以處理多尺度的聚類問題,還相對對參數(shù)選擇不敏感。實(shí)驗(yàn)證明該算法能有效地描述數(shù)據(jù)的實(shí)際聚類分布。

定義一個密度可調(diào)節(jié)的線段長度

式中：d(xi,xj)為數(shù)據(jù)點(diǎn)xi和xj間的歐式距離,ρ＞1稱為伸縮因子。

數(shù)據(jù)點(diǎn)xi和xj間的密度敏感的距離定義為

密度敏感的相似性度量可表示為

與高斯核函數(shù)相比,該相似性度量不需要引入核函數(shù),可以在距離測度上直接計(jì)算相似度。密度敏感的距離可以度量沿著流形上的最短路徑,使得位于同一高密度區(qū)域內(nèi)的兩點(diǎn)可用許多較短的邊相連,而位于不同高密度區(qū)域內(nèi)的兩點(diǎn)要用穿過低密度區(qū)域的較長邊相連,最終達(dá)到這一目的：使不同高密度區(qū)域的數(shù)據(jù)點(diǎn)間距離放大,同一高密度區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)間距離縮小。因此,這一距離度量是數(shù)據(jù)依賴的,且可以反映數(shù)據(jù)的局部密度特征,即所謂的密度敏感。

在上述相似性度量方法的基礎(chǔ)上,將“消息傳遞”機(jī)制引入到譜聚類中,提出了一種基于消息傳遞的譜聚類算法(Spectral clustering algorithm based on message passing,MPSC),其基本思想是：首先使用基于密度敏感的相似性度量方法計(jì)算相似性，構(gòu)造相似性矩陣和拉普拉斯矩陣;然后選擇拉氏矩陣的前k個最大特征向量,構(gòu)造特征空間并將原始數(shù)據(jù)集中的點(diǎn)映射到Rk空間中;最后在Rk空間中,用AP聚類方法將數(shù)據(jù)點(diǎn)劃分成k個類。MPSC算法的詳細(xì)步驟如下。

輸入：數(shù)據(jù)集X={xi|i=1,…,n},聚類數(shù)目k。

輸出：k個劃分好的類。

Step 1根據(jù)式(8),計(jì)算數(shù)據(jù)點(diǎn)之間的相似性值,建立基于密度的相似性矩陣W∈Rn×n。

Step 2建立圖的度矩陣D∈Rn×n,D是一個對角矩陣：對角線上的元素為稱為頂點(diǎn)i的度,而對角線外的元素值為0。

Step 3根據(jù)相似性矩陣W和度矩陣D,構(gòu)造拉普拉斯矩陣L：L=D-1/2WD-1/2。

Step 4計(jì)算矩陣L的前k個最大特征值所對應(yīng)的特征向量u1,…,uk(重復(fù)特征值取其相互正交的特征向量),然后將這些特征向量縱向排列,形成矩陣U，U=[u1?…?uk]∈Rn×k。

Step 5規(guī)范化矩陣U的每一行,將行向量轉(zhuǎn)變成單位向量,得到矩陣

Step 6將矩陣Y的每一行看作空間Rk中的一個點(diǎn),利用AP聚類方法將這些點(diǎn)劃分成k類。

Step 7如果矩陣Y的第i行被分配到第j類,就將原始的數(shù)據(jù)點(diǎn)xi劃分到第j類。

MPSC算法繼承了AP聚類的優(yōu)點(diǎn),它在初始時將所有的數(shù)據(jù)點(diǎn)都看作候選聚類中心,在不斷的迭代過程中,選擇某個數(shù)據(jù)點(diǎn)作為中心或每個數(shù)據(jù)點(diǎn)通過“消息傳遞”來競爭成為聚類中心,最終獲得若干個優(yōu)化的聚類中心。為了克服傳統(tǒng)劃分算法中隨機(jī)選擇參數(shù)對整個數(shù)據(jù)聚類結(jié)果的影響,引入消息傳遞機(jī)制優(yōu)化傳統(tǒng)譜聚類算法中初始化敏感的問題,得到更穩(wěn)定的聚類結(jié)果。

4 實(shí)驗(yàn)分析

4.1 仿真數(shù)據(jù)集聚類

文獻(xiàn)[26]給出了一些有“挑戰(zhàn)性”的人工數(shù)據(jù)集,例如：Blobs and circle，F(xiàn)our lines,Two moons,Two circles,Two spirals和Three circles。用MPSC算法分別對這些數(shù)據(jù)集進(jìn)行聚類,得到的聚類結(jié)果如圖2所示(伸縮因子ρ=2,偏好參數(shù)p取數(shù)據(jù)集全體樣本相似度的中位數(shù))。從圖2中可以看出,MPSC算法可以有效識別不同尺度的流形數(shù)據(jù)結(jié)構(gòu),得到令人滿意的聚類結(jié)果。這是因?yàn)樵撍惴ú捎妹芏让舾械南嗨菩远攘糠椒?通過拉普拉斯變換,將原始數(shù)據(jù)點(diǎn)映射到譜空間,使得相同類內(nèi)的數(shù)據(jù)點(diǎn)更加緊湊,而不同類間的數(shù)據(jù)點(diǎn)更加分離。在2002年，Ng,Jordan和Weiss提出NJW算法（算法以3位作者名字的首字母縮寫命名），圖3給出了NJW算法（分別取σ=0.1和σ=0.2）在Blobs and circle,Two moons和Two spirals人工數(shù)據(jù)集上的聚類結(jié)果,可見NJW算法對尺度參數(shù)σ的取值比較敏感,當(dāng)數(shù)據(jù)結(jié)構(gòu)復(fù)雜時,無法得到準(zhǔn)確的聚類結(jié)果。相比之下,MPSC算法在聚類過程中可以保持?jǐn)?shù)據(jù)的全局一致性,從而克服了高斯核函數(shù)無法處理多尺度數(shù)據(jù)集的缺點(diǎn)。圖2，3中橫縱坐標(biāo)分別為人工數(shù)據(jù)集的第1列和第2列。

圖2 MPSC算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig.2 Clustering results of MPSC algorithm on artificial data sets

4.2 真實(shí)數(shù)據(jù)集聚類

為了進(jìn)一步驗(yàn)證MPSC算法的有效性,從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中選取了3個真實(shí)的數(shù)據(jù)集,它們的數(shù)據(jù)特征如表1所示。如果將聚類得到的結(jié)果和真實(shí)的劃分情況進(jìn)行比較,對于數(shù)據(jù)集中的每對數(shù)據(jù)點(diǎn),存在著下面4種可能：(1)SS：屬于同一類的兩個數(shù)據(jù)點(diǎn)在聚類時也被分到相同的類中;(2)SD：屬于同一類的兩個數(shù)據(jù)點(diǎn)在聚類時卻被分到不同的類中;(3)DS：不屬于同一類的兩個數(shù)據(jù)點(diǎn)在聚類時卻被分到相同的類中;(4)DD：不屬于同一類的兩個數(shù)據(jù)點(diǎn)在聚類時也被分到不同的類中。

圖3 NJW算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig.3 Clustering results of NJW algorithm on artificial data sets

ARI(Adjusted rand index)指標(biāo)就是根據(jù)數(shù)據(jù)點(diǎn)對的這4種關(guān)系來評價聚類結(jié)果的,它可以定量描述聚類的質(zhì)量,客觀反映聚類算法的優(yōu)劣,是一種常用的聚類評價準(zhǔn)則[27]。

設(shè)滿足SS,SD,DS,DD關(guān)系的數(shù)據(jù)點(diǎn)對的數(shù)目分別是a,b,c,d,則ARI的計(jì)算公式為

表1 真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征Tab.1 Data characteristics of real data sets

式中ARI∈[0,1],如ARI的值越小,也就表明聚類的結(jié)果越差。

在實(shí)驗(yàn)中,以ARI指標(biāo)作為衡量標(biāo)準(zhǔn),分別在Iris,Wine,Zoo數(shù)據(jù)集上,對比了MPSC算法、NJW算法、AP算法和k-means算法的聚類性能。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 4種算法在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.4 Experimental results of four algorithms on real data sets

在圖4中,NJW算法和k-means算法的曲線都有明顯的波動,說明它們對聚類中心的初始化比較敏感。這兩種算法都需要隨機(jī)地確定初始聚類中心,當(dāng)聚類中心的選擇不合適時,就會產(chǎn)生較差的聚類結(jié)果。AP算法和MPSC算法的曲線非常平穩(wěn),沒有出現(xiàn)任何波動,說明AP算法和MPSC算法的性能很穩(wěn)定，但AP算法表現(xiàn)不理想，本文提出的MPSC算法將AP算法中“消息傳遞”機(jī)制引入，以確定聚類中心,有效地解決了傳統(tǒng)譜聚類算法對聚類中心初始化敏感的問題。而且從圖4中也可以看出,MPSC算法的ARI指標(biāo)也要明顯優(yōu)于NJW算法、AP算法和k-means算法,因此MPSC算法可以得到比較理想的聚類結(jié)果。表2給出了MPSC算法、NJW算法、AP算法和k-means算法10次聚類的平均準(zhǔn)確率和ARI指標(biāo)。

表2 4種算法的平均準(zhǔn)確率和ARI指標(biāo)Tab.2 Average accuracy and ARI index of four algorithms

5 結(jié)束語

本文分析了傳統(tǒng)的譜聚類算法初始化敏感的原因,提出了一種基于消息傳遞的譜聚類算法。該算法引入了“消息傳遞”機(jī)制,通過在數(shù)據(jù)點(diǎn)之間不斷傳遞“吸引度”和“歸屬度”信息,可以獲得高質(zhì)量的聚類中心。而且該算法使用了密度敏感的相似性度量方法,這樣在度量數(shù)據(jù)點(diǎn)之間的相似性時,可以更好地描述數(shù)據(jù)的分布情況,保持?jǐn)?shù)據(jù)的全局一致性。為了驗(yàn)證MPSC算法的有效性,在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上分別進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,MPSC算法不僅可以有效識別數(shù)據(jù)全局的和局部的分布特征,而且對聚類中心的初始化不再敏感,其聚類準(zhǔn)確率和穩(wěn)定性都明顯好于傳統(tǒng)的譜聚類算法和k-means算法。

不過MPSC算法的計(jì)算復(fù)雜度較高,在處理大數(shù)據(jù)集時,會花費(fèi)較長的時間,如何降低算法的時間復(fù)雜度,提高聚類的效率,還有待進(jìn)一步研究?，F(xiàn)實(shí)的聚類問題中,除了含有大量無標(biāo)記的數(shù)據(jù),有時也會含有一些標(biāo)記數(shù)據(jù),因此將半監(jiān)督學(xué)習(xí)與MPSC算法相結(jié)合,利用少量的標(biāo)記信息來指導(dǎo)聚類的過程,也是一個有價值的研究方向。另外,MPSC算法也有著廣闊的應(yīng)用前景,可以用來處理圖像分割、語音分離和文字識別等實(shí)際問題。