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

劉　季，陳秀宏，杭文龍

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

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

1　引言

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

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

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

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

AP算法是一種無(wú)預(yù)設(shè)類(lèi)別數(shù)的聚類(lèi)方法，它將所有的數(shù)據(jù)點(diǎn)都作為潛在的代表點(diǎn)，以數(shù)據(jù)之間的相似度矩陣作為輸入，通過(guò)吸引度矩陣和歸屬度矩陣之間的迭代計(jì)算，不斷更新數(shù)據(jù)之間的消息，最終選出聚類(lèi)中心。設(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中元素（又稱(chēng)為消息參數(shù)）的交替更新。

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

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

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

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)，這樣就能得到最后的聚類(lèi)中心。

若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ì)角線上的元素即為最后的聚類(lèi)中心，其中表示各個(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)程度，矩陣稱(chēng)為關(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ò)大了聚類(lèi)決策邊界，在不考慮關(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聚類(lèi)過(guò)程的樣本數(shù)據(jù)，從而減小算法的時(shí)間開(kāi)銷(xiāo)，同時(shí)兼顧MEAP聚類(lèi)的優(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稱(chēng)為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ù)雜性降為。類(lèi)似于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)行聚類(lèi)的時(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)系。

綜上可見(jià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算法在大樣本聚類(lèi)問(wèn)題上的有效性，本文將在不同的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，除了FRSMEAP算法以外，也運(yùn)行MEAP、AP、Kcenters[15]以及模糊C均值（fuzzy C-means，F(xiàn)CM）聚類(lèi)算法[16]。用NMI（normalized mutual information）[17]、PR（Purity）[17]、RI（RandIndex）[17]、ACC（Accuracy）[17]作為聚類(lèi)結(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次直到聚類(lèi)中心不變即停止計(jì)算。AP和MEAP算法的阻尼系數(shù)λ=0.9，逼近參數(shù)ε取值1E-5，η為3，核帶寬h取值為0.4～0.8。每個(gè)算法執(zhí)行20次，得到聚類(lèi)評(píng)價(jià)指標(biāo)的均值和標(biāo)準(zhǔn)差。

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

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

各個(gè)算法的聚類(lèi)性能比較如表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)差以及聚類(lèi)平均時(shí)間

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

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

人工數(shù)據(jù)集CreateArtData（CD)由兩點(diǎn)簇和兩個(gè)括弧形數(shù)據(jù)組成，總共有4類(lèi)，如圖1（a）所示。圖1（b）表示FRSMEAP算法對(duì)壓縮集的聚類(lèi)結(jié)果。將人工數(shù)據(jù)樣本大小從120遞增到38 400時(shí)，4種聚類(lèi)算法的聚類(lèi)結(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)聚類(lèi)指標(biāo)趨于穩(wěn)定，并與FCM算法（k=4）相當(dāng)，且保持了AP和MEAP的精度；與未知類(lèi)別數(shù)的FCM算法（k=3）相比，F(xiàn)RSMEAP算法更具有優(yōu)勢(shì)。

表2給出了3種仿射類(lèi)算法在樣本數(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)行，且聚類(lèi)時(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與壓縮集聚類(lèi)結(jié)果

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

考慮以下幾個(gè)真實(shí)數(shù)據(jù)集Brain web、Sea、Shuttle和Iris，它們所含總樣本數(shù)、每個(gè)樣本的維數(shù)及所有樣本的類(lèi)別數(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算法聚類(lèi)效果良好的優(yōu)點(diǎn)，與未知類(lèi)別數(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ù)集不同樣本容量下的聚類(lèi)評(píng)價(jià)指標(biāo)

Table 2　CD sample size with clustering time表2　CD樣本規(guī)模與聚類(lèi)時(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算法的聚類(lèi)時(shí)間如表4所示。

Table 4　BW sample size with clustering time表4　BW樣本規(guī)模與聚類(lèi)時(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類(lèi)，包含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)行聚類(lèi)，以NMI、PR和ACC指標(biāo)的平均值和標(biāo)準(zhǔn)差作為聚類(lèi)結(jié)果，如表5所示，括號(hào)內(nèi)的數(shù)值表示標(biāo)準(zhǔn)差。

由表5、表6和表7知，F(xiàn)RSMEAP算法在Sea數(shù)據(jù)集上的各項(xiàng)聚類(lèi)指標(biāo)均優(yōu)于FCM算法，而在Shuttle數(shù)據(jù)集上雖然NMI指標(biāo)略低于FCM（k=7）算法，但PR和ACC聚類(lèi)指標(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ù)集上的聚類(lèi)結(jié)果

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

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

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

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

針對(duì)MEAP算法無(wú)法處理大數(shù)據(jù)集的問(wèn)題，提出了一種快速多代表點(diǎn)仿射傳播聚類(lèi)算法FRSMEAP。該算法首先用FRSDE方法對(duì)數(shù)據(jù)集進(jìn)行壓縮預(yù)處理，并以壓縮后的小樣本數(shù)據(jù)集來(lái)模擬整個(gè)數(shù)據(jù)集，這樣可大大減小MEAP算法的聚類(lèi)時(shí)間。實(shí)驗(yàn)表明，F(xiàn)RSMEAP算法比MEAP和AP等算法更適合大數(shù)據(jù)聚類(lèi)問(wèn)題，而且其聚類(lèi)精度不低于已有算法，表現(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]王縱虎.聚類(lèi)分析優(yōu)化關(guān)鍵技術(shù)研究[D].西安:西安電子科技大學(xué),2012.

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

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

[7]杜艷新,葛洪偉,肖志勇.基于模糊連接度的近鄰傳播聚類(lèi)圖像分割方法[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