賴健瓊 周金治

1(西南科技大學(xué)信息工程學(xué)院 四川 綿陽(yáng) 621000) 2(特殊環(huán)境機(jī)器人技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室 四川 綿陽(yáng) 621000)

0 引 言

近鄰傳播(Affinity Propagation，AP)聚類(lèi)是Frey等于2007年在Science上發(fā)表的一種基于代表點(diǎn)的聚類(lèi)算法[1-2]。它一般選取N個(gè)數(shù)據(jù)作為輸入，將N個(gè)數(shù)據(jù)點(diǎn)之間的歐氏距離構(gòu)成相似度矩陣S作為算法的工作基礎(chǔ)，該矩陣大小為N×N。按照AP聚類(lèi)的因子圖，N個(gè)對(duì)象對(duì)應(yīng)N×N條邊，算法通過(guò)順著因子圖的邊傳遞N×N個(gè)吸引度值(Responsibility,R)和歸屬度值(Availability, A)來(lái)完成更新迭代。鑒于該算法通過(guò)無(wú)監(jiān)督學(xué)習(xí)完成聚類(lèi)，不需要事先人為設(shè)定代表點(diǎn)或聚類(lèi)數(shù)目，因此，自問(wèn)世以來(lái)，許多領(lǐng)域都在運(yùn)用AP聚類(lèi)算法實(shí)現(xiàn)聚類(lèi)，如推薦系統(tǒng)[3]、文本數(shù)據(jù)挖掘[4]、數(shù)字醫(yī)療[5]和商務(wù)智能[6]等。

AP聚類(lèi)算法不僅在算法上具備簡(jiǎn)單、快速等特點(diǎn)，且在解決大多數(shù)數(shù)據(jù)集聚類(lèi)問(wèn)題上，與傳統(tǒng)聚類(lèi)算法相比能夠獲取更好的聚類(lèi)效果。但是，原始的AP聚類(lèi)算法的復(fù)雜度為O(N2T),其中T表示迭代次數(shù)。隨著人工智能時(shí)代的到來(lái)，各種感知和通信設(shè)備以及存儲(chǔ)設(shè)備的普及，使當(dāng)前數(shù)據(jù)形式發(fā)生翻天覆地的變化，生活中的數(shù)據(jù)規(guī)模都在爆炸式增長(zhǎng)。這使得數(shù)據(jù)量級(jí)別在增大，不僅會(huì)增大現(xiàn)有的AP聚類(lèi)算法時(shí)間復(fù)雜度，還會(huì)占用大量?jī)?nèi)存空間。對(duì)此，文獻(xiàn)[1]提出稀疏AP聚類(lèi)算法，但沒(méi)有給出具體的稀疏化方法。由于AP聚類(lèi)算法是以數(shù)據(jù)對(duì)象之間的相似度作為算法的數(shù)據(jù)基礎(chǔ)，所以如何保證在矩陣稀疏化過(guò)程中留下最重要的相似度信息，使得稀疏AP聚類(lèi)算法不出現(xiàn)嚴(yán)重失真顯得至關(guān)重要。因此，Xiao等[7]提出了基于K最近鄰的快速AP聚類(lèi)算法；Jia等[8]通過(guò)K最近鄰來(lái)構(gòu)建稀疏相似度矩陣來(lái)實(shí)現(xiàn)快速AP聚類(lèi)算法；Shang等[9]通過(guò)因子圖稀疏化來(lái)實(shí)現(xiàn)快速AP聚類(lèi)算法。

上述對(duì)提高AP聚類(lèi)算法性能的主要研究思路大多基于如下思想：在聚類(lèi)過(guò)程中，均認(rèn)為一個(gè)數(shù)據(jù)對(duì)象只和它比較近的代表點(diǎn)的選擇過(guò)程有關(guān)，且起到至關(guān)重要的作用，相反和離它較遠(yuǎn)的代表點(diǎn)的選擇過(guò)程中起到的作用微乎其微。對(duì)于每個(gè)數(shù)據(jù)對(duì)象只留下和它相鄰的相似度，舍棄了離它較遠(yuǎn)的相似度。但是，這一改進(jìn)策略都只考慮局域相似度信息而忽視了全局相似度信息，從而導(dǎo)致了聚類(lèi)結(jié)果中聚類(lèi)中心數(shù)目過(guò)多或難以控制的問(wèn)題。為此，本文提出一種基于稀疏因子圖的DPCA_AP聚類(lèi)算法，即將基于密度峰值聚類(lèi)算法和AP聚類(lèi)算法進(jìn)行融合的方法。首先將N個(gè)數(shù)據(jù)對(duì)象作為輸入，使用基于密度峰值聚類(lèi)算法(Density Peaks Clustering Algorithm，DPCA)的決策圖選擇潛藏代表點(diǎn)完成對(duì)相似矩陣的稀疏化；其次依據(jù)上述稀疏矩陣得到稀疏因子圖；最后通過(guò)在稀疏因子圖上完成R和A值的循環(huán)更新，以獲取最后的聚類(lèi)結(jié)果。

1 相關(guān)理論

1.1 因子圖

因子圖是由Kschischang等[10]于2001年提出的對(duì)函數(shù)進(jìn)行因子分解的一種概率圖模型，主要包括變量節(jié)點(diǎn)和函數(shù)節(jié)點(diǎn)。如圖1所示，f(x1,x2,x3)=f1(x1,x2,x3)f2(x1,x2,x3)，其中：x1、x2、x3為變量節(jié)點(diǎn)；f1和f2為函數(shù)節(jié)點(diǎn)。因子圖的消息是通過(guò)變量節(jié)點(diǎn)和函數(shù)節(jié)點(diǎn)構(gòu)成并進(jìn)行相互傳遞的。

圖1 因子圖

1.2 決策圖

圖2 50個(gè)數(shù)據(jù)點(diǎn)分布圖

圖3是利用基于密度峰值聚類(lèi)算法得到的決策圖，其中點(diǎn)1、2和3為離群點(diǎn)，被選為聚類(lèi)中心的可能性較大。

圖3 決策圖

2 AP聚類(lèi)算法

AP聚類(lèi)算法將N個(gè)數(shù)據(jù)對(duì)象作為輸入，計(jì)算N個(gè)數(shù)據(jù)之間的相似度并將其組成N×N的相似度矩陣S或s(i,k)，即similarity，其中相似度矩陣是利用歐氏距離作為測(cè)量標(biāo)準(zhǔn)，數(shù)據(jù)對(duì)象i和k之間的相似度記作s(i,k)=-‖xi-xk‖2，并且將所有的數(shù)據(jù)點(diǎn)都視為潛藏代表點(diǎn)；N個(gè)數(shù)據(jù)對(duì)象對(duì)應(yīng)因子圖的N×N條邊，通過(guò)因子圖的邊傳遞完成R和A的更新迭代；重復(fù)上述過(guò)程直到達(dá)到最終終止條件，算法結(jié)束，獲得最終的聚類(lèi)結(jié)果。

算法1AP聚類(lèi)算法

輸入：N個(gè)數(shù)據(jù)對(duì)象。

輸出：k個(gè)聚類(lèi)數(shù)目。

1.根據(jù)N個(gè)數(shù)據(jù)對(duì)象計(jì)算它們之間的相似度得到相似度矩陣s(i,k)；

2.初始化吸引度矩陣r(i,k)和歸屬度矩陣a(i,k)；

3.根據(jù)式(1)構(gòu)造AP聚類(lèi)算法的因子圖[4]，其中s(i,.)代表點(diǎn)i與ci的相似度，如圖4所示；

圖4 AP聚類(lèi)算法因子圖

(1)

式中：c=(c1,c2,…,cn);δk(c)是懲罰項(xiàng)，定義為:

4.沿著因子圖的N×N條邊更新r(i,k)和a(i,k)；

(2)

r(i,k)=(1-λ)×r(i,k)+λ×r(i,k)old

(3)

(4)

a(i,k)=(1-λ)×a(i,k)+λ×a(i,k)old

(5)

5.重復(fù)步驟4，直到滿足終止條件，以獲得最終聚類(lèi)結(jié)果。

3 算法設(shè)計(jì)

處理大數(shù)據(jù)集時(shí)，為了提高算法的效率，文獻(xiàn)[1]提出可以通過(guò)對(duì)因子圖稀疏化來(lái)提高算法的運(yùn)行效率，但是，他們并未給出具體的因子圖稀疏化的具體方法。因此，本文通過(guò)減小相似度矩陣的規(guī)模來(lái)解決這個(gè)問(wèn)題。鑒于AP聚類(lèi)算法的相似度矩陣大小與因子圖的規(guī)模關(guān)系緊密，本文選用DPCA算法中的決策圖來(lái)選擇潛藏的代表點(diǎn)，從而減小相似矩陣的大小，與此同時(shí)，因子圖的規(guī)模也會(huì)隨之減小，即對(duì)因子圖進(jìn)行稀疏化，以此來(lái)提高算法效率。

3.1 相似度矩陣稀疏化

針對(duì)N個(gè)數(shù)據(jù)對(duì)象組成的規(guī)模為N×N的相似度矩陣S，其實(shí)際維數(shù)要遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)對(duì)象的數(shù)量，因此，可以在保證不破壞數(shù)據(jù)對(duì)象之間的相似關(guān)系的前提下，對(duì)其進(jìn)行降維處理。在文獻(xiàn)[5]中已經(jīng)對(duì)結(jié)構(gòu)化數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)進(jìn)行特征提取，利用負(fù)歐氏距離度量其特征向量之間的相似度，證明在不同的情境下，均可以將N個(gè)數(shù)據(jù)對(duì)象嵌入到一個(gè)低維特征空間中，并保持?jǐn)?shù)據(jù)對(duì)象之間的相似度關(guān)系不變。在對(duì)于基于代表點(diǎn)的聚類(lèi)問(wèn)題中，最重要的任務(wù)就是如何在N個(gè)數(shù)據(jù)對(duì)象中選取代表點(diǎn)集合E。然而在選擇代表點(diǎn)的過(guò)程中，需要不停地更新迭代R和A的消息值，在此過(guò)程中由于相似度矩陣S的規(guī)模為N×N，算法的時(shí)間復(fù)雜度為O(N2T)。

為了提高算法的速率，首要任務(wù)就是解決如何完成相似度矩陣S稀疏化的問(wèn)題，處理步驟如下：

(1)設(shè)代表點(diǎn)集合為E，E∈S；

(2)在消息更新迭代之前，對(duì)數(shù)據(jù)對(duì)象完成挑選取得潛藏代表點(diǎn)序列E′；

(3)根據(jù)吸引度R和歸屬度A消息的不斷更新迭代，得出最終的代表點(diǎn)序列E*，且|E|=|E*|。

在文獻(xiàn)[5]中已經(jīng)證明，若相似度矩陣S的內(nèi)在維數(shù)不高，潛藏代表點(diǎn)的數(shù)量|E′|相當(dāng)大時(shí)，那么能夠使得從|E′|中獲取的代表點(diǎn)序列E*無(wú)限靠近代表點(diǎn)序列，則可以選用E*替換作為最終的代表點(diǎn)序列。該方法能夠做到兼顧聚類(lèi)效果和運(yùn)行速率。文獻(xiàn)[5]將相似度矩陣作為輸入，采用了一種自下而上選擇代表點(diǎn)實(shí)現(xiàn)相似度矩陣稀疏化的微簇合并算法(Micro Cluster Merging,MCM)，而本文是通過(guò)將所有對(duì)象作為輸入，采用全局搜索潛在代表點(diǎn)的方法，即利用基于密度峰值聚類(lèi)算法的決策圖來(lái)選擇潛在代表點(diǎn)實(shí)現(xiàn)相似矩陣稀疏化。

3.2 算法步驟

(a)相似度矩陣

算法2DPCA_AP聚類(lèi)算法

輸入：N個(gè)數(shù)據(jù)。

輸出：k個(gè)聚類(lèi)數(shù)目。

1.將r(i,k)和a(i,k)進(jìn)行初始化。

5.重復(fù)步驟4直到達(dá)到算法終止條件，輸出并獲得最終聚類(lèi)結(jié)果，即k個(gè)聚類(lèi)數(shù)目。

3.3 復(fù)雜度分析

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

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證DPCA_AP聚類(lèi)算法的有效性，以AP、K-Means和DPCA聚類(lèi)算法的各項(xiàng)性能指標(biāo)作為評(píng)價(jià)的標(biāo)準(zhǔn)，選取輪廓系數(shù)(Silhouette Coefficient)[12-13]、調(diào)整互信息(Adjusted Mutual Information,AMI)[14]和調(diào)整蘭德指數(shù)(Adjusted Rand index,ARI)來(lái)評(píng)價(jià)算法的聚類(lèi)效果[15]，選取真實(shí)計(jì)算時(shí)間作為聚類(lèi)效率的評(píng)價(jià)指標(biāo)。

4.1 評(píng)價(jià)指標(biāo)

(1)輪廓系數(shù)。輪廓系數(shù)是評(píng)價(jià)聚類(lèi)結(jié)構(gòu)的類(lèi)內(nèi)緊密性和類(lèi)間可分性，能夠用來(lái)評(píng)估聚類(lèi)質(zhì)量和最優(yōu)聚類(lèi)數(shù)目。計(jì)算公式為：

(6)

式中：a代表數(shù)據(jù)對(duì)象和類(lèi)內(nèi)余下的點(diǎn)之間距離的均值；b代表數(shù)據(jù)對(duì)象與類(lèi)間其余點(diǎn)之間距離的均值。Sil值越大，聚類(lèi)效果越好。

(2)調(diào)整互信息。調(diào)整互信息是通過(guò)labels_true(真實(shí)類(lèi)標(biāo)號(hào))和predict_labels(聚類(lèi)結(jié)果后的類(lèi)標(biāo)號(hào))之間的互信息來(lái)評(píng)價(jià)labels_true和predict_labels的一致性。計(jì)算公式為：

(7)

式中：U表示真實(shí)類(lèi)標(biāo)號(hào)；V表示聚類(lèi)結(jié)果后的類(lèi)標(biāo)號(hào)；MI表示labels_true和predict_labels之間的互信息；E(MI)表示U、V的相互信息的期望值；H(U)、H(V)分別表示U、V的信息熵。

(3)調(diào)整蘭德指數(shù)(ARI)。調(diào)整蘭德指數(shù)通過(guò)labels_true(真實(shí)類(lèi)標(biāo)號(hào))和predict_labels(聚類(lèi)結(jié)果后的類(lèi)標(biāo)號(hào))之間的一致性來(lái)評(píng)價(jià)被聚在一起的數(shù)據(jù)對(duì)象是否被正確分類(lèi)。計(jì)算公式為：

(8)

4.2 實(shí)驗(yàn)數(shù)據(jù)和運(yùn)行環(huán)境

實(shí)驗(yàn)運(yùn)行環(huán)境為Windows 10 64位操作系統(tǒng)，物理內(nèi)存8 GB，Python 3.7(IDLE)編程實(shí)現(xiàn)算法。算法的最大迭代次數(shù)設(shè)為5 000，稀疏化比率設(shè)為0.2。所有程序在同一臺(tái)筆記本電腦上運(yùn)行。以scikit-learn 的clustering中AP聚類(lèi)算法Python源程序?yàn)榛A(chǔ)，取人工數(shù)據(jù)集和UCI公共數(shù)據(jù)集來(lái)印證算法的有效性。人工隨機(jī)生成數(shù)據(jù)集是以[1,1]、[1，-1]、[-1，-1]三個(gè)點(diǎn)為中心，生成100、500、1 000、1 500和2 000等5個(gè)數(shù)據(jù)集，且標(biāo)準(zhǔn)的聚類(lèi)數(shù)目個(gè)數(shù)為3。UCI公共數(shù)據(jù)，如表1所示，選用Iris、Wine、Yeast、Balance Scale和Heart等真實(shí)數(shù)據(jù)測(cè)試DPCA_AP聚類(lèi)算法的有效性和運(yùn)行速率。

表1 5個(gè)UCI公共數(shù)據(jù)集

4.3 聚類(lèi)效果對(duì)比

(1)人工數(shù)據(jù)集。實(shí)驗(yàn)選取K-Means、DPCA、AP三種聚類(lèi)算法用作評(píng)估標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果如表2所示?？梢园l(fā)現(xiàn)，K-Means、DPCA、AP和DPCA_AP聚類(lèi)算法所取得的輪廓系數(shù)、調(diào)整互信息、調(diào)整蘭德系數(shù)和聚類(lèi)數(shù)目大致相同；DPCA_AP聚類(lèi)算法與AP聚類(lèi)算法的計(jì)算效率在很大程度上得到提高。

表2 K-Means、DPCA、AP和DPCA_AP算法實(shí)驗(yàn)對(duì)比

為了更好地說(shuō)明DPCA_AP聚類(lèi)算法在保證聚類(lèi)效果的同時(shí)在計(jì)算速率方面與AP聚類(lèi)算法相比更勝一籌，圖6給出2種算法在相同數(shù)量級(jí)上的計(jì)算時(shí)間曲線。當(dāng)數(shù)據(jù)量不斷變大時(shí)，2種聚類(lèi)算法的計(jì)算時(shí)間也隨之增加，但是DPCA_AP聚類(lèi)算法增加的速度慢于AP聚類(lèi)算法，特別是在數(shù)據(jù)量較大時(shí)，DPCA_AP聚類(lèi)算法在計(jì)算速率方面更有優(yōu)勢(shì)。

圖6 AP和DPCA_AP聚類(lèi)算法時(shí)間對(duì)比

圖7-圖9給出了4種聚類(lèi)算法的聚類(lèi)效果對(duì)比。

圖7 4種算法輪廓系數(shù)對(duì)比

圖8 4種算法AMI對(duì)比

圖9 4種算法ARI對(duì)比

由圖7可知，K-Means、AP和DPCA_AP聚類(lèi)算法的輪廓系數(shù)相差不超過(guò)0.01，且DPCA_AP聚類(lèi)算法的輪廓系數(shù)明顯優(yōu)于DPCA聚類(lèi)算法。

由圖8可知，當(dāng)數(shù)據(jù)在200～500之間，DPCA_AP聚類(lèi)算法的AMI優(yōu)于其他3種聚類(lèi)算法；當(dāng)數(shù)據(jù)量大于500，DPCA_AP、K-Means和AP這3種聚類(lèi)算法的AMI值相差未超過(guò)0.01，且DPCA_AP聚類(lèi)算法的AMI值明顯優(yōu)于DPCA聚類(lèi)算法。

由圖9可知，當(dāng)數(shù)據(jù)在200～500之間，DPCA_AP聚類(lèi)算法的ARI優(yōu)于K-Means和DPCA聚類(lèi)算法,與AP聚類(lèi)算法ARI差值小于0.01；當(dāng)數(shù)據(jù)量大于500，DPCA_AP、K-Means和AP這3種聚類(lèi)算法的ARI值相差未超過(guò)0.01，且DPCA_AP聚類(lèi)算法的ARI明顯優(yōu)于DPCA聚類(lèi)算法。

圖10和圖11是數(shù)據(jù)點(diǎn)為500時(shí)的聚類(lèi)效果圖，其中●和▲表示聚類(lèi)中心。因此，DPCA_AP聚類(lèi)算法在保證聚類(lèi)效果的前提下提高了運(yùn)行速率。

圖10 AP聚類(lèi)算法500個(gè)數(shù)據(jù)點(diǎn)的聚類(lèi)結(jié)果

圖11 DPCA_AP聚類(lèi)算法500個(gè)數(shù)據(jù)點(diǎn)的聚類(lèi)結(jié)果

表3 4種算法聚類(lèi)效果對(duì)比

(2)公共數(shù)據(jù)集(UCI)。為了更清楚地測(cè)試DPCA_AP聚類(lèi)算法的有效性，本文選取了Iris、Wine、Yeast、Balance Scale和Heart等5個(gè)真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試。由于數(shù)據(jù)集通常擁有不同量綱評(píng)估指標(biāo)，因此數(shù)據(jù)之間具有差異，如果不解決很可能會(huì)影響聚類(lèi)效果。因此，在執(zhí)行聚類(lèi)之前需完成數(shù)據(jù)標(biāo)準(zhǔn)化處理，將所有的指標(biāo)按比例縮放，映射到[-1,1]之間。然后，以標(biāo)準(zhǔn)化后的數(shù)據(jù)作為輸入，分別用AP和DPCA_AP聚類(lèi)算法進(jìn)行測(cè)試，聚類(lèi)結(jié)果如表4所示。

表4 AP和DPCA_AP算法實(shí)驗(yàn)對(duì)比

從表4中可以發(fā)現(xiàn)，在相同的聚類(lèi)數(shù)目上，2種算法最終的聚類(lèi)效果相差不大，但DPCA-AP算法的運(yùn)行速率在一定程度上得到提升，且數(shù)據(jù)量逐漸增大的時(shí)候，效果更加明顯。

表5給出了DPCA_AP聚類(lèi)算法采用Iris數(shù)據(jù)集作為輸入的實(shí)驗(yàn)結(jié)果對(duì)比?？梢钥闯?，DPCA_AP聚類(lèi)算法在各個(gè)方面與其他3種聚類(lèi)算法相比均有優(yōu)勢(shì)，在輪廓系數(shù)方面提高2%，AMI值提高8%，ARI值提高了10%，在計(jì)算速度方面提高了16.5%。

表5 4種算法聚類(lèi)效果對(duì)比

通過(guò)上述評(píng)價(jià)指標(biāo)可以證明，在相同數(shù)量級(jí)上，DPCA_AP聚類(lèi)算法在保證聚類(lèi)效果的同時(shí)其計(jì)算速率勝過(guò)標(biāo)準(zhǔn)AP聚類(lèi)算法，且數(shù)量級(jí)越大，優(yōu)勢(shì)就更加突出。

5 結(jié) 語(yǔ)

本文提出一種基于稀疏因子圖的DPCA_AP聚類(lèi)算法，在聚類(lèi)之前對(duì)相似矩陣完成稀疏化處理，將矩陣的規(guī)模從N2降低到Nx,從而使得利用因子圖的邊進(jìn)行消息傳遞時(shí)，R和A的計(jì)算量減少，使其減少了聚類(lèi)算法的時(shí)間復(fù)雜度，提高了算法的運(yùn)行效率。本文利用輪廓系數(shù)、調(diào)整互信息、調(diào)整蘭德系數(shù)和實(shí)際運(yùn)行時(shí)間來(lái)評(píng)價(jià)算法的聚類(lèi)有效性和運(yùn)行速率，并利用隨機(jī)生成數(shù)據(jù)集和UCI公共數(shù)據(jù)集驗(yàn)證了DPCA_AP聚類(lèi)算法的有效性。