一種改進的模糊C-均值聚類算法

曹 易， 張 寧

（上海理工大學管理學院，上海 200093）

聚類是根據對象之間的相似性來將他們聚集成不同類別的方法.評價一個聚類質量的好壞，總體是該聚類結果中同一類內部的對象盡可能相似，不同類之間的對象盡可能相異.到目前為止，數據挖掘中常用的聚類算法有層次聚類、劃分聚類、基于網格聚類、基于密度聚類及模糊聚類等［1］.

傳統的聚類是一種硬性劃分，具有“非此即彼”性，但是，現實生活中很多事物是“亦此亦彼”，很難將它們嚴格地劃分到一個具體的類中.模糊C－均值聚類算法（FCM）是應用最廣泛的聚類算法之一［2］，它具有算法簡單、收斂速度快、能處理大規模數據等優點，因此，該算法已經有效地應用在數據挖掘、模式識別及決策支持等領域，具有很大的理論以及實踐價值.但是，FCM算法同時也存在著很大的局限性［3］：聚類數與聚類初始中心的選擇極大地影響著聚類效果，并且該算法采用梯度法求解極值，所求解往往是局部最優.為此，文獻［4］用信息熵來計算最佳聚類數目，Yager和Filev［5］提出了一種稱為爬山法的初始聚類中心方法.

由于一般模糊C－均值算法的上述缺點，本文提出了一種改進的FCM算法.首先用概率密度的思想得到最佳聚類數和初始聚類中心，其次通過對擁有次大隸屬度的中心點加入一個抑制因子來加速算法收斂，最后用一個兼顧類內距與類間距的新的目標函數來替代原有的目標函數.經實驗證實，該算法在聚類結果質量與算法速度上都有了一定程度的改進.

1 普通模糊C-均值的算法

設X＝｛x1，x2，…，xn｝是待聚類的對象的全體（論域），X中每個對象（樣本）xk（k＝1，2，…，n）可以用有限個參數值來描述，每個參數刻畫xkj的某個特征.所以，對象xk就可以用一個向量P（xk）＝（xk1，xk2，…，xks）來表示，P（xk）為xk的特征向量［6］.uik表示X中第k個對象對第i類的隸屬度函數，vi（i＝1，2，…，c）表示聚類中心，則第k個對象到第i個聚類中心vi的歐式距離為

目標函數定義為

隨著隸屬函數uik和中心點vi不斷更新，若目標函數Jm（U，V，c）達到了滿意的穩定程度，就終止迭代算法.

2 改進的模糊C-均值的算法及其實現

2.1 聚類數和初始聚類中心選取的改進

上述算法具有簡單、收斂速度快、能處理大規模數據等優點，但是，聚類數和聚類初始中心的選擇極大地影響著聚類效果，并且該算法采用梯度法求解極值，所求解往往是局部最優.

目前，在FCM算法中，聚類數和初始中心點的選擇對算法的復雜度以及聚類效果的影響相當大，因此，選擇一個適合的中心點是至關重要的.本文利用一種概率密度函數來選擇聚類數和初始中心［9，10］.定義對象xi處的密度函數為

其中，rd為鄰域半徑，其數值與數據的分布特性有關.

本文取rd為n個對象的平均距離，即

顯然，xi周圍分布越密集，rd值越小，密度函數值越大.令其滿足條件的點取為第一個初始聚類中心，設為x＊1.第k個聚類中心點為

第k次迭代時的聚類中心的密度函數為

2.2 隸屬度的改進

由FCM算法可知，聚類實際上就是一個隸屬矩陣u和聚類中心v交替優化過程.可以修正隸屬矩陣u來計算下一次迭代的聚類中心v，使計算結果更合理，提高算法的收斂速度.隸屬度越大，樣本點對類中心的吸引力就越大，類中心的下一次迭代值受隸屬度的影響就越大［11］.本文根據競爭學習算法，給出了一種修正隸屬矩陣u的算法.本文稱距離樣本點最近的類中心為贏者，距離次近的為贏者對手，通過減弱對手的吸引力來加快贏者的收斂速度.加入一個抑制因子α∈［0，1］，抑制次近樣本點的吸引力，來加快算法收斂速度.具體描述為：對于對象xj，假如它對第t類的隸屬度最大，為utj；對第s類的隸屬度次大，為usj.給定抑制因子α，根據式（6）修改隸屬度為

其余對象的隸屬度不變.

2.3 目標函數選取的改進

聚類結果應該是類內盡可能緊湊，類間盡可能疏遠.但是，傳統的FCM算法的目標函數只考慮了類內距離，沒有重視類間距離.本文根據Xie－Beni提出的聚類有效性指標［12］，給出一種兼顧類內和類間距離的有效性指標，將它作為新的目標函數.

類內差異W（u，v，c）和類間差異B（u，v，c）分別為

將W（u，v，c）和B（u，v，c）的商作為新的目標函數Jm（u，v，c），即

2.4 模糊C-均值算法改進的具體實現

綜上所述，現給出該算法的具體步驟.

Step 1 給定待聚類對象集X，參數δ，模糊因子m，抑制因子α，迭代參數ε.

Step 2 根據式（3）～（5）求出初始聚類數c和聚類中心v.

Step 3 計算隸屬矩陣uik，再根據式（6）修改u.

Step 4 更新聚類中心vi.

Step 5 根據式（9）計算Jm（u，v，c），若式（12）成立，終止計算；否則，l＝l＋1，轉向Step 3.

3 實驗結果及分析

通過實驗來測試改進算法的效率和聚類質量，并與普通的模糊C－均值算法進行比較.本次實驗平臺操作系統為Windows XP，CPU為雙核E7500 2.9GHz，內存2GB.數據采用某高校的Web訪問日志，共有2 993個IP用戶，訪問的網頁被綜合成了教育、娛樂、搜索等35個類別，每個類別認為是用戶的一個屬性值，大小取該用戶對該類別的訪問頻率，得到了2 993×35的用戶類別矩陣.實驗取模糊因子m值為2，最大可能迭代次數為200，通過改變參數δ，α和ε的值來測試算法的性能，得到參數的最佳取值范圍.聚類結果的有效性指標p［13］用式（13）來評價，值越小，則聚類效果越好；反之亦然.N為算法迭代次數.

經調整實驗控制參數得出結果如圖1～4所示.

圖1 聚類有效性p和迭代次數N與α的關系Fig.1 Relationship of clustering validity p，iteration number Nandα

從圖1～4可以看出：

a.當m＝2，δ＝0.5，ε＝0.001時，隨著參數α從0變化到1時，有效性指標p與迭代次數N的變化趨勢如圖1，綜合考慮該算法的聚類質量以及迭代次數，取α＝0.3較為合理.

b.在圖2中，當m＝2，α＝0.3，ε＝0.001時，隨著參數δ從0變化到1時，有效性指標p，迭代次數N以及聚類數c變化趨勢如圖2（見下頁），同樣綜合考慮該算法，取δ＝0.5較為合理，此時聚類數c＝43.

c.當m＝2，α＝0.3，δ＝0.5時，隨著參數ε從0.000 5～0.001 4之間變化時，有效性指標p與迭代次數N的變化趨勢如圖3（見下頁），同樣綜合考慮該算法，取ε＝0.001較為合理.

d.取m＝2，α＝0.3，δ＝0.5，ε＝0.001時，用本文的改進FCM算法與經典的FCM算法進行比較，從圖4（見下頁）中可以看出，當聚類數目相同時，與經典FCM算法相比，本文算法在有效性指標p與迭代次數N上均有一定程度的提高.

綜上所述，本文提出的改進FCM算法中，通過調節參數α，δ，ε的大小，其中本文的數據中α＝0.3、δ＝0.5、ε＝0.001，較原有的FCM算法在聚類質量和算法速度有一定程度的提高.

圖2 聚類有效性p，迭代次數N及聚類數c與δ的關系Fig.2 Relationship of clustering validity p，iteration number N，cluster number c andα

圖3 聚類有效性p和迭代次數N與ε的關系Fig.3 Relationship of clustering validity p，iteration number Nandε

圖4 改進的FCM算法與經典FCM算法比較Fig.4 Comparison of the improved FCM and classical FCM algorithm

4 結 論

通過分析經典的FCM算法中的局限性，例如聚類結果對聚類數和初始聚類中心的敏感性，以及目標函數選取只考慮類內部距離而忽略了類間距離，提出了一種改進的FCM算法.經實驗證明，與經典算法相比，改進算法不論是在聚類質量上還是在算法復雜度上，都有一定程度的提高.用概率密度函數找到最佳的聚類數以及初始聚類中心點；利用競爭學習算法中的抑制對手來修改隸屬矩陣，從而達到加快算法的收斂速度；用一個類內距離與類間距離兼顧的新目標函數替換原有目標函數.實驗證明，本文算法在參數設置合理的情況下，聚類質量和算法速度在原有FCM算法上有一定程度的提高.

［1］ Mitra S，Pal S K，Mitra P.Data mining in soft computing framework：a survey［J］.IEEE Transactions on Neural Networks，2002，13（1）：3－14.

［2］ 賀玲，吳玲達，蔡益朝.數據挖掘中的聚類算法綜述.計算機應用研究，2007，1（1）：16－19.

［3］ 齊淼，張化祥.改進的模糊C－均值聚類算法研究.計算機工程與應用，2009，45（20）：133－135.

［4］ 沈紅斌，楊杰，王士同，等.基于信息理論的合作聚類算法研究［J］.計算機學報，2005，28（8）：1287－1294.

［5］ Yager R R，Filev D P.Approximate clustering via the mountain method［J］.IEEE Transactions on SMC，1994，24（8）：1279－1284.

［6］ 張敏，于劍.基于劃分的模糊聚類算法［J］.軟件學報，2004，15（6）：858－868.

［7］ 朱文婕，吳楠，胡學鋼.一個改進的模糊聚類有效性指標［J］.計算機工程與應用2011，47（5）：206－209.

［8］ 高新波，裴繼紅，謝維信.模糊C－均值聚類算法中的加權指數m的研究［J］.電子學報，2000，28（4）：80－83.

［9］ 饒泓，扶名福，謝明詳.基于模糊聚類的神經網絡故障診斷方法［J］.微計算機信息，2007，1（1）：196－197.

［10］ 李春生，王耀南.聚類中心初始化的新方法［J］.控制理論與應用，2010，27（10）：1435－1440.

［11］ 張曙紅，孫建勛，諸克軍.基于遺傳優化的采樣模糊C－均值聚類算法［J］.系統工程理論與實踐，2004，5（1）：121－125.

［12］ Xie X L，Beni G.A validity measure for fuzzy clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（8）：841－847.

［13］ Kwon S H.Cluster Validity index of fuzzy clustering［J］.Electronics Letters，1998，34（22）：2176－2177.