一種基于稀疏因子圖的大數據近鄰傳播聚類算法

賴健瓊 周金治

1(西南科技大學信息工程學院 四川 綿陽 621000) 2(特殊環境機器人技術四川省重點實驗室 四川 綿陽 621000)

0 引 言

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

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

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

1 相關理論

1.1 因子圖

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

圖1 因子圖

1.2 決策圖

圖2 50個數據點分布圖

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

圖3 決策圖

2 AP聚類算法

AP聚類算法將N個數據對象作為輸入，計算N個數據之間的相似度并將其組成N×N的相似度矩陣S或s(i,k)，即similarity，其中相似度矩陣是利用歐氏距離作為測量標準，數據對象i和k之間的相似度記作s(i,k)=-‖xi-xk‖2，并且將所有的數據點都視為潛藏代表點；N個數據對象對應因子圖的N×N條邊，通過因子圖的邊傳遞完成R和A的更新迭代；重復上述過程直到達到最終終止條件，算法結束，獲得最終的聚類結果。

算法1AP聚類算法

輸入：N個數據對象。

輸出：k個聚類數目。

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

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

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

圖4 AP聚類算法因子圖

(1)

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

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.重復步驟4，直到滿足終止條件，以獲得最終聚類結果。

3 算法設計

處理大數據集時，為了提高算法的效率，文獻[1]提出可以通過對因子圖稀疏化來提高算法的運行效率，但是，他們并未給出具體的因子圖稀疏化的具體方法。因此，本文通過減小相似度矩陣的規模來解決這個問題。鑒于AP聚類算法的相似度矩陣大小與因子圖的規模關系緊密，本文選用DPCA算法中的決策圖來選擇潛藏的代表點，從而減小相似矩陣的大小，與此同時，因子圖的規模也會隨之減小，即對因子圖進行稀疏化，以此來提高算法效率。

3.1 相似度矩陣稀疏化

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

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

(1)設代表點集合為E，E∈S；

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

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

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

3.2 算法步驟

(a)相似度矩陣

算法2DPCA_AP聚類算法

輸入：N個數據。

輸出：k個聚類數目。

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

5.重復步驟4直到達到算法終止條件，輸出并獲得最終聚類結果，即k個聚類數目。

3.3 復雜度分析

4 實 驗

本節通過實驗來驗證DPCA_AP聚類算法的有效性，以AP、K-Means和DPCA聚類算法的各項性能指標作為評價的標準，選取輪廓系數(Silhouette Coefficient)[12-13]、調整互信息(Adjusted Mutual Information,AMI)[14]和調整蘭德指數(Adjusted Rand index,ARI)來評價算法的聚類效果[15]，選取真實計算時間作為聚類效率的評價指標。

4.1 評價指標

(1)輪廓系數。輪廓系數是評價聚類結構的類內緊密性和類間可分性，能夠用來評估聚類質量和最優聚類數目。計算公式為：

(6)

式中：a代表數據對象和類內余下的點之間距離的均值；b代表數據對象與類間其余點之間距離的均值。Sil值越大，聚類效果越好。

(2)調整互信息。調整互信息是通過labels_true(真實類標號)和predict_labels(聚類結果后的類標號)之間的互信息來評價labels_true和predict_labels的一致性。計算公式為：

(7)

式中：U表示真實類標號；V表示聚類結果后的類標號；MI表示labels_true和predict_labels之間的互信息；E(MI)表示U、V的相互信息的期望值；H(U)、H(V)分別表示U、V的信息熵。

(3)調整蘭德指數(ARI)。調整蘭德指數通過labels_true(真實類標號)和predict_labels(聚類結果后的類標號)之間的一致性來評價被聚在一起的數據對象是否被正確分類。計算公式為：

(8)

4.2 實驗數據和運行環境

實驗運行環境為Windows 10 64位操作系統，物理內存8 GB，Python 3.7(IDLE)編程實現算法。算法的最大迭代次數設為5 000，稀疏化比率設為0.2。所有程序在同一臺筆記本電腦上運行。以scikit-learn 的clustering中AP聚類算法Python源程序為基礎，取人工數據集和UCI公共數據集來印證算法的有效性。人工隨機生成數據集是以[1,1]、[1，-1]、[-1，-1]三個點為中心，生成100、500、1 000、1 500和2 000等5個數據集，且標準的聚類數目個數為3。UCI公共數據，如表1所示，選用Iris、Wine、Yeast、Balance Scale和Heart等真實數據測試DPCA_AP聚類算法的有效性和運行速率。

表1 5個UCI公共數據集

4.3 聚類效果對比

(1)人工數據集。實驗選取K-Means、DPCA、AP三種聚類算法用作評估標準，實驗結果如表2所示?？梢园l現，K-Means、DPCA、AP和DPCA_AP聚類算法所取得的輪廓系數、調整互信息、調整蘭德系數和聚類數目大致相同；DPCA_AP聚類算法與AP聚類算法的計算效率在很大程度上得到提高。

表2 K-Means、DPCA、AP和DPCA_AP算法實驗對比

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

圖6 AP和DPCA_AP聚類算法時間對比

圖7-圖9給出了4種聚類算法的聚類效果對比。

圖7 4種算法輪廓系數對比

圖8 4種算法AMI對比

圖9 4種算法ARI對比

由圖7可知，K-Means、AP和DPCA_AP聚類算法的輪廓系數相差不超過0.01，且DPCA_AP聚類算法的輪廓系數明顯優于DPCA聚類算法。

由圖8可知，當數據在200～500之間，DPCA_AP聚類算法的AMI優于其他3種聚類算法；當數據量大于500，DPCA_AP、K-Means和AP這3種聚類算法的AMI值相差未超過0.01，且DPCA_AP聚類算法的AMI值明顯優于DPCA聚類算法。

由圖9可知，當數據在200～500之間，DPCA_AP聚類算法的ARI優于K-Means和DPCA聚類算法,與AP聚類算法ARI差值小于0.01；當數據量大于500，DPCA_AP、K-Means和AP這3種聚類算法的ARI值相差未超過0.01，且DPCA_AP聚類算法的ARI明顯優于DPCA聚類算法。

圖10和圖11是數據點為500時的聚類效果圖，其中●和▲表示聚類中心。因此，DPCA_AP聚類算法在保證聚類效果的前提下提高了運行速率。

圖10 AP聚類算法500個數據點的聚類結果

圖11 DPCA_AP聚類算法500個數據點的聚類結果

表3 4種算法聚類效果對比

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

表4 AP和DPCA_AP算法實驗對比

從表4中可以發現，在相同的聚類數目上，2種算法最終的聚類效果相差不大，但DPCA-AP算法的運行速率在一定程度上得到提升，且數據量逐漸增大的時候，效果更加明顯。

表5給出了DPCA_AP聚類算法采用Iris數據集作為輸入的實驗結果對比?？梢钥闯觯珼PCA_AP聚類算法在各個方面與其他3種聚類算法相比均有優勢，在輪廓系數方面提高2%，AMI值提高8%，ARI值提高了10%，在計算速度方面提高了16.5%。

表5 4種算法聚類效果對比

通過上述評價指標可以證明，在相同數量級上，DPCA_AP聚類算法在保證聚類效果的同時其計算速率勝過標準AP聚類算法，且數量級越大，優勢就更加突出。

5 結 語

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