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