劉　季，陳秀宏，杭文龍

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122

面向大規(guī)模數(shù)據(jù)的快速多代表點(diǎn)仿射傳播算法*

劉季+，陳秀宏，杭文龍

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 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.

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

仿射傳播；聚類；大數(shù)據(jù)；多代表點(diǎn)

1　引言

聚類是將物理或者抽象對(duì)象的集合依據(jù)對(duì)象的相似性分成多個(gè)類別的過(guò)程，使得同一個(gè)類別中的對(duì)象之間具有較高的相似度，而不同類別中的對(duì)象具有較低的相似度。在機(jī)器學(xué)習(xí)中，聚類是一種很重要的無(wú)監(jiān)督學(xué)習(xí)方法[1]。

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

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

2　經(jīng)典的仿射傳播聚類算法

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

對(duì)于任意數(shù)據(jù)xi，迭代最后它所在類的代表點(diǎn)為，將具有相同類代表點(diǎn)的數(shù)據(jù)聚為同一個(gè)類。

3　基于大數(shù)據(jù)集的快速多代表點(diǎn)仿射傳播聚類算法

3.1多代表點(diǎn)的仿射傳播聚類算法

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

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

而對(duì)i=1,2,…,N,k=1,2,…,N有：

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

3.2FRSMEAP算法

MEAP算法在面向大規(guī)模數(shù)據(jù)集時(shí)，時(shí)空效率低。本文使用快速壓縮集密度估計(jì)（FRSDE）對(duì)原始大規(guī)模數(shù)據(jù)樣本進(jìn)行壓縮，使得壓縮后數(shù)據(jù)集的密度估計(jì)與原數(shù)據(jù)集近似，較好地保持了數(shù)據(jù)集的特性，能從根本上減少M(fèi)EAP聚類過(guò)程的樣本數(shù)據(jù)，從而減小算法的時(shí)間開銷，同時(shí)兼顧MEAP聚類的優(yōu)點(diǎn)，很好地平衡了時(shí)間與精度之間的矛盾。

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

其對(duì)偶形式為：

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

特征空間?！渲腥我粋€(gè)點(diǎn)到球心的距離平方為：

核心集之間采用高斯核作為核函數(shù)進(jìn)行核密度估計(jì)，F(xiàn)RSDE方法通過(guò)不斷擴(kuò)大核心集，最后得到包含X的最小包含球的核心集，此時(shí)由所對(duì)應(yīng)的數(shù)據(jù)而組成的集合Xr稱為FRSDE的壓縮集。

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

3.3算法復(fù)雜性分析

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

綜上可見，F(xiàn)RSMEAP算法的復(fù)雜性遠(yuǎn)小于MEAP算法的復(fù)雜性，其運(yùn)算速度得到很大的提高，從而能解決MEAP算法無(wú)法解決的大數(shù)據(jù)集問(wèn)題。

4　實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證FRSMEAP算法在大樣本聚類問(wèn)題上的有效性，本文將在不同的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，除了FRSMEAP算法以外，也運(yùn)行MEAP、AP、Kcenters[15]以及模糊C均值（fuzzy C-means，F(xiàn)CM）聚類算法[16]。用NMI（normalized mutual information）[17]、PR（Purity）[17]、RI（RandIndex）[17]、ACC（Accuracy）[17]作為聚類結(jié)果的評(píng)價(jià)指標(biāo)。

實(shí)驗(yàn)中，F(xiàn)CM算法采用Matlab工具箱中自帶的fcm函數(shù)，取默認(rèn)參數(shù)設(shè)置。Kcenters、AP及MEAP算法中最大迭代次數(shù)為1 000，連續(xù)迭代100次直到聚類中心不變即停止計(jì)算。AP和MEAP算法的阻尼系數(shù)λ=0.9，逼近參數(shù)ε取值1E-5，η為3，核帶寬h取值為0.4～0.8。每個(gè)算法執(zhí)行20次，得到聚類評(píng)價(jià)指標(biāo)的均值和標(biāo)準(zhǔn)差。

4.1JAFFE數(shù)據(jù)集

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

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

Table 1　Average values and standard deviations of NMI and average computational time on JAFFE data set表1　在JAFFE數(shù)據(jù)集上NMI的均值和標(biāo)準(zhǔn)差以及聚類平均時(shí)間

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

4.2大規(guī)模人工數(shù)據(jù)集上的實(shí)驗(yàn)

人工數(shù)據(jù)集CreateArtData（CD)由兩點(diǎn)簇和兩個(gè)括弧形數(shù)據(jù)組成，總共有4類，如圖1（a）所示。圖1（b）表示FRSMEAP算法對(duì)壓縮集的聚類結(jié)果。將人工數(shù)據(jù)樣本大小從120遞增到38 400時(shí)，4種聚類算法的聚類結(jié)果的4種評(píng)價(jià)指標(biāo)如圖2所示。

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

表2給出了3種仿射類算法在樣本數(shù)增加時(shí)運(yùn)行時(shí)間的情況。當(dāng)樣本數(shù)多于1 920時(shí)，AP與MEAP算法在相同實(shí)驗(yàn)環(huán)境下均無(wú)法運(yùn)行，而FRSMEAP算法仍能繼續(xù)運(yùn)行，且聚類時(shí)間雖然隨樣本數(shù)的增加而增加，但仍在可控范圍內(nèi)。圖3描述了FRSMEAP算法的運(yùn)行時(shí)間隨樣本數(shù)增加的線性漸近變化情況。

Fig.1　Synthetic data set and its condensed set clustering results圖1　人工數(shù)據(jù)集CD與壓縮集聚類結(jié)果

4.3真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)

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

（1）Brain web（BW）數(shù)據(jù)集

由于MEAP算法很耗時(shí)，難以在相同實(shí)驗(yàn)環(huán)境下運(yùn)行，故不取它作為對(duì)比算法。由圖2（e）、（g）和（h）可知，在小樣本容量情況下，F(xiàn)RSMEAP算法在4個(gè)指標(biāo)上均能達(dá)到AP算法的效果。但當(dāng)樣本規(guī)模超過(guò)3 000時(shí)，AP算法已無(wú)法運(yùn)行，而FRSMEAP算法的這4個(gè)指標(biāo)和FCM算法（k=2）相當(dāng)，并延續(xù)了AP與MEAP算法聚類效果良好的優(yōu)點(diǎn)，與未知類別數(shù)的FCM算法（k=3）相比，F(xiàn)RSMEAP算法也有一定的優(yōu)勢(shì)。

Fig.2　Clustering evaluation index under different sample sizes of CD and BW data sets圖2　CD和BW數(shù)據(jù)集不同樣本容量下的聚類評(píng)價(jià)指標(biāo)

Table 2　CD sample size with clustering time表2　CD樣本規(guī)模與聚類時(shí)間　s

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

Table 3　Datasets description表3　數(shù)據(jù)集描述

當(dāng)樣本容量不同時(shí)，F(xiàn)RSMEAP與AP、MEAP算法的聚類時(shí)間如表4所示。

Table 4　BW sample size with clustering time表4　BW樣本規(guī)模與聚類時(shí)間　s

由表4可知，在樣本容量較小時(shí)，雖然AP算法也能夠進(jìn)行，但所需時(shí)間會(huì)隨著樣本容量的增加而快速增長(zhǎng)；當(dāng)樣本數(shù)增大到一定量時(shí)，AP和MEAP算法均因內(nèi)存溢出而無(wú)法執(zhí)行，尤其是MEAP算法。而FRSMEAP算法在樣本超過(guò)3 000時(shí)，執(zhí)行效率明顯優(yōu)于AP、MEAP算法。圖4亦給出了FRSMEAP算法運(yùn)行時(shí)間隨樣本數(shù)增加的線性漸近變化情況。

Fig.4　Changed time of the proposed algorithm under different sample size of BW圖4　本文算法在不同BW樣本規(guī)模下的運(yùn)行時(shí)間

（2）Sea、Shuttle和Iris數(shù)據(jù)集

Iris來(lái)自UCI數(shù)據(jù)集，共3類，包含150個(gè)樣本。為了驗(yàn)證大規(guī)模數(shù)據(jù)集下本文方法的性能，對(duì)Iris數(shù)據(jù)集進(jìn)行擴(kuò)充，擴(kuò)充方法是為數(shù)據(jù)集樣本的每一個(gè)分量增加一個(gè)均值為0，方差為1的正態(tài)分布偏移量，擴(kuò)充后的Iris樣本為75 000，如表3所示。由前面實(shí)驗(yàn)可知，AP、MEAP和Kcenters算法均無(wú)法處理大規(guī)模數(shù)據(jù)集，故以下在3個(gè)大數(shù)據(jù)集上利用FCM和 FRSMEAP算法進(jìn)行聚類，以NMI、PR和ACC指標(biāo)的平均值和標(biāo)準(zhǔn)差作為聚類結(jié)果，如表5所示，括號(hào)內(nèi)的數(shù)值表示標(biāo)準(zhǔn)差。

由表5、表6和表7知，F(xiàn)RSMEAP算法在Sea數(shù)據(jù)集上的各項(xiàng)聚類指標(biāo)均優(yōu)于FCM算法，而在Shuttle數(shù)據(jù)集上雖然NMI指標(biāo)略低于FCM（k=7）算法，但PR和ACC聚類指標(biāo)均明顯優(yōu)于FCM算法。在Iris數(shù)據(jù)集上ACC指標(biāo)要低于FCM（k=3）算法，但是要明顯高于FCM（k=4）算法。

Table 5　Clustering results of two algorithms on Sea data set表5　兩種算法在Sea大數(shù)據(jù)集上的聚類結(jié)果

Table 6　Clustering results of two algorithms on Shuttle data set表6　兩種算法在Shuttle大數(shù)據(jù)集上的聚類結(jié)果

Table 7　Clustering results of two algorithms on Iris data set表7　兩種算法在Iris大數(shù)據(jù)集上的聚類結(jié)果

綜合而言，F(xiàn)CM算法總是非常快速，在真實(shí)數(shù)據(jù)集上的結(jié)果再一次表明它一般只適合凸形數(shù)據(jù)集，而且需要預(yù)先設(shè)定好類別數(shù)，無(wú)自適應(yīng)性。由于FRSMEAP算法涉及CCMEB求解，所需時(shí)耗要大于FCM算法。因?yàn)閴嚎s數(shù)據(jù)集保持了原數(shù)據(jù)屬性，而且MEAP算法具有更好的決策邊界，所以有很好的聚類效果，不低于FCM算法。因此，F(xiàn)RSMEAP聚類算法與傳統(tǒng)的MEAP算法相比，不僅能夠處理大數(shù)據(jù)問(wèn)題，而且其聚類性能較優(yōu)。

5　結(jié)束語(yǔ)

針對(duì)MEAP算法無(wú)法處理大數(shù)據(jù)集的問(wèn)題，提出了一種快速多代表點(diǎn)仿射傳播聚類算法FRSMEAP。該算法首先用FRSDE方法對(duì)數(shù)據(jù)集進(jìn)行壓縮預(yù)處理，并以壓縮后的小樣本數(shù)據(jù)集來(lái)模擬整個(gè)數(shù)據(jù)集，這樣可大大減小MEAP算法的聚類時(shí)間。實(shí)驗(yàn)表明，F(xiàn)RSMEAP算法比MEAP和AP等算法更適合大數(shù)據(jù)聚類問(wèn)題，而且其聚類精度不低于已有算法，表現(xiàn)出該算法的優(yōu)越性。

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.

附中文參考文獻(xiàn)：

[1]王縱虎.聚類分析優(yōu)化關(guān)鍵技術(shù)研究[D].西安:西安電子科技大學(xué),2012.

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

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

[7]杜艷新,葛洪偉,肖志勇.基于模糊連接度的近鄰傳播聚類圖像分割方法[J].計(jì)算機(jī)應(yīng)用,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—），女，湖北鄂州人，江南大學(xué)數(shù)字媒體學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，圖像處理等。

陳秀宏（1964—），男，江蘇泰興人，2000年于華東理工大學(xué)獲得博士學(xué)位，2001年到2006年先后在南京大學(xué)和南京理工大學(xué)做博士后研究工作，現(xiàn)為江南大學(xué)數(shù)字媒體學(xué)院教授，主要研究領(lǐng)域?yàn)閳D像處理，模式識(shí)別等。

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—），男，江蘇南通人，江南大學(xué)數(shù)字媒體學(xué)院博士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，圖像處理等。

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(國(guó)家自然科學(xué)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-07-13,http://www.cnki.net/kcms/detail/11.5602.TP.20150713.1426.002.html

A

TP181