曹 易， 張 寧

（上海理工大學(xué)管理學(xué)院，上海 200093）

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

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

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

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

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

目標(biāo)函數(shù)定義為

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

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

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

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

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

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

本文取rd為n個(gè)對(duì)象的平均距離，即

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

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

2.2 隸屬度的改進(jìn)

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

其余對(duì)象的隸屬度不變.

2.3 目標(biāo)函數(shù)選取的改進(jìn)

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

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

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

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

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

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

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

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

Step 4 更新聚類中心vi.

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

3 實(shí)驗(yàn)結(jié)果及分析

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

經(jīng)調(diào)整實(shí)驗(yàn)控制參數(shù)得出結(jié)果如圖1～4所示.

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

從圖1～4可以看出：

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

［4］ 沈紅斌，楊杰，王士同，等.基于信息理論的合作聚類算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，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］.軟件學(xué)報(bào)，2004，15（6）：858－868.

［7］ 朱文婕，吳楠，胡學(xué)鋼.一個(gè)改進(jìn)的模糊聚類有效性指標(biāo)［J］.計(jì)算機(jī)工程與應(yīng)用2011，47（5）：206－209.

［8］ 高新波，裴繼紅，謝維信.模糊C－均值聚類算法中的加權(quán)指數(shù)m的研究［J］.電子學(xué)報(bào)，2000，28（4）：80－83.

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

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

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