摘   要： 針對(duì)模糊c-均值（FCM）聚類(lèi)算法受初始聚類(lèi)中心影響，易陷入局部最優(yōu)，以及算法對(duì)孤立點(diǎn)數(shù)據(jù)敏感的問(wèn)題，提出了解決方案：采用快速減法聚類(lèi)算法初始化聚類(lèi)中心，為每個(gè)樣本點(diǎn)賦予一個(gè)定量的權(quán)值，用來(lái)區(qū)分不同的樣本點(diǎn)對(duì)最終的聚類(lèi)結(jié)果的不同作用，為提高聚類(lèi)速度采用修正隸屬度矩陣的方法，并將算法與傳統(tǒng)的FCM相比。實(shí)驗(yàn)結(jié)果表明，該算法較好地解決了初值問(wèn)題，與隨機(jī)初始化方法相比，迭代次數(shù)少、收斂速度快、具有較好的聚類(lèi)結(jié)果。
關(guān)鍵詞： 模糊c-均值； 減法聚類(lèi)； 權(quán)值

    模糊聚類(lèi)作為無(wú)監(jiān)督機(jī)器學(xué)習(xí)的主要技術(shù)之一，廣泛應(yīng)用于數(shù)據(jù)挖掘、矢量量化、圖像分割、模式識(shí)別、醫(yī)學(xué)診斷等領(lǐng)域。引入模糊數(shù)學(xué)方法,通過(guò)建立數(shù)據(jù)樣本類(lèi)屬的不確定描述,將相似性質(zhì)的事物分開(kāi)并加以分類(lèi)，能比較客觀地反映現(xiàn)實(shí)世界。
    模糊c-均值（FCM）算法是模糊聚類(lèi)的基本方法之一，它是一種聚類(lèi)不定歸屬的方法。它通過(guò)引入隸屬度函數(shù)來(lái)表示每個(gè)樣本點(diǎn)屬于各個(gè)類(lèi)別的程度，從而決定樣本點(diǎn)的類(lèi)屬,對(duì)數(shù)據(jù)進(jìn)行軟劃分。
    FCM算法就是通過(guò)搜索目標(biāo)函數(shù)的最小點(diǎn)，反復(fù)修改聚類(lèi)中心矩陣和隸屬度矩陣的分類(lèi)過(guò)程。目前算法的收斂性已得到證明[1]，但它是一種局部搜索算法，對(duì)初值的選取十分敏感，如果初值選取不當(dāng)，它容易收斂到局部極小點(diǎn)。且FCM對(duì)孤立點(diǎn)數(shù)據(jù)、樣本分布不均衡也很敏感。鑒于此，提出基于減法聚類(lèi)的改進(jìn)的模糊c-均值聚類(lèi)，使得算法的收斂速度和準(zhǔn)確性都得以改善。
1 模糊c-均值算法分析


2 基于減法聚類(lèi)的改進(jìn)的模糊c-均值算法
2．1初始聚類(lèi)中心的選擇
    減法聚類(lèi)是一種爬山法，它把所有的樣本點(diǎn)作為聚類(lèi)中心的候選點(diǎn)，其基本思想是計(jì)算每個(gè)樣本點(diǎn)的密度指標(biāo)，如果該樣本點(diǎn)周?chē)狞c(diǎn)多，則密度指標(biāo)就大，就選取密度指標(biāo)最大的樣本點(diǎn)作為聚類(lèi)中心。減法聚類(lèi)是一種快速獨(dú)立的近似的聚類(lèi)方法，用它計(jì)算，計(jì)算量由樣本數(shù)目決定且與樣本點(diǎn)的數(shù)目成簡(jiǎn)單的線性關(guān)系，而且與所考慮問(wèn)題的維數(shù)無(wú)關(guān)。


    (2) 修正隸屬度矩陣
    FCM算法的思想是：迭代調(diào)整隸屬矩陣和聚類(lèi)中心使目標(biāo)函數(shù)值最小,為保證FCM算法每次的迭代都朝著全局最優(yōu)的方向逼近，其關(guān)鍵就在于保證確定V的下一次迭代值，加快收斂于全局最優(yōu)點(diǎn)的速度。在此采用修正隸屬矩陣來(lái)計(jì)算下一次迭代的聚類(lèi)中心，使得到的V更靠近聚類(lèi)中心，更合理，從而提高FCM算法的收斂速度。因此修正隸屬度矩陣[5]可以提高聚類(lèi)速度，使聚類(lèi)效果更好。
    樣本離聚類(lèi)中心距離越遠(yuǎn)屬于該聚類(lèi)中心的程度越小，反之越大，樣本對(duì)類(lèi)中心的影響即稱(chēng)為樣本對(duì)類(lèi)中心施加的吸引力，在這里設(shè)定了一個(gè)抑制因子，由它來(lái)控制對(duì)離樣本點(diǎn)次最近的類(lèi)中心的抑制作用。
    當(dāng)α＝１時(shí)，算法退化為FCM算法，對(duì)離樣本點(diǎn)次最近的類(lèi)中心沒(méi)有任何抑制作用。
    當(dāng)α=0時(shí)，算法完全抑制了樣本對(duì)離它次最近類(lèi)中心的吸引力，對(duì)離樣本最近類(lèi)中心的吸引力的增強(qiáng)力度最大。
    當(dāng)1<α<0時(shí)，算法對(duì)離樣本次最近類(lèi)中心的吸引力有一定的抑制作用，對(duì)離樣本最近類(lèi)中心的吸引力有一定的增加作用。
    修正隸屬度矩陣的過(guò)程如下：
  
    (5) 判斷是否終止迭代。終止而退出，否則，L=L+1，返回步驟(２)，繼續(xù)迭代。
    經(jīng)過(guò)對(duì)隸屬度矩陣的修正可知：改進(jìn)后的算法，樣本點(diǎn)增大了對(duì)離它最近的類(lèi)中心的吸引力強(qiáng)度；樣本點(diǎn)減小了對(duì)離它次最近的類(lèi)中心的吸引力強(qiáng)度，從而減弱了離樣本次最近類(lèi)中心對(duì)離樣本最近的類(lèi)中心收斂速度的延緩作用。對(duì)其余類(lèi)中心的吸引力強(qiáng)度不變，從而提升了FCM算法的收斂速度。
2．3 基于減法聚類(lèi)改進(jìn)的模糊c-均值算法過(guò)程
    為保證改進(jìn)的FCM聚類(lèi)結(jié)果為全局最優(yōu)解，采用減法聚類(lèi)的聚類(lèi)中心作為改進(jìn)的FCM聚類(lèi)的初始聚類(lèi)中心。算法步驟如下：
    (1) 設(shè)定聚類(lèi)參數(shù):領(lǐng)域的半徑ra、rb,比例參數(shù)δ，F(xiàn)CM聚類(lèi)數(shù)c,模糊指數(shù)m和最小誤差ε,迭代次數(shù)L,吸引力抑制因子α。
    (2) 應(yīng)用式(4)計(jì)算所有樣本點(diǎn)的密度指標(biāo)，將密度指標(biāo)最高的一個(gè)作為第一個(gè)聚類(lèi)中心點(diǎn)xc1。
    (3) 依據(jù)公式(5)利用減法步驟(2)中的xc1進(jìn)一步計(jì)算余下的n-1個(gè)數(shù)據(jù)點(diǎn)的密度指標(biāo)，找出最高的作為第二個(gè)聚類(lèi)中心xc2，依此類(lèi)推，找到p個(gè)聚類(lèi)中心，從中選取前c個(gè)作為FCM的初始聚類(lèi)中心v(0)。
    減法聚類(lèi)中心中，密度指標(biāo)越大的聚類(lèi)中心出現(xiàn)得越早，越有可能成為改進(jìn)的FCM初始聚類(lèi)中心。所以，當(dāng)聚類(lèi)數(shù)為c時(shí)，取減法聚類(lèi)產(chǎn)生的前c個(gè)聚類(lèi)中心作為改進(jìn)的FCM的初始中心，無(wú)須再重新初始化，從而提高了聚類(lèi)的效率。
    (4) 求式(10)的最小值
    (5) 按式(11)和式(12)計(jì)算出隸屬度U(L)
    (6) 依據(jù)式(13)和式(14)修正隸屬度矩陣U(L)。
    (7) 依據(jù)式(15)，用修正后的U(L)計(jì)算下一次的迭代中心V(L+1)。
    (8) 判斷是否滿足終止迭代條件。對(duì)給定的閾值，
‖U(L+1)-U(L)‖<ε如果終止而退出，否則，L=L+1，返回步驟(5)，繼續(xù)迭代。
3 仿真與結(jié)果分析

    從圖1、圖2與表1中可以看出,傳統(tǒng)FCM與本文中的算法相比迭代次數(shù)少、搜索速度更快、聚類(lèi)平均準(zhǔn)確率更高。

    基于減法聚類(lèi)的改進(jìn)的FCM算法很好地解決了FCM算法對(duì)初始值敏感及易陷入局部最優(yōu)的問(wèn)題，同時(shí)也改善了FCM對(duì)孤立點(diǎn)敏感的問(wèn)題，提高了聚類(lèi)的速度，具有很高的實(shí)用價(jià)值。
參考文獻(xiàn)
[1]  GAMES R A, CHAN A H. A fast algorithm for determining the linear complexity of a pseudorandom sequence with period 2n[J].IEEE Trans Inf Theory ,1983,IT-29(1):144-146.
[2]  HAND D, MANNILA H, SMYTH P. Principles of data mining [M].Cambridge MA:MITPress,2001.
[3]  PAL N R, CHAKRABORTY D. Mountain and subtractive clustering method; Improvements and Generalization. International Journal of Intelligent Systems , 2000,15 (4):329-341.
[4]  齊淼，張化祥.改進(jìn)的模糊c-均值聚類(lèi)算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(20).
[5]  閆兆振.自適應(yīng)模糊c-均值聚類(lèi)算法研究[D]. 濟(jì)南：山東科技大學(xué),2006.