面向大規模數據的快速多代表點仿射傳播算法*

劉　季，陳秀宏，杭文龍

江南大學 數字媒體學院，江蘇 無錫 214122

面向大規模數據的快速多代表點仿射傳播算法*

劉季+，陳秀宏，杭文龍

江南大學 數字媒體學院，江蘇 無錫 214122

LIU Ji,CHEN Xiuhong,HANG Wenlong.Fast multi-exemplar affinity propagation algorithm for large data sets.Journal of Frontiers of Computer Science and Technology,2016,10(2)：268-276.

針對原始的仿射傳播（affinity propagation，AP）聚類算法難以處理多代表點聚類，以及空間和時間開銷過大等問題，提出了快速多代表點仿射傳播（multi-exemplar affinity propagation using fast reduced set density estimator，FRSMEAP）聚類算法。該算法在聚類初始階段，引入快速壓縮集密度估計算法（fast reduced set density estimator，FRSDE）對大規模數據集進行預處理，得到能夠充分代表樣本屬性的壓縮集；在聚類階段，使用多代表點仿射傳播（multi-exemplar affinity propagation，MEAP）聚類算法，獲得比AP更加明顯的聚類決策邊界，從而提高聚類的精度；最后再利用K-鄰近（K-nearest neighbor，KNN）算法分配剩余點得到最終的數據劃分。在人工數據集和真實數據集上的仿真實驗結果表明，該算法不僅能在大規模數據集上進行聚類，而且具有聚類精度高和運行速度快等優點。

仿射傳播；聚類；大數據；多代表點

1　引言

聚類是將物理或者抽象對象的集合依據對象的相似性分成多個類別的過程，使得同一個類別中的對象之間具有較高的相似度，而不同類別中的對象具有較低的相似度。在機器學習中，聚類是一種很重要的無監督學習方法[1]。

Frey等人在Science上首次提出了仿射傳播（affinity propagation,AP）聚類算法[2]。它引入數據點間的消息傳遞機制，通過數據集中數據點之間的消息傳遞獲得具有更高價值的聚類中心點，提高了聚類的質量。AP算法無需預先設置類別數，而且相比K-means等經典算法具有聚類效果好和錯誤率低等優點[3]，在圖像處理、數據挖掘等領域成為研究熱點。為反映數據的實際分布特性，文獻[4]設計了一種可變相似性度量的計算方法，解決了多重尺度及任意空間形狀的數據聚類處理。文獻[5]先引入元點（meta-point）將標記的數據與未標記的數據形成成對約束條件，再將違背成對約束條件的懲罰項加入目標函數，實現了AP的半監督過程。文獻[6]將AP算法成功應用于增值聚類模型中，實現了向動態數據聚類的擴展。文獻[7]先對圖像進行超像素分割，通過計算這些超像素之間的全模糊連接度計算相似度，用AP算法完成了無監督圖像分割。AP算法在以上多個領域獲得了成功，但是由于AP算法中每一個類用一個代表點表示，使得它在多代表點模型中的應用受到了極大阻礙[8]，于是文獻[8]提出多代表點仿射傳播（multi-exemplar affinity propagation,MEAP）聚類算法，允許一個類用多個代表點進行表示，最后推舉出屬于此類的超級代表點，通過改變消息迭代過程成功地實現了AP在多特征模型中的應用。雖然MEAP算法成功應用在了多代表點模型中，聚類邊界比AP更加精確，但忽略了消息參數的迭代造成的繁重的時間開銷，因此該方法不適用于處理大規模數據集。

本文提出了一種基于大規模數據集的快速多代表點仿射傳播聚類算法（multi-exemplar affinity propagation using fast reduced set density estimator, FRSMEAP），該算法在聚類之前利用基于核心集的中心約束最小包含球的快速壓縮方法（fast reduced set density estimator,FRSDE）對原始大規模數據集進行壓縮，得到可以代表整個數據集的壓縮集，再對該壓縮集使用MEAP算法得到全局聚類中心，最后采用K-鄰近（K-nearest neighbor，KNN）算法得到最終劃分，從而解決了復雜模型大數據集下的聚類問題。

2　經典的仿射傳播聚類算法

AP算法是一種無預設類別數的聚類方法，它將所有的數據點都作為潛在的代表點，以數據之間的相似度矩陣作為輸入，通過吸引度矩陣和歸屬度矩陣之間的迭代計算，不斷更新數據之間的消息，最終選出聚類中心。設給定的數據集為X={x1,x2,…,xN}，數據xi與xk之間的相似度為，吸引度為r(i,k)，歸屬度為a(i,k)，則與X對應的相似度矩陣、吸引度矩陣和歸屬度矩陣分別為S=[s(i,k)]N×N，R=[r(i,k)]N×N和A=[a(i,k)]N×N。AP算法的核心是對R和A中元素（又稱為消息參數）的交替更新。

對于任意數據xi，迭代最后它所在類的代表點為，將具有相同類代表點的數據聚為同一個類。

3　基于大數據集的快速多代表點仿射傳播聚類算法

3.1多代表點的仿射傳播聚類算法

AP算法以每個點作為潛在的代表點，故它難以應用于諸如場景分析和特征識別等多特征模型[9]。MEAP算法對AP算法中的消息傳遞及其迭代過程進行改進，以便能適用于多代表點數據模型。它將每個數據點分配給最合適的代表點，而選出的代表點又被分配給最合適的超級代表點，這樣就能得到最后的聚類中心。

若G=[gij]N×N為分配矩陣，其中gij=1表示數據xi選擇數據xj作為代表點，而gii=k,k∈{1,2,…,N}表示代表點xi的超級代表點為xk。MEAP方法的目標是求使 S(G)=S1+S2達到最大的最優分配，那么G*中主對角線上的元素即為最后的聚類中心，其中表示各個數據點相對應的代表點之間的相似度之和，表示各個代表點相對應的超級代表點之間的相關度之和，而l(i,j)=s(i,j)/N表示代表點xi與其潛在超級代表點xj之間的關聯程度，矩陣稱為關聯矩陣。由于極大化目標函數S(G)是一個NP難問題，采用置信傳播（belief propagation,BP）中的max-sum方法[10]來表示數據點、代表點和超級代表點之間的消息傳遞。當i≠j(i=1,2,…,N,j=1,2,…,N)時：

而對i=1,2,…,N,k=1,2,…,N有：

MEAP算法擴大了聚類決策邊界，在不考慮關聯矩陣L的情況下它退化為AP算法。由于MEAP算法中增加了4條消息傳遞函數，而每條消息函數的時間復雜度為Ο(N2lbN)，故其存儲和時間復雜度大大增加，從而限制了其在大規模數據集上的應用。

3.2FRSMEAP算法

MEAP算法在面向大規模數據集時，時空效率低。本文使用快速壓縮集密度估計（FRSDE）對原始大規模數據樣本進行壓縮，使得壓縮后數據集的密度估計與原數據集近似，較好地保持了數據集的特性，能從根本上減少MEAP聚類過程的樣本數據，從而減小算法的時間開銷，同時兼顧MEAP聚類的優點，很好地平衡了時間與精度之間的矛盾。

文獻[11]提出壓縮集密度估計器（reduced set density estimator,RSDE），文獻[12]進一步揭示了RSDE與核化中心約束極小化包含球（center-constrained minimal enclosing ball,CCMEB）問題之間的等價關系，利用快速核心集技術[13]求解CCMEB問題，得到具有與原始數據集近似的核密度估計函數的目標壓縮數據集，提出了FRSDE。為增強算法的適用性，在FRSDE算法中引入非線性函數映射φ(x)將低維數據映射到高維空間特征Γ，并在特征空間中尋求以為中心的最小包含球（minimal enclosing ball,MEB），其中δ∈R，c為Γ中特征向量。在數據子集Q?X上CCMEB問題可表示為：

其對偶形式為：

其中，α為p維Lagrange乘子向量；1=[1,1,…,1]T為p維列向量；K=[k(xi,xj)]=[φ(xi)Tφ(xj)]為Q上的 p×p維核矩陣，p為Q中數據個數。設問題（11）關于Q的最優解為α*，則與Q相關的最小包含球半徑R*和中心c*分別為：

特征空間Γ′中任一個點到球心的距離平方為：

核心集之間采用高斯核作為核函數進行核密度估計，FRSDE方法通過不斷擴大核心集，最后得到包含X的最小包含球的核心集，此時由所對應的數據而組成的集合Xr稱為FRSDE的壓縮集。

MEAP算法中每條消息的傳遞都可能出現震蕩，為了消除出現的震蕩，在步驟7的消息參數傳遞過程中引入阻尼系數λ，μ=λμold+(1-λ)μnew，μ代表7條消息參數中的任意一條，λ越大消除震蕩的效果越好，但是算法的收斂速度會減慢。

3.3算法復雜性分析

在MEAP算法中，每條消息參數每次迭代的時間復雜度為Ο(N2lbN)，令迭代次數為ρ，MEAP的時間復雜度為Ο(ρN2lbN)。在FRSMEAP算法中，步驟3求離中心點ct最遠點時，每次迭代的時間復雜度為，其中為尋找最遠點的目標域樣本規模，當樣本規模N較大時非常耗時。此時文獻[14]通過在中隨機抽取子集來尋找最遠點，當子集規模時最遠點在中的概率約為95%，這樣復雜性降為。類似于FRSDE算法[12]，步驟4中利用核心集求解問題（11）的時間復雜度為Ο(N′/ε2+1/ε4)，其中N′為核心集中樣本數，ε為逼近參數，由于N′＜＜N，故該復雜性也遠小于求解所有樣本的時間復雜性。對壓縮集Xr進行聚類的時間復雜性為Ο(dM2lbM)，其中d為迭代次數；分配剩余點的時間復雜性為Ο(N-M)。這樣，FRSMEAP算法總的時間復雜性上界為Ο(N/ε2+ 1/ε4+dM2lbM+N-M)，M＜＜N，它與總樣本數N成線性關系。

綜上可見，FRSMEAP算法的復雜性遠小于MEAP算法的復雜性，其運算速度得到很大的提高，從而能解決MEAP算法無法解決的大數據集問題。

4　實驗及結果分析

為驗證FRSMEAP算法在大樣本聚類問題上的有效性，本文將在不同的數據集上進行實驗，除了FRSMEAP算法以外，也運行MEAP、AP、Kcenters[15]以及模糊C均值（fuzzy C-means，FCM）聚類算法[16]。用NMI（normalized mutual information）[17]、PR（Purity）[17]、RI（RandIndex）[17]、ACC（Accuracy）[17]作為聚類結果的評價指標。

實驗中，FCM算法采用Matlab工具箱中自帶的fcm函數，取默認參數設置。Kcenters、AP及MEAP算法中最大迭代次數為1 000，連續迭代100次直到聚類中心不變即停止計算。AP和MEAP算法的阻尼系數λ=0.9，逼近參數ε取值1E-5，η為3，核帶寬h取值為0.4～0.8。每個算法執行20次，得到聚類評價指標的均值和標準差。

4.1JAFFE數據集

JAFFE數據集總共有213張圖片，包含了10名女性的多種表情，每種表情有3～4張圖片。

各個算法的聚類性能比較如表1所示。

Table 1　Average values and standard deviations of NMI and average computational time on JAFFE data set表1　在JAFFE數據集上NMI的均值和標準差以及聚類平均時間

表1表明，FCM是一種執行速度很快的聚類算法，但是它同Kcenters一樣需要預先設定好聚類類別數，決定了這二者的不自適應性。在該數據集上FCM無法聚成10類，基本無效，印證了FCM適合凸數據集。MEAP能夠正確將JAFFE聚成10類，比Kcenters、AP算法更適合處理此多代表點模型，但由于迭代過程繁重的時間開銷，耗時最大。

4.2大規模人工數據集上的實驗

人工數據集CreateArtData（CD)由兩點簇和兩個括弧形數據組成，總共有4類，如圖1（a）所示。圖1（b）表示FRSMEAP算法對壓縮集的聚類結果。將人工數據樣本大小從120遞增到38 400時，4種聚類算法的聚類結果的4種評價指標如圖2所示。

由圖2（a）、（c）和（d）可知，在小樣本情況下，FRSMEAP算法的NMI、RI和ACC指標不夠穩定，僅低于FCM算法（k=4），卻優于其他算法；當樣本量分別大于600和1 920時，MEAP、AP和Kcenters算法已無法運行，而隨著樣本數的不斷增大，FRSMEAP算法的各項聚類指標趨于穩定，并與FCM算法（k=4）相當，且保持了AP和MEAP的精度；與未知類別數的FCM算法（k=3）相比，FRSMEAP算法更具有優勢。

表2給出了3種仿射類算法在樣本數增加時運行時間的情況。當樣本數多于1 920時，AP與MEAP算法在相同實驗環境下均無法運行，而FRSMEAP算法仍能繼續運行，且聚類時間雖然隨樣本數的增加而增加，但仍在可控范圍內。圖3描述了FRSMEAP算法的運行時間隨樣本數增加的線性漸近變化情況。

Fig.1　Synthetic data set and its condensed set clustering results圖1　人工數據集CD與壓縮集聚類結果

4.3真實數據集上的實驗

考慮以下幾個真實數據集Brain web、Sea、Shuttle和Iris，它們所含總樣本數、每個樣本的維數及所有樣本的類別數如表3所示。

（1）Brain web（BW）數據集

由于MEAP算法很耗時，難以在相同實驗環境下運行，故不取它作為對比算法。由圖2（e）、（g）和（h）可知，在小樣本容量情況下，FRSMEAP算法在4個指標上均能達到AP算法的效果。但當樣本規模超過3 000時，AP算法已無法運行，而FRSMEAP算法的這4個指標和FCM算法（k=2）相當，并延續了AP與MEAP算法聚類效果良好的優點，與未知類別數的FCM算法（k=3）相比，FRSMEAP算法也有一定的優勢。

Fig.2　Clustering evaluation index under different sample sizes of CD and BW data sets圖2　CD和BW數據集不同樣本容量下的聚類評價指標

Table 2　CD sample size with clustering time表2　CD樣本規模與聚類時間　s

Fig.3　Changed time of the proposed algorithm under different sample size of CD圖3　本文算法在不同CD樣本規模下的時間變化

Table 3　Datasets description表3　數據集描述

當樣本容量不同時，FRSMEAP與AP、MEAP算法的聚類時間如表4所示。

Table 4　BW sample size with clustering time表4　BW樣本規模與聚類時間　s

由表4可知，在樣本容量較小時，雖然AP算法也能夠進行，但所需時間會隨著樣本容量的增加而快速增長；當樣本數增大到一定量時，AP和MEAP算法均因內存溢出而無法執行，尤其是MEAP算法。而FRSMEAP算法在樣本超過3 000時，執行效率明顯優于AP、MEAP算法。圖4亦給出了FRSMEAP算法運行時間隨樣本數增加的線性漸近變化情況。

Fig.4　Changed time of the proposed algorithm under different sample size of BW圖4　本文算法在不同BW樣本規模下的運行時間

（2）Sea、Shuttle和Iris數據集

Iris來自UCI數據集，共3類，包含150個樣本。為了驗證大規模數據集下本文方法的性能，對Iris數據集進行擴充，擴充方法是為數據集樣本的每一個分量增加一個均值為0，方差為1的正態分布偏移量，擴充后的Iris樣本為75 000，如表3所示。由前面實驗可知，AP、MEAP和Kcenters算法均無法處理大規模數據集，故以下在3個大數據集上利用FCM和 FRSMEAP算法進行聚類，以NMI、PR和ACC指標的平均值和標準差作為聚類結果，如表5所示，括號內的數值表示標準差。

由表5、表6和表7知，FRSMEAP算法在Sea數據集上的各項聚類指標均優于FCM算法，而在Shuttle數據集上雖然NMI指標略低于FCM（k=7）算法，但PR和ACC聚類指標均明顯優于FCM算法。在Iris數據集上ACC指標要低于FCM（k=3）算法，但是要明顯高于FCM（k=4）算法。

Table 5　Clustering results of two algorithms on Sea data set表5　兩種算法在Sea大數據集上的聚類結果

Table 6　Clustering results of two algorithms on Shuttle data set表6　兩種算法在Shuttle大數據集上的聚類結果

Table 7　Clustering results of two algorithms on Iris data set表7　兩種算法在Iris大數據集上的聚類結果

綜合而言，FCM算法總是非常快速，在真實數據集上的結果再一次表明它一般只適合凸形數據集，而且需要預先設定好類別數，無自適應性。由于FRSMEAP算法涉及CCMEB求解，所需時耗要大于FCM算法。因為壓縮數據集保持了原數據屬性，而且MEAP算法具有更好的決策邊界，所以有很好的聚類效果，不低于FCM算法。因此，FRSMEAP聚類算法與傳統的MEAP算法相比，不僅能夠處理大數據問題，而且其聚類性能較優。

5　結束語

針對MEAP算法無法處理大數據集的問題，提出了一種快速多代表點仿射傳播聚類算法FRSMEAP。該算法首先用FRSDE方法對數據集進行壓縮預處理，并以壓縮后的小樣本數據集來模擬整個數據集，這樣可大大減小MEAP算法的聚類時間。實驗表明，FRSMEAP算法比MEAP和AP等算法更適合大數據聚類問題，而且其聚類精度不低于已有算法，表現出該算法的優越性。

References:

[1]Wang Zonghu.Research on the key techniques of clustering algorithm[D].Xi'an:Xi'an University of Electronic Science and Technology,2012.

[2]Frey B J,Dueck D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[3]Wang Jun,Wang Shitong,Deng Zhaohong.Several problems in cluster analysis[J].Control and Decision,2012,27 (3):321-328.

[4]Dong Jun,Wang Suoping,Xiong Fanlun.Affinity propagation clustering based on variable similarity measure[J]. Journal of Electronics&Information Technology,2010,32 (3):509-514.

[5]Arzeno N M,Vikalo H.Semi-supervised affinity propagation with soft instance-level constraints[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2015,37 (5):1041-1052.

[6]Sun Leilei,Guo Chonghui.Incremental affinity propagation clustering based on message passing[J].IEEE Transactions on Knowledge&Data Engineering,2014,26(11):2731-2744.

[7]Du Yanxin,Ge Hongwei,Xiao Zhiyong.Affinity propagation image segmentation based on the fuzzy connection of degree method[J].Journal of Computer Applications,2014, 34(11):3309-3313.

[8]Wang Changdong,Lai Jianhuang,Suen C Y,et al.Multiexemplar affinity propagation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2013,35(9):2223-2237.

[9]Zhu Manli,Martinez A M.Subclass discriminant analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(8):1274-1286.

[10]Dueck D.Affinity propagation:clustering data by passing messages[D].Toronto,Canada:University of Toronto,2009.

[11]Girolami M,He Chao.Probability density estimation from optimally condensed Data samples[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2003,25(10): 1253-1264.

[12]Deng Zhaohong,Chung Fulai,Wang Shitong.FRSDE:fast reduced set density estimator using minimal enclosing ball approximation[J].Pattern Recognition,2008,41(4):1363-1372.

[13]Tsang I W,Kwok J T Y,Zurada J M.Generalized core vector machines[J].IEEE Transactions on Neural Networks, 2006,17(5):1126-1140.

[14]Smola A J,Sch?kopf B.Sparse greedy matrix approximation for machine learning[C]//Proceedings of the 17th International Conference on Machine Learning,Stanford,USA, Jun 29-Jul 2,2000.San Francisco,USA:Morgan Kaufmann Publishers Inc,2000:911-918.

[15]Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability,Statistics.Berkeley,USA:University of California Press,1967,1:281-297.

[16]Bezdek J C,Ehrlich R,Full W.FCM:the fuzzy C-means clustering algorithm[J].Computers&Geosciences,1984, 10(84):191-203.

[17]Liu Jun,Mohammed J,Carter J,et al.Distance-based clustering of GGH data[J].Bioinformatics,2006,22(16):1971-1978.

附中文參考文獻：

[1]王縱虎.聚類分析優化關鍵技術研究[D].西安:西安電子科技大學,2012.

[3]王駿,王士同,鄧趙紅.聚類分析研究中的若干問題[J].控制與決策,2012,27(3):321-328.

[4]董俊,王鎖萍,熊范綸.可變相似性度量的近鄰傳播聚類[J].電子與信息學報,2010,32(3):509-514.

[7]杜艷新,葛洪偉,肖志勇.基于模糊連接度的近鄰傳播聚類圖像分割方法[J].計算機應用,2014,34(11):3309-3313.

LIU Ji was born in 1992.She is an M.S.candidate at School of Digital Media,Jiangnan University.Her research interests include pattern recognition and image processing,etc.

劉季（1992—），女，湖北鄂州人，江南大學數字媒體學院碩士研究生，主要研究領域為模式識別，圖像處理等。

陳秀宏（1964—），男，江蘇泰興人，2000年于華東理工大學獲得博士學位，2001年到2006年先后在南京大學和南京理工大學做博士后研究工作，現為江南大學數字媒體學院教授，主要研究領域為圖像處理，模式識別等。

HANG Wenlong was born in 1988.He is a Ph.D.candidate at School of Digital Media,Jiangnan University.His research interests include pattern recognition and image processing,etc.

杭文龍（1988—），男，江蘇南通人，江南大學數字媒體學院博士研究生，主要研究領域為模式識別，圖像處理等。

Fast Multi-ExemplarAffinity PropagationAlgorithm for Large Data Sets*

LIU Ji+,CHEN Xiuhong,HANG Wenlong
School of Digital Media,Jiangnan University,Wuxi,Jiangsu 214122,China
+Corresponding author:E-mail:liuji199209@163.com

The traditional affinity propagation(AP)is difficult to handle with multi-exemplar clustering,and has large space and time complexity,so it is not suitable for large data sets.To address these problems,this paper proposes a multi-exemplar affinity propagation using fast reduced set density estimator(FRSMEAP).At the beginning of clustering,fast reduced set density estimator(FRSDE)is introduced to preprocess large-scale data sets,and then the condensed set fully representing sample properties can be obtained.Multi-exemplar affinity propagation(MEAP)algorithm is used to cluster the condensed set,which can find better decision boundaries than AP.So the accuracy of clustering is improved.In order to get the final data partition,the K-nearest neighbor(KNN)is used to assign the remained data.The simulation results on synthetic and standard data sets show that the proposed algorithm can not only cluster on large-scale data sets,but also has the advantage of high precision and fast speed.

affinity propagation;clustering;large data sets;multi-exemplar

2015-05,Accepted 2015-07.

CHEN Xiuhong was born in 1964.He the Ph.D.degree from East China University of Science and Technology in 2000.From 2001 to 2006,he successively carries out post-doctoral studies at Nanjing University and Nanjing University of Technology.Now he is a professor at Jiangnan University.His research interests include image processing and pattern recognition,etc.

10.3778/j.issn.1673-9418.1505034

*The National Natural Science Foundation of China under Grant No.61373055(國家自然科學基金).

CNKI網絡優先出版：2015-07-13,http://www.cnki.net/kcms/detail/11.5602.TP.20150713.1426.002.html

A

TP181