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

李滔，王士同

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

?

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

李滔，王士同

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

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

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

中文引用格式：李滔，王士同. 適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法[J]. 智能系統(tǒng)學報， 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.

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

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

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

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

1相關算法

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

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

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

(1)

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

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

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

(2)

式中：Vi表示第i簇的聚類中心，zj表示已知的聚類中心。對所有的樣本而言，都應該滿足如下關系：

(3)

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

(4)

(5)

(6)

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

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

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

2.1IFCM(c+p)算法

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

(7)

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

(8)

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

(9)

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

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

(10)

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

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

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

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

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

輸出：聚類中心V。

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

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

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

forl=1,2，…，s

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

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

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

④取出距當前數(shù)據(jù)塊的聚類中心最近的n0個樣本點存入Xnear中；

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

endfor

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

2.2算法的可行性分析

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

2.3算法復雜度

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

表1　各算法的時間、空間復雜度

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

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

3相關實驗研究

3.1評價指標

為了公正地對各聚類算法的聚類效果做出合理的評價，本文采用如下3種評價指標進行算法的性能分析。

3.1.1算法運行時間的加速比speedup

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

speedup=tfull/tincremental

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

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

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

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

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

3.2實驗結果

1)實驗環(huán)境

本文所有的實驗均在如表2的環(huán)境中進行。

2)實驗數(shù)據(jù)集

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

表2　實驗環(huán)境

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

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

3)實驗參數(shù)設置

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

4)算法性能比較

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

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

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

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

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

表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ù)集上運行時間的加速比比較

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

4結束語

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

參考文獻:

[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]應文豪, 許敏, 王士同, 等. 在大規(guī)模數(shù)據(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年生，碩士研究生，主要研究方向為人工智能與模式識別、模糊聚類算法、增量式學習。

王士同，男，1964年生，教授，博士生導師，中國離散數(shù)學學會常務理事，中國機器學習學會常務理事。主要研究方向為人工智能/模式識別、圖像處理及其應用等。發(fā)表學術論文近百篇，其中被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

作者簡介：

中圖分類號：TP391.4

文獻標志碼：A

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

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

基金項目：國家自然科學基金項目(61272210).

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

DOI:10.11992/tis.201507013

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