基于Fuzzy c一meads的高效自適應(yīng)截集算法
加入技術(shù)交流群
掃碼加入
和技術(shù)大咖面對(duì)面交流
海量資料庫(kù)查詢(xún)
1 引 言
聚類(lèi)在統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域得到了廣泛的研究[1]。
在實(shí)際問(wèn)題中，樣本量可能非常大，這就無(wú)法有效地確定聚類(lèi)數(shù)目，采用fcm對(duì)大樣本聚類(lèi)時(shí)將耗費(fèi)大量的空間及時(shí)間，且有時(shí)會(huì)收斂到局部極小點(diǎn)上，fcm算法的缺點(diǎn)限制了人們對(duì)他的使用[2]。本文針對(duì)fcm算法存在的不足，在算法結(jié)構(gòu)上進(jìn)行了具體的改進(jìn)。該方法以最大隸屬度原則為指導(dǎo)，利用對(duì)聚類(lèi)的有效性函數(shù)分析，提出了自適應(yīng)截集fcm算法(s2afcm算法)，在保持模糊聚類(lèi)優(yōu)點(diǎn)的同時(shí)，提高了收斂速度，并能自適應(yīng)地確定聚類(lèi)中心的個(gè)數(shù)，可以避免在聚類(lèi)數(shù)目的選取上存在的主觀性。另一方面，在分類(lèi)識(shí)別問(wèn)題中，給出了正確分類(lèi)和拒識(shí)的樣本特征，提高了分類(lèi)識(shí)別的正確性。
2 自適應(yīng)截集算法
模糊聚類(lèi)是無(wú)監(jiān)督模式識(shí)別的一個(gè)重要分支[4]。在眾多的聚類(lèi)算法中，模糊c均值算法(fuzzy c-means)也是為人們熟悉的方法之一。
由于fcm算法要求聚類(lèi)類(lèi)別數(shù)c的先驗(yàn)知識(shí)，而關(guān)于數(shù)據(jù)的空間分布及結(jié)構(gòu)的先驗(yàn)知識(shí)是很少有的，或者一點(diǎn)也沒(méi)有，因此這一要求限制了fcm類(lèi)型算法的實(shí)際應(yīng)用，這就要求聚類(lèi)分析中還需要研究聚類(lèi)結(jié)果的有效性，以判決算法識(shí)別出的聚類(lèi)是否真實(shí)。
本文所提出的自適應(yīng)截集聚類(lèi)方法是在xie-beni方法[5]上發(fā)展起來(lái)的，這里首先定義了聚類(lèi)的緊密性：
模糊聚類(lèi)的有效性函數(shù)s被定義為模糊聚類(lèi)的緊密性與分離性之比，即：s-comp／sep。
本文針對(duì)fcm算法上存在的不足，在算法結(jié)構(gòu)上進(jìn)行了具體的改進(jìn)，增加了聚類(lèi)有效性函數(shù)的分析，解決了fcm算法中初值選擇問(wèn)題，動(dòng)態(tài)確定聚類(lèi)中心的個(gè)數(shù)，可以克服主觀性。
另外，使用模糊截集，在保持模糊聚類(lèi)優(yōu)點(diǎn)的同時(shí)，提高了收斂速度。
3 實(shí)驗(yàn)及分析使用sendmail系統(tǒng)調(diào)用序列進(jìn)行仿真實(shí)驗(yàn)，主要比較2種算法的聚類(lèi)效果和運(yùn)行的效率。在完成了數(shù)據(jù)預(yù)處理之后[6]，依據(jù)對(duì)算法事先的假設(shè)，算法應(yīng)該能夠自動(dòng)地對(duì)分類(lèi)數(shù)c進(jìn)行選擇。那么實(shí)驗(yàn)所得到的結(jié)果應(yīng)該好于模糊c均值算法。為了證明這一結(jié)論，分別用2種算法對(duì)同一數(shù)據(jù)集進(jìn)行聚類(lèi)并做圖(圖2，圖3)比較，然后討論。
以上兩圖分別是fcm算法和自適應(yīng)截集算法對(duì)同一批數(shù)據(jù)進(jìn)行聚類(lèi)的效果圖。在兩幅效果圖中，聚類(lèi)中心并不在同一位置，而是有著明顯差異，而且聚類(lèi)中心的數(shù)目不同。產(chǎn)生這樣的結(jié)果，其根本原因是由于算法的不同而造成的。在圖2的中是硬性規(guī)定模糊c均值算法把數(shù)據(jù)集分為2類(lèi)，而自適應(yīng)截集fcm算法是自適應(yīng)地將數(shù)據(jù)集分為4類(lèi)，因而產(chǎn)生了上述結(jié)果。而且，通過(guò)直觀的觀察，比較數(shù)據(jù)與聚類(lèi)中心的距離，顯然，自適應(yīng)截集算法的聚類(lèi)結(jié)果更具有合理性，并且方便進(jìn)行進(jìn)一步的處理。
為了進(jìn)一步比較2種算法之間的不同，在表1中用一組共有125個(gè)樣本的向量進(jìn)行實(shí)驗(yàn)給出2種算法的聚類(lèi)中心和運(yùn)行時(shí)間的比較。然后，再給出一個(gè)共有501個(gè)樣本的數(shù)據(jù)集再做一次比較，從2個(gè)表的對(duì)比中可以看出，自適應(yīng)截集算法的運(yùn)行時(shí)間大于fcm算法的運(yùn)行時(shí)間(單位：s)。從圖1中可以得到，這是由于本算法要多次迭代尋找合適的聚類(lèi)數(shù)c所消耗的時(shí)間，這種消耗換來(lái)了聚類(lèi)的精確性，能夠得到一個(gè)更合理的分類(lèi)數(shù)。
在算法的運(yùn)行效率上，s2afcm算法的時(shí)間復(fù)雜度增高了，但是當(dāng)數(shù)據(jù)量增大時(shí)，如圖4所示，s2afcm算法的時(shí)間增長(zhǎng)速度卻小于fcm算法。
由s2afcm得到的樣本隸屬度矩陣，既具有一定的明晰性，又保持了樣本在空間分布的模糊性。這種劃分特性對(duì)聚類(lèi)以后的識(shí)別處理很有好處，一方面他減小了由模糊劃分所引起的對(duì)樣本進(jìn)行進(jìn)一步劃分所需的工作量，另一方面他給出了樣本空間中那些與原型的相對(duì)距離較接近的樣本的模糊屬性(隸屬度)，以便更高層的決策機(jī)構(gòu)識(shí)別或拒識(shí)，提高分類(lèi)識(shí)別的正確性。
4 結(jié) 語(yǔ)
在實(shí)驗(yàn)中，可以得到一個(gè)好的聚類(lèi)效果。雖然應(yīng)用了模糊截集來(lái)提高收斂速度，但算法的運(yùn)行效率并不能使人滿(mǎn)意。通過(guò)算法流程圖，可以看出算法消耗的時(shí)間主要是在聚類(lèi)有效性的求取上，如何優(yōu)化聚類(lèi)有效性函數(shù)，以縮短算法運(yùn)行時(shí)間是將來(lái)著重要做的工作。
評(píng)論