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