李滔，王士同

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

?

適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法

李滔，王士同

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

摘要：FCPM算法已被成功地應(yīng)用到模糊系統(tǒng)建模上，但其在某一類的聚類中心已知的大規(guī)模數(shù)據(jù)上的聚類性能較差。為了避免這個(gè)缺點(diǎn)，參照單程模糊c均值(SPFCM)聚類算法、在線模糊c均值(OFCM)聚類算法，提出了適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法(Incremental fuzzy (c+p)-means clustering ,IFCM(c+p))。通過在每個(gè)數(shù)據(jù)塊中使用FCPM算法進(jìn)行聚類，把每個(gè)數(shù)據(jù)塊的聚類中心及其附近的一些樣本點(diǎn)加入到下一個(gè)數(shù)據(jù)塊參與聚類，同時(shí)添加平衡因子以提高算法聚類性能。同SPFCM、OFCM以及rseFCM算法相比，IFCM(c+p)對(duì)初始聚類中心不敏感。實(shí)驗(yàn)表明在沒有花費(fèi)很多運(yùn)行時(shí)間的情況下，IFCM(c+p)算法的聚類性能比SPFCM算法和rseFCM算法更具優(yōu)勢，因此該算法更適合處理某一類聚類中心已知的大規(guī)模數(shù)據(jù)集。

關(guān)鍵詞：增量式模糊聚類；FCPM；IFCM(c+p)；平衡因子；大規(guī)模數(shù)據(jù)集

中文引用格式：李滔，王士同. 適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(2): 188-199.

英文引用格式：LI Tao， WANG Shitong. Incremental fuzzy (c+p)-means clustering for large data[J]. CAAI transactions on intelligent systems, 2016, 11(2): 188-199.

聚類就是將物理或抽象的對(duì)象按照自己的某些屬性聚集成類的過程，并盡可能使得類(或者簇)之間對(duì)象的差異程度最大，而類內(nèi)(或者簇內(nèi))的相似程度達(dá)到最大。聚類過程沒有先驗(yàn)知識(shí)指導(dǎo)，僅憑對(duì)象間的相似程度作為類屬劃分的準(zhǔn)則，是無監(jiān)督分類學(xué)習(xí)的一部分。最為經(jīng)典的模糊聚類算法之一就是J.C.Bezdek教授在20世紀(jì)80年代提出的模糊c均值聚類算法[1]，該算法被成功地應(yīng)用到了在諸多問題的解決上。

隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)庫中的數(shù)據(jù)更新速度日益加快、數(shù)據(jù)容量不斷增大，若仍然采用原來的聚類算法對(duì)這樣的大規(guī)模數(shù)據(jù)進(jìn)行聚類將產(chǎn)生以下幾個(gè)問題：1)數(shù)據(jù)更新前得到的聚類結(jié)果可能與數(shù)據(jù)更新后的聚類結(jié)果不匹配；2)對(duì)更新后的數(shù)據(jù)進(jìn)行重新聚類會(huì)導(dǎo)致較高的時(shí)間復(fù)雜度和計(jì)算資源的浪費(fèi)；3)還可能由于系統(tǒng)內(nèi)存不足的原因而導(dǎo)致該算法失效。鑒于這些問題，F(xiàn)azli Can教授在1990年提出的增量式聚類算法[2]使得這些問題得以解決。所謂增量式聚類是指利用前期數(shù)據(jù)已取得的聚類結(jié)果，對(duì)新增數(shù)據(jù)進(jìn)行分批或者逐批次地進(jìn)行聚類的過程。研究增量式模糊聚類算法對(duì)于避免重復(fù)聚類造成的計(jì)算資源浪費(fèi)，提高聚類性能等都具有十分重要的意義。

近幾年，研究者們提出了很多關(guān)于增量式聚類的算法。這些算法大致可以被分為3類：1)對(duì)大數(shù)據(jù)進(jìn)行隨機(jī)抽樣獲取小樣本進(jìn)行計(jì)算，例如，L. Kaufman等提出的CLARA[3]，S.Guha等[4]提出的CURE；2)按序?qū)⑿颖炯虞d進(jìn)內(nèi)存的單程算法(single-pass)，具有代表性的有F. Can在文獻(xiàn)[5]和[6]中提出的增量式算法；3)采取類圖表結(jié)構(gòu)的數(shù)據(jù)轉(zhuǎn)換算法，如T. Zhang等提出的BIRCH[7]和R. Ng等[8]提出的CLARANS，對(duì)于增量式模糊聚類算法；B. U. Shankar等[9]提出了快速模糊c均值算法FFCM，T. Cheng[10]提出了多階段的隨機(jī)模糊c均值算法MRFCM，J. F. Kolen等[11]提出了隨機(jī)抽樣模糊c均值算法rsFCM，Dhanesh Kothari等[12]提出了將隨機(jī)抽樣的結(jié)果擴(kuò)展到整個(gè)數(shù)據(jù)集上的擴(kuò)展隨機(jī)抽樣模糊c均值算法rseFCM。除此之外，還有基于FCM的單程模糊c均值算法SPFCM[13]、在線模糊c均值算法OFCM[14]，以及在這基礎(chǔ)上發(fā)展的基于核的模糊c均值算法spkFCM和okFCM[15]，Yangtao Wang等[16]提出的基于多重中心的增量式模糊聚類算法在相關(guān)性大數(shù)據(jù)上的應(yīng)用。最近B?hm等[17]受到動(dòng)力學(xué)中同步現(xiàn)象的啟發(fā)提出了一種新穎的同步聚類算法Sync，但是這種算法在大規(guī)模數(shù)據(jù)集上的聚類受到了相當(dāng)大的限制，基于此應(yīng)文豪等[18]在此基礎(chǔ)上提出了快速自適應(yīng)同步聚類算法FAKCS。

傳統(tǒng)的FCM算法對(duì)初始聚類中心敏感且容易陷入局部最優(yōu)，同時(shí)也忽略了類間的相互影響。Jacek M. Leski對(duì)FCM算法進(jìn)行了改進(jìn)，提出了模糊c+p均值聚類算法FCPM，并采用了新的方法初始化聚類中心[19]。對(duì)于某一類的聚類中心，它能吸引屬于該類的樣本并排斥屬于其他類的樣本，這樣更清楚地確定了樣本的“歸屬”問題。對(duì)于小樣本數(shù)據(jù)，F(xiàn)CPM算法可以保持不錯(cuò)的聚類性能，但其在大規(guī)模數(shù)據(jù)集上的聚類性能明顯降低而且有較大的時(shí)間花費(fèi)，甚至可能由于無法加載進(jìn)內(nèi)存而導(dǎo)致算法失效。對(duì)于以往的增量式模糊聚類算法，比如SPFCM算法和OFCM算法都是通過對(duì)樣本加權(quán)以影響每個(gè)數(shù)據(jù)塊產(chǎn)生的聚類中心，但數(shù)據(jù)塊間聚類中心的相互影響程度不明顯甚至可能會(huì)由于上一次聚類結(jié)果的加入而干擾新的數(shù)據(jù)進(jìn)行聚類。為了解決以上問題，通過FCPM算法計(jì)算每個(gè)數(shù)據(jù)塊的聚類中心，把離聚類中心最近的一些樣本點(diǎn)連同聚類中心一起加入到下一個(gè)數(shù)據(jù)塊中參與聚類，同時(shí)添加平衡項(xiàng)以提高聚類性能，文中提出了適合大規(guī)模數(shù)據(jù)集的增量式聚類算法IFCM(c+p)。

1相關(guān)算法

設(shè)N元樣本集合X={x1,x2,…,xN}，xk(k=1,2，…,N)表示其中的某一個(gè)樣本，其中每一個(gè)樣本都有D={d1,d2,…,dn}?Rn一共n個(gè)特征，dj(j=1,2，…,n)表示其中的某一個(gè)特征。FCM算法將N個(gè)樣本按照它所固有的特征劃分成c簇，用μik表示第k個(gè)樣本隸屬于第i簇的程度，那么劃分成c簇后得到的隸屬度矩陣是U={μik}?Rc×N,i∈[1,c],k∈[1,N]。對(duì)于模糊劃分而言，所有的樣本都需要滿足下面的條件：

由此可見，模糊劃分矩陣U的每一列的和都必須等于1，這樣才能確保每一個(gè)樣本都能夠被完整地劃分到它所屬的簇中。

通過使用歐式距離尋求最小均方誤差，可以得到FCM模型的目標(biāo)函數(shù)(其中m為模糊指數(shù))：

(1)

在式(1)的條件下通過拉格朗日乘子法可以得出隸屬度矩陣U和聚類中心V的更新公式。由于篇幅有限，F(xiàn)CM算法的具體更新公式以及計(jì)算步驟在此不做贅述。

傳統(tǒng)的FCM算法讓聚類中心盡可能地靠近樣本點(diǎn)，概率約束也只考慮了聚類中心之間的排斥力，所有的樣本重要性相同，同時(shí)對(duì)初始聚類中心敏感、容易陷入局部最優(yōu)，得到的聚類結(jié)果往往不理想。JacekM.Leski考慮了類別間的相互影響，利用了新的方法初始化聚類中心，采用固定一類求其他類的方法，在FCM算法的基礎(chǔ)上提出了模糊c+p均值聚類算法FCPM。

FCPM算法中來自其他類的樣本對(duì)本類的聚類會(huì)產(chǎn)生影響，在某一類中，聚類中心應(yīng)該吸引屬于該類的樣本，而排斥其他類的樣本。設(shè)有c個(gè)聚類中心來自一類，而p個(gè)聚類中心來自另一類，該算法把N個(gè)樣本劃分成為c簇，可得目標(biāo)函數(shù)為

(2)

式中：Vi表示第i簇的聚類中心，zj表示已知的聚類中心。對(duì)所有的樣本而言，都應(yīng)該滿足如下關(guān)系：

(3)

式中：μik表示第k個(gè)樣本屬于第i簇的程度，ζjk表示第k個(gè)樣本屬于第j簇的程度，利用拉格朗日乘子法，可以得到劃分矩陣U、T以及聚類中心V的更新公式：

(4)

(5)

(6)

針對(duì)FCM算法對(duì)初始聚類中心敏感的問題，F(xiàn)CPM算法采用了新的方法初始化聚類中心。通過該方法初始化未知類的聚類中心V，使用FCM算法初始化已知類的聚類中心Z，再依次通過式(4)、(5)和(6)獲取模糊劃分矩陣U和聚類中心V。文獻(xiàn)[19]詳細(xì)介紹了新的聚類中心初始化方法及FCPM算法，此處不再贅述。

如文獻(xiàn)[19]所示，F(xiàn)CPM算法在模糊系統(tǒng)建模上得到了很好的應(yīng)用。該算法采用新的初始化聚類中心的方法有效地避免了FCM算法對(duì)初始聚類中心敏感的問題，通過先確定已知類聚類中心來求未知類聚類中心的方法以提高算法的聚類性能。通過實(shí)驗(yàn)可以發(fā)現(xiàn)，F(xiàn)CPM算法對(duì)一類已知的小樣本數(shù)據(jù)集有著不錯(cuò)的聚類性能，但對(duì)現(xiàn)實(shí)中的大規(guī)模數(shù)據(jù)集而言，該算法的聚類性能會(huì)下降、算法效率會(huì)大大降低甚至?xí)捎跇颖具^大而導(dǎo)致算法失效。基于這些問題，本文提出了適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法IFCM(c+p)。

2適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法IFCM(c+p)

2.1IFCM(c+p)算法

在增量式模糊聚類算法中，對(duì)每一個(gè)數(shù)據(jù)塊進(jìn)行聚類的算法起著舉足輕重的作用。針對(duì)以往基于FCM的增量式模糊聚類算法對(duì)初始聚類中心敏感的問題，文中采用了FCPM算法中提到的特別的方法初始化聚類中心。另外在傳統(tǒng)的增量式模糊聚類算法中，不管是靜態(tài)的還是動(dòng)態(tài)的、單程的還是在線的、一個(gè)中心或者是多個(gè)中心(多個(gè)中心形成了一個(gè)約束對(duì))等等的方法，都沒有考慮數(shù)據(jù)塊之間聚類中心的相互影響，提及的IFCM(c+p)算法很好地解決了這些問題。

(7)

下面采用拉格朗日極值法求模糊劃分矩陣U、T以及聚類中心V的更新公式。

(8)

對(duì)G(U,T,V,λ)中的各個(gè)變量分別求偏導(dǎo)并令其等于零得：

(9)

通過(9)可以很容易地求出模糊劃分矩陣的更新公式μik和ζjk，如式(4)、(5)所示?？梢园l(fā)現(xiàn)，模糊劃分矩陣U和T與平衡因子α無關(guān)。

由式(9)第4個(gè)等式可得

(10)

從式(10)可以看出，根據(jù)平衡因子α是否等于0，又可以分為兩種情況。

當(dāng)α=0即不考慮數(shù)據(jù)塊間聚類中心的相互影響時(shí)，在每一個(gè)數(shù)據(jù)塊的聚類過程中，將某個(gè)數(shù)據(jù)塊產(chǎn)生的聚類中心加入下一個(gè)數(shù)據(jù)塊中參與聚類，為了增大對(duì)數(shù)據(jù)塊間聚類效果的影響程度，把距聚類中心最近的n0個(gè)樣本點(diǎn)也一同加入下一個(gè)數(shù)據(jù)塊參與聚類，以此類推，直至計(jì)算出最后一個(gè)數(shù)據(jù)塊的聚類中心，這個(gè)最終的聚類中心就是我們所要求的整個(gè)數(shù)據(jù)集的聚類中心。

α=0時(shí)的情況僅僅考慮了某一數(shù)據(jù)塊的聚類中心及其周圍的n0個(gè)樣本點(diǎn)對(duì)下一個(gè)數(shù)據(jù)塊的聚類性能的影響，這樣得出的聚類效果并不理想。為了提高聚類性能，應(yīng)該考慮數(shù)據(jù)塊間聚類中心的相互影響即α≠0時(shí)的情況，此時(shí)平衡項(xiàng)的加入很好地提高了聚類性能。

如下所述為IFCM(c+p)算法的具體計(jì)算步驟。

輸入：X，c，p，m，n0，ε；

輸出：聚類中心V。

1)把樣本集x隨機(jī)劃分成大小相等的s個(gè)子集即x={X1,X2,…,Xs}；

2)定義一個(gè)空的集合Xincre和Xnear；

3)遍歷所有的數(shù)據(jù)塊獲取聚類中心：

forl=1,2，…，s

①初始化未知類和已知類的聚類中心V、Z；

②把從上一數(shù)據(jù)塊獲得的樣本Xincre添加到當(dāng)前數(shù)據(jù)塊，即Xl={Xl∪Xincre}；

③使用式(4)、(5)和(10)計(jì)算當(dāng)前數(shù)據(jù)塊的聚類中心Vl；

④取出距當(dāng)前數(shù)據(jù)塊的聚類中心最近的n0個(gè)樣本點(diǎn)存入Xnear中；

⑤把聚類中心Vl及其附近的n0個(gè)樣本點(diǎn)存入Xincre中，即Xincre={Vl∪Xnear}；

endfor

上述算法步驟2)的Xincre用以存放每一個(gè)數(shù)據(jù)塊產(chǎn)生的聚類中心及其附近的n0個(gè)樣本點(diǎn)Xnear，3)對(duì)這s個(gè)數(shù)據(jù)塊進(jìn)行遍歷，求其聚類中心。3)中的主要迭代過程在每個(gè)數(shù)據(jù)塊中使用FCPM算法計(jì)算聚類中心，使用歐氏距離求距聚類中心最近的n0個(gè)樣本點(diǎn)，并把它們一同加入到下一個(gè)數(shù)據(jù)塊中去參與聚類。注意在初始化聚類中心時(shí)，采用前面提到的FCPM算法的初始化方法對(duì)已知類和未知類的聚類中心Z、V進(jìn)行初始化，聚類中心V和模糊隸屬度矩陣U的更新公式分別為(10)、(4)，‖·‖表示求歐氏距離。FCPM算法的迭代終止于聚類中心的連續(xù)變化值的Frobenius范數(shù)小于ε。整個(gè)IFCM(c+p)算法終止于所有的數(shù)據(jù)塊遍歷結(jié)束并獲得最終的聚類中心。

2.2算法的可行性分析

正如傳統(tǒng)的增量式聚類算法一樣，IFCM(c+p)算法對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行聚類。在IFCM(c+p)算法中，沒有添加平衡項(xiàng)時(shí)，將每個(gè)數(shù)據(jù)塊的c個(gè)聚類中心及距其最近的n0個(gè)樣本點(diǎn)作為一次聚類結(jié)果的歷史信息加入到新增數(shù)據(jù)中，即每次都有c+n0個(gè)樣本點(diǎn)加入到新增數(shù)據(jù)中參與聚類，那么這些歷史信息的加入勢必將影響新增數(shù)據(jù)的聚類效果。如果歷史信息恰好位于新增數(shù)據(jù)附近，則其聚類效果將變好，如果歷史信息遠(yuǎn)離它們，歷史信息的加入反而會(huì)導(dǎo)致一個(gè)很差的聚類效果。對(duì)于SPFCM算法和OFCM算法而言，它們通過添加樣本權(quán)值以增加聚類效果，在一定程度上比僅僅添加歷史信息得到的聚類效果要好，但也存在上面所提到的一些問題。為了克服以上問題，提到的IFCM(c+p)算法添加了平衡項(xiàng)，通過平衡項(xiàng)中的平衡因子去改變數(shù)據(jù)塊間聚類中心的相互影響程度，此時(shí)即便歷史信息遠(yuǎn)離新增數(shù)據(jù)，通過合理調(diào)節(jié)平衡因子α的取值也可以使得聚類中心吸引它周圍的新增數(shù)據(jù)，從而提高聚類效果。

2.3算法復(fù)雜度

文獻(xiàn)[15]詳細(xì)介紹了rseFCM、SPFCM算法的時(shí)間和空間復(fù)雜度，如表1所示，本文提到的FCPM及IFCM(c+p)算法的時(shí)間和空間復(fù)雜度也如表1所示。其中t表示非增量式算法的迭代次數(shù)，t'表示增量式算法中每個(gè)數(shù)據(jù)塊的平均迭代次數(shù)，d表示數(shù)據(jù)集維數(shù)，c表示未知類的聚類個(gè)數(shù)，p表示已知類的聚類個(gè)數(shù)，s表示數(shù)據(jù)塊的個(gè)數(shù)，n0表示在IFCM(c+p)算法中距每個(gè)數(shù)據(jù)塊的聚類中心最近的樣本點(diǎn)個(gè)數(shù)。

表1　各算法的時(shí)間、空間復(fù)雜度

如表1所示，本文提到的算法均在相同環(huán)境下運(yùn)行，都對(duì)同一數(shù)據(jù)集X進(jìn)行處理，時(shí)間復(fù)雜度都為O(n)。然而從第3部分的實(shí)驗(yàn)可以看出，各算法的運(yùn)行時(shí)間存在著顯著不同。對(duì)于增量式模糊聚類算法，由于它們在每個(gè)數(shù)據(jù)塊的處理中能夠快速收斂因而可以使得算法總的運(yùn)行時(shí)間減少。

本文提到的增量式模糊聚類算法都是對(duì)數(shù)據(jù)進(jìn)行分塊處理，因此需要計(jì)算每個(gè)數(shù)據(jù)塊所占用的空間即為n/s。如表1所示，同rseFCM和SPFCM算法相比，由于IFCM(c+p)算法需要存儲(chǔ)聚類中心及其周圍的一些樣本，因此需要占用相對(duì)較多的存儲(chǔ)空間，也就擁有相對(duì)高的空間復(fù)雜度。

3相關(guān)實(shí)驗(yàn)研究

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

為了公正地對(duì)各聚類算法的聚類效果做出合理的評(píng)價(jià)，本文采用如下3種評(píng)價(jià)指標(biāo)進(jìn)行算法的性能分析。

3.1.1算法運(yùn)行時(shí)間的加速比speedup

該指標(biāo)反映了聚類算法在指定數(shù)據(jù)集下運(yùn)行時(shí)間的比較情況。定義加速比：

speedup=tfull/tincremental

式中:tfull表示在整個(gè)數(shù)據(jù)集下采用FCPM算法所運(yùn)行的時(shí)間；tincremental表示采用增量式算法比如SPFCM、IFCM(c+p)等所運(yùn)行的時(shí)間。

2)歸一化互信息(normalized mutual information，NMI)[20-21]

3)芮氏指標(biāo)(rand index，RI)[20-22]

式中：f00表示樣本點(diǎn)具有不同的類標(biāo)簽并且屬于不同類的配對(duì)樣本數(shù)目,f11則表示樣本點(diǎn)具有相同的類標(biāo)簽并且屬于同一類的配對(duì)樣本數(shù)目，N表示樣本總數(shù)。

以上NMI、RI兩種指標(biāo),其取值范圍均為[0,1],且取值越靠近1越能反映該聚類算法在某數(shù)據(jù)集下的聚類效果越好，反之越靠近0則反映該聚類算法的聚類效果越差。加速比speedup越大反映了增量式聚類算法的運(yùn)行時(shí)間越短。

3.2實(shí)驗(yàn)結(jié)果

1)實(shí)驗(yàn)環(huán)境

本文所有的實(shí)驗(yàn)均在如表2的環(huán)境中進(jìn)行。

2)實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)所選取的數(shù)據(jù)集包括人工數(shù)據(jù)集2D15(http://www.uef.fi/en/sipu/datasets)、UCI(http://archive.ics.uci.edu/ml/datasets.html)、標(biāo)準(zhǔn)數(shù)據(jù)集waveform、forest和手寫數(shù)字?jǐn)?shù)據(jù)集MNIST(http://yann.lecun.com/exdb/mnist/)。各數(shù)據(jù)集的分布情況如表3。

表2　實(shí)驗(yàn)環(huán)境

表3　各數(shù)據(jù)集的分布情況

MNIST數(shù)據(jù)集是手寫數(shù)字集的一個(gè)子集，包含了70 000張28 × 28 像素的數(shù)字0～9的圖像，每個(gè)像素都在整數(shù)0～255之間取值。為加快運(yùn)算，對(duì)MNIST數(shù)據(jù)集中的所有樣本分別除以255進(jìn)行歸一化處理[15]。為方便計(jì)算，本文隨機(jī)取forest的581 000個(gè)樣本進(jìn)行計(jì)算。同樣，對(duì)其他數(shù)據(jù)集也進(jìn)行歸一化處理以加快運(yùn)算，即用每個(gè)特征的所有樣本與該特征的最小值作差再除以該特征的最大值與最小值之差。

3)實(shí)驗(yàn)參數(shù)設(shè)置

本文中所有的參數(shù)都按如下取值：模糊指數(shù)m取2，最大迭代次數(shù)均為100，迭代終止參數(shù)ε取1e-3，聚類中心附近的樣本點(diǎn)個(gè)數(shù)n0取5，其中數(shù)據(jù)集2D15、waveform重復(fù)試驗(yàn)50次，由于數(shù)據(jù)集MNIST和forest樣本過大，我們重復(fù)試驗(yàn)20次。數(shù)據(jù)塊的大小應(yīng)由用戶指定，但在實(shí)驗(yàn)中，由于計(jì)算機(jī)內(nèi)存受限，forest數(shù)據(jù)集的數(shù)據(jù)塊大小依次取0.1%、0.5%、1%、2.5%、5%，其余均按照整個(gè)數(shù)據(jù)集的1%、2.5%、5%、10%、25%、50%隨機(jī)抽取。取MNIST數(shù)據(jù)集70%的樣本、forest數(shù)據(jù)集10%的樣本參與FCPM算法的聚類。平衡因子α的具體取值也由用戶指定，但是必須在給定的經(jīng)驗(yàn)值范圍內(nèi)取值，本文中的所有α值均是在多次重復(fù)實(shí)驗(yàn)中，提到的聚類指標(biāo)的均值達(dá)到最好的時(shí)候的取值。我們計(jì)算提到的幾種算法在各個(gè)數(shù)據(jù)集上的NMI和RI的最值、均值以及標(biāo)準(zhǔn)差，其中均值反映了算法的平均聚類性能，最值和標(biāo)準(zhǔn)差反映了算法的穩(wěn)定魯棒性。

4)算法性能比較

本文采用SPFCM算法和rseFCM算法同IFCM(c+p)算法在聚類性能和加速比上進(jìn)行比較。

1)各算法在數(shù)據(jù)集上的聚類性能比較

各算法在指定數(shù)據(jù)集下的聚類性能如表4～11所示，其中最優(yōu)均值已用黑體標(biāo)出。

表4　IFCM(c+p)、SPFCM、rseFCM算法的NMI值

從各表中的實(shí)驗(yàn)結(jié)果對(duì)比發(fā)現(xiàn)，增量式模糊聚類算法的聚類性能均優(yōu)于FCPM算法。在人工數(shù)據(jù)集2D15的聚類性能比較中發(fā)現(xiàn)數(shù)據(jù)塊大小取25%、35%和50%時(shí)，rseFCM算法和SPFCM算法的聚類性能略優(yōu)于IFCM(c+p)算法，對(duì)類似2D15這樣的小樣本數(shù)據(jù)集而言這種情況是可能的，而IFCM(c+p)算法在大規(guī)模數(shù)據(jù)集的聚類問題上可以表現(xiàn)出很好的效果。在本文提到的其他數(shù)據(jù)集中，IFCM(c+p)算法均能保持最好的聚類性能。在高維大樣本的手寫數(shù)字集MNIST和大樣本的forest數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)IFCM(c+p)算法在提高了聚類性能的同時(shí)還具備很好的穩(wěn)定魯棒性，這是本文其他算法不具備的。另外還可以發(fā)現(xiàn)隨著數(shù)據(jù)塊大小的增加，所有增量式模糊聚類算法的聚類性能均呈下降趨勢，這是由于本文提及的增量式算法均采用分塊處理的方式，隨著數(shù)據(jù)塊大小的增加直至接近原數(shù)據(jù)集大小時(shí)，在某數(shù)據(jù)塊中聚類就相當(dāng)于在整個(gè)數(shù)據(jù)集上進(jìn)行聚類，很明顯這樣增加算法運(yùn)行時(shí)間的同時(shí)還降低了聚類性能。另外還注意到對(duì)于大樣本數(shù)據(jù)，隨機(jī)抽取的數(shù)據(jù)塊較小時(shí)rseFCM算法會(huì)由于無法加載進(jìn)內(nèi)存而致使該算法失效，而IFCM(c+p)算法不用擔(dān)心這個(gè)問題。

表5　IFCM(c+p)、SPFCM、rseFCM算法在2D15數(shù)據(jù)集中的NMI值

表6　IFCM(c+p)、SPFCM、rseFCM算法在MNIST數(shù)據(jù)集中的NMI值

續(xù)表6

樣本大小IFCM(c+p)(α=160)avg.std.IFCM(c+p)(α=0)avg.std.SPFCMavg.std.rseFCMavg.std.10%0.321700.208900.22990——0.32170.32170.20890.20890.22960.2301——25%0.263400.218000.18180——0.26340.26340.21800.21800.18070.1832——35%0.330900.171200.20270.0131——0.33090.33090.17120.17120.17630.2328——50%0.213500.207200.17440.0188——0.21350.21350.20720.20720.16320.2037——FCPM(70%)0.172300.17230.1723

表7　IFCM(c+p)、SPFCM、rseFCM算法在forest數(shù)據(jù)集中的NMI值

表8　IFCM(c+p)、SPFCM、rseFCM算法在waveform數(shù)據(jù)集中的RI值

續(xù)表8

樣本大小IFCM(c+p)(α=2.1)avg.std.IFCM(c+p)(α=0)avg.std.SPFCMavg.std.rseFCMavg.std.25%0.66430.00180.663300.661300.663300.65370.66930.66330.66340.66120.66150.66320.663435%0.670200.664000.663200.66230.00240.66920.67030.66380.6640.66320.66330.66190.679050%0.669900.664400.665100.660700.66980.67010.66440.66440.66480.66520.66070.6608FCPM0.66220.00270.64920.6627

表9　IFCM(c+p)、SPFCM、rseFCM算法在2D15數(shù)據(jù)集中的RI值

表10　IFCM(c+p)、SPFCM、rseFCM算法在MNIST數(shù)據(jù)集中的RI值

續(xù)表10

樣本大小IFCM(c+p)(α=160)avg.std.IFCM(c+p)(α=0)avg.std.SPFCMavg.std.rseFCMavg.std.10%0.811700.642900.79470——0.81170.81170.64290.64290.79440.7953——25%0.737500.660800.72740——0.73750.73750.66080.66080.72700.7289——35%0.772900.607600.72150.0099——0.77290.77290.60760.60760.70320.7408——50%0.663300.661200.64200.0224——0.66330.66330.66120.66120.60940.6916——FCPM(70%)0.613400.61340.6134

表11　IFCM(c+p)、SPFCM、rseFCM算法在forest數(shù)據(jù)集中的RI值

2)各算法在數(shù)據(jù)集上運(yùn)行時(shí)間的加速比比較

各個(gè)算法相對(duì)于FCPM算法在不同數(shù)據(jù)集上不同大小的數(shù)據(jù)塊下運(yùn)行時(shí)間的加速比的比較情況下圖1所示。

圖1　IFCM(c+p)、SPFCM、rseFCM算法在不同數(shù)據(jù)集的不同大小數(shù)據(jù)塊下的加速比 Fig.1　Speedup ratio of IFCM(c+p), SPFCM, rseFCM for different chunk size of different datasets

從圖1中可以看出，本文提到的算法的運(yùn)行時(shí)間的加速比基本上隨著數(shù)據(jù)塊大小的增加呈下降趨勢，這是由于隨著數(shù)據(jù)塊大小的增加，提到的算法單次運(yùn)行的樣本總量在增加，因而運(yùn)行時(shí)間會(huì)隨之增加。在小樣本數(shù)據(jù)集waveform和2D15中，IFCM(c+p)算法的運(yùn)行時(shí)間高于SPFCM算法。由于forest數(shù)據(jù)集的數(shù)據(jù)塊取得較小，因而SPFCM算法在此時(shí)的運(yùn)行時(shí)間也較短。而在大樣本的MNIST數(shù)據(jù)集中，SPFCM算法的加速程度明顯降低，IFCM(c+p)算法的加速程度明顯提高。由此可見，IFCM(c+p)算法會(huì)隨著數(shù)據(jù)集樣本的增加而加速程度得到提高，尤其是對(duì)于一類聚類中心已知的大規(guī)模數(shù)據(jù)集，該算法的運(yùn)行時(shí)間會(huì)大幅降低。

4結(jié)束語

針對(duì)FCPM算法對(duì)大樣本數(shù)據(jù)聚類性能較差甚至可能出現(xiàn)算法失效的問題，本文在該算法的基礎(chǔ)上提出了IFCM(c+p)算法，特別是適合處理某一類已知的大規(guī)模數(shù)據(jù)集的聚類問題。通過對(duì)每一個(gè)數(shù)據(jù)塊使用FCPM算法獲取其聚類中心，并把它們及其附近的一些樣本點(diǎn)加入到下一個(gè)數(shù)據(jù)塊中參與聚類，同時(shí)添加平衡項(xiàng)以提高聚類性能。通過第3部分的實(shí)驗(yàn)可以發(fā)現(xiàn)，平衡項(xiàng)的加入提高了IFCM(c+p)算法的聚類性能和運(yùn)行時(shí)間，另外還保持了很好的穩(wěn)定魯棒性。平衡項(xiàng)中的平衡因子的合理選擇是IFCM(c+p)算法的關(guān)鍵所在，本文中所采用的方法是根據(jù)經(jīng)驗(yàn)值，保證公式(7)中的J(U,T,V)值與平衡項(xiàng)盡量處于同一數(shù)量級(jí)，取在各數(shù)據(jù)集下IFCM(c+p)算法能夠達(dá)到最好的聚能性能時(shí)的α值作為算法的最佳平衡因子。對(duì)于如何才能選取更好的平衡因子α，如何既保證算法的聚類性能又提高運(yùn)行時(shí)間，都是我們繼續(xù)研究的方向。

參考文獻(xiàn):

[1]BEZDEKJC,EHRLICHR,FULLW.FCM:thefuzzyc-meansclusteringalgorithm[J].Computers&Geosciences, 1984, 10(2): 191-203.

[2]CANF,DROCHAKNDII.Incrementalclusteringfordynamicdocumentdatabases[C]//Proceedingsofthe1990SymposiumonAppliedComputing.Fayetteville,AR,USA, 1990: 61-67.

[3]KAUFMANL,ROUSSEEUWPJ.Findinggroupsindata:anintroductiontoclusteranalysis[M].NewYork:JohnWiley&Sons, 2009: 830-832.

[4]GUHAS,RASTOGIR,SHIMK.Cure:anefficientclusteringalgorithmforlargedatabases[J].Informationsystems, 2001, 26(1): 35-58.

[5]CANF.Incrementalclusteringfordynamicinformationprocessing[J].ACMtransactionsoninformationsystems, 1993, 11(2): 143-164.

[6]CANF,FOXEA,SNAVELYCD,etal.Incrementalclusteringforverylargedocumentdatabases:InitialMARIANexperience[J].Informationsciences, 1995, 84(1/2): 101-114.

[7]ZHANGTian,RAMAKIRSHNANR,LIVNYM.BIRCH:Anefficientdataclusteringmethodforverylargedatabases[C]//Proceedingsofthe1998ACMSIGMODInternationalConferenceonManagementofData.NewYork,USA, 1996: 103-114.

[8]NGRT,HANJiawei.CLARANS:Amethodforclusteringobjectsforspatialdatamining[J].IEEEtransactionsonknowledgeanddataengineering, 2002, 14(5): 1003-1016.

[9]SHANKERBU,PALNR.FFCM:Aneffectiveapproachforlargedatasets[C]//Proceedingsofthe3rdInternationalConferenceonFuzzyLogic,NeuralNetsandSoftComputing.Iizuka,Japan, 1994: 331-332.

[10]CHENGTaiwai,GOLDGOFDB,HALLLO.Fastclusteringwithapplicationtofuzzyrulegeneration[C]//Proceedingsof1995IEEEInternationalFuzzySystems, 1995.InternationalJointConferenceoftheFourthIEEEInternationalConferenceonFuzzySystemsandTheSecondInternationalFuzzyEngineeringSymposium.Yokohama,Japan, 1995: 2289-2295.

[11]KOLENJF,HUTCHESONT.Reducingthetimecomplexityofthefuzzyc-meansalgorithm[J].IEEEtransactionsonfuzzysystems, 2002, 10(2): 263-267.

[12]KOTHARID,NARAYANANST,DEVIKK.Extendedfuzzyc-meanswithrandomsamplingtechniquesforclusteringlargedata[J].Internationaljournalofinnovativeresearchinadvancedengineering(IJIRAE), 2014, 1(1): 1-4.

[13]HOREP,HALLLO,GOLDGOFDB.Singlepassfuzzycmeans[C]//ProceedingsofIEEEInternationalFuzzySystemsConference.London,UK, 2007: 1-7.

[14]HOREP,HALLLO,GOLDGOFDB,etal.Onlinefuzzycmeans[C]//ProceedingsofAnnualMeetingoftheNorthAmericanFuzzyInformationProcessingSociety.NewYork,USA, 2008: 1-5.

[15]HAVENST,BEZDEKJ,LECKIEC,etal.Fuzzyc-meansalgorithmsforverylargedata[J].IEEEtransactionsonfuzzysystems, 2012, 20(6): 1130-1146.

[16]WANGYangtao,CHENLihui,MEIJianping.Incrementalfuzzyclusteringwithmultiplemedoidsforlargedata[J].IEEEtransactionsonfuzzysystems, 2014, 22(6): 1557-1568

[17]B?HMC,PLANTC,SHAOJ,etal.Clusteringbysynchronization[C]//Proceedingsofthe16thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,USA, 2010: 583-592.

[18]應(yīng)文豪, 許敏, 王士同, 等. 在大規(guī)模數(shù)據(jù)集上進(jìn)行快速自適應(yīng)同步聚類[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(4): 707-720.

YINGWenhao,XUMin,WANGShitong,etal.Fastadaptiveclusteringbysynchronizationonlargescaledatasets[J].Journalofcomputerresearchanddevelopment, 2014, 51(4): 707-720.

[19]LESKIJM.Fuzzy(c+p) -meansclusteringanditsapplicationtoafuzzyrule-basedclassifier:towardsgoodgeneralizationandgoodinterpretability[J].IEEEtransactionsonfuzzysystems, 2014, 23(4): 802-812.

[20]LIUJun,MOHAMMEDJ,CARTERJ,etal.Distance-BasedclusteringofCGHdata[J].Bioinformatics, 2006, 22(16): 1971-1978.

[21]DENGZhaohong,CHOIKS,CHUNGFulai,etal.Enhancedsoftsubspaceclusteringintegratingwithin-clusterandbetween-clusterinformation[J].Patternrecognition, 2010, 43(3): 767-781.

[22]RANDWM.Objectivecriteriafortheevaluationofclusteringmethods[J].JournaloftheAmericanstatisticalassociation, 1971, 66(336): 846-850.

李滔，男，1990年生，碩士研究生，主要研究方向?yàn)槿斯ぶ悄芘c模式識(shí)別、模糊聚類算法、增量式學(xué)習(xí)。

王士同，男，1964年生，教授，博士生導(dǎo)師，中國離散數(shù)學(xué)學(xué)會(huì)常務(wù)理事，中國機(jī)器學(xué)習(xí)學(xué)會(huì)常務(wù)理事。主要研究方向?yàn)槿斯ぶ悄?模式識(shí)別、圖像處理及其應(yīng)用等。發(fā)表學(xué)術(shù)論文近百篇，其中被SCI、EI檢索50余篇。

Incremental fuzzy (c+p)-means clustering for large data

LI Tao， WANG Shitong

(School of Digital Media， Jiangnan University， Wuxi 214122， China)

Abstract：FCPM has been demonstrated to be successful in fuzzy system modeling, however, it will be ineffective for large data clustering tasks where the cluster centers of one class are known. In order to circumvent this drawback, referring to single-pass fuzzy c-means (SPFCM) clustering algorithm and online fuzzy c-means (OFCM) clustering algorithm, the incremental fuzzy clustering algorithm for large data called IFCM(c+p) is proposed in this paper. FCPM algorithm is used to cluster for each data block at first, and then the clustering centers of data block and some of the sample points being near them are joined into the next block to be clustered, meanwhile the balance factor is given to enhance the clustering performance. In contrast to SPFCM, OFCM and rseFCM, IFCM(c+p) is not sensitive to the initial cluster centers. The experiments indicate the proposed clustering algorithm IFCM(c+p) is competitive to the clustering algorithms SPFCM and rseFCM in the clustering performance without the loss of running time a lot, hence it is especially suitable for large data clustering tasks where the cluster centers of one class are known.

Keywords：incremental fuzzy clustering； FCPM； IFCM(c+p)； balance factor； large data

作者簡介：

中圖分類號(hào)：TP391.4

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-4785(2016)02-0188-12

通信作者：李滔. E-mail：chasingdream119@163.com.

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61272210).

收稿日期：2015-07-06. 網(wǎng)絡(luò)出版日期：2016-03-15.

DOI:10.11992/tis.201507013

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160315.1239.014.html