曹 易， 張 寧

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

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

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

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

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

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

目標函數(shù)定義為

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

2 改進的模糊C-均值的算法及其實現(xiàn)

2.1 聚類數(shù)和初始聚類中心選取的改進

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

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

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

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

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

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

2.2 隸屬度的改進

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

其余對象的隸屬度不變.

2.3 目標函數(shù)選取的改進

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

類內(nèi)差異W（u，v，c）和類間差異B（u，v，c）分別為

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

2.4 模糊C-均值算法改進的具體實現(xiàn)

綜上所述，現(xiàn)給出該算法的具體步驟.

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

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

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

Step 4 更新聚類中心vi.

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

3 實驗結果及分析

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

經(jīng)調整實驗控制參數(shù)得出結果如圖1～4所示.

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

從圖1～4可以看出：

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

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

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

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

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

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

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

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

4 結 論

通過分析經(jīng)典的FCM算法中的局限性，例如聚類結果對聚類數(shù)和初始聚類中心的敏感性，以及目標函數(shù)選取只考慮類內(nèi)部距離而忽略了類間距離，提出了一種改進的FCM算法.經(jīng)實驗證明，與經(jīng)典算法相比，改進算法不論是在聚類質量上還是在算法復雜度上，都有一定程度的提高.用概率密度函數(shù)找到最佳的聚類數(shù)以及初始聚類中心點；利用競爭學習算法中的抑制對手來修改隸屬矩陣，從而達到加快算法的收斂速度；用一個類內(nèi)距離與類間距離兼顧的新目標函數(shù)替換原有目標函數(shù).實驗證明，本文算法在參數(shù)設置合理的情況下，聚類質量和算法速度在原有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］ 賀玲，吳玲達，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述.計算機應用研究，2007，1（1）：16－19.

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

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

［5］ Yager R R，F(xiàn)ilev 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－均值聚類算法中的加權指數(shù)m的研究［J］.電子學報，2000，28（4）：80－83.

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

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

［11］ 張曙紅，孫建勛，諸克軍.基于遺傳優(yōu)化的采樣模糊C－均值聚類算法［J］.系統(tǒng)工程理論與實踐，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.