于 迪，李義杰

(1.遼寧工程技術(shù)大學(xué) 研究生學(xué)院，遼寧 葫蘆島 125105;

(2.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105）

模糊聚類作為無監(jiān)督機(jī)器學(xué)習(xí)的主要技術(shù)之一，廣泛應(yīng)用于數(shù)據(jù)挖掘、矢量量化、圖像分割、模式識別、醫(yī)學(xué)診斷等領(lǐng)域。引入模糊數(shù)學(xué)方法,通過建立數(shù)據(jù)樣本類屬的不確定描述,將相似性質(zhì)的事物分開并加以分類，能比較客觀地反映現(xiàn)實世界。

模糊c-均值（FCM）算法是模糊聚類的基本方法之一，它是一種聚類不定歸屬的方法。它通過引入隸屬度函數(shù)來表示每個樣本點屬于各個類別的程度，從而決定樣本點的類屬,對數(shù)據(jù)進(jìn)行軟劃分。

FCM算法就是通過搜索目標(biāo)函數(shù)的最小點，反復(fù)修改聚類中心矩陣和隸屬度矩陣的分類過程。目前算法的收斂性已得到證明[1]，但它是一種局部搜索算法，對初值的選取十分敏感，如果初值選取不當(dāng)，它容易收斂到局部極小點。且FCM對孤立點數(shù)據(jù)、樣本分布不均衡也很敏感。鑒于此，提出基于減法聚類的改進(jìn)的模糊c-均值聚類，使得算法的收斂速度和準(zhǔn)確性都得以改善。

1模糊c-均值算法分析

設(shè)樣本空間為X={x1,x2,…,xn}，其中每個元素包含 s個屬性。模糊聚類就是將x劃分為c類，c個聚類中心為v={v1,v2,…,vc}。uij是樣本空間X中的第 j個元素對第i個類中心的隸屬度。dij=‖vi-xj‖是第 i個聚類中心與第j個數(shù)據(jù)點之間的歐幾里德距離，在FCM聚類算法中，隸屬度矩陣和聚類中心分別為U={uij}和V={vi},FCM算法的目標(biāo)函數(shù)為：

2基于減法聚類的改進(jìn)的模糊c-均值算法

2．1初始聚類中心的選擇

減法聚類是一種爬山法，它把所有的樣本點作為聚類中心的候選點，其基本思想是計算每個樣本點的密度指標(biāo)，如果該樣本點周圍的點多，則密度指標(biāo)就大，就選取密度指標(biāo)最大的樣本點作為聚類中心。減法聚類是一種快速獨立的近似的聚類方法，用它計算，計算量由樣本數(shù)目決定且與樣本點的數(shù)目成簡單的線性關(guān)系，而且與所考慮問題的維數(shù)無關(guān)。

M維空間的 n個樣本點 xi(i=1,2,…,n)全部都為聚類中心的候選點，定義樣本點xi處密度指標(biāo)為：

減法聚類的過程如下：

(1)用式(4)計算每個樣本點 xi的密度指標(biāo)，選擇具有最高密度指標(biāo)的數(shù)據(jù)點xc1作為第一個聚類中心，Dc1為其密度指標(biāo)。其中ra是一個正數(shù)，定義了該點的領(lǐng)域半徑，半徑以外的數(shù)據(jù)點對該點的密度指標(biāo)貢獻(xiàn)非常小，這里取：

(2)令xci為第 i次選出的聚類中心，Dci為其密度指標(biāo)，則其他樣本點的密度指標(biāo)可用式(5)修正。選出密度指標(biāo)最高的數(shù)據(jù)點xci+1作為新的聚類中心。其中rb是一個正數(shù)，定義了一個密度指標(biāo)函數(shù)顯著減小的領(lǐng)域，這里取 rb=1.2ra。

判斷式(6)是否成立，若不成立，則轉(zhuǎn)到步驟(2)；若成立則退出。預(yù)先給定參數(shù)δ、ra、rb。δ決定了最終產(chǎn)生的初始聚類中心數(shù)目，δ越小，產(chǎn)生的聚類數(shù)越多;反之則聚類數(shù)越少。ra，rb越大，產(chǎn)生的類數(shù)就越少，反之，則產(chǎn)生的類數(shù)就越多。

2.2改進(jìn)的FCM算法

(1)為樣本加權(quán)

樣本空間為X={x1,x2,…,xn},每個樣本點對于分類結(jié)果來說貢獻(xiàn)是不同的，例如樣本空間中，孤立點就是對分類不重要的樣本點，F(xiàn)CM算法對于這一點不敏感。因此為了區(qū)分各個樣本點的不同之處，給每個樣本點賦予一個權(quán)值 wi[4]。

則計算聚類中心的公式變?yōu)椋?/p>

其中 d(xi,xj)表示兩個樣本點 xi與 xj之間的歐式距離，d(xi,xj)的值越接近0則表示xi與xj之間越相似或越接近，則權(quán)重wi越大；反之,xi,xj差異性越大或越遠(yuǎn),則權(quán)重wi越小。如果樣本點周圍的點越多，則它的權(quán)重越大，因此可以用權(quán)重wi表示第i個樣本xi對分類的影響程度。由于算法中噪聲和孤立點的權(quán)重比較小，這樣就能消除它們的影響。為樣本加權(quán)后目標(biāo)函數(shù)為：

(2)修正隸屬度矩陣

FCM算法的思想是：迭代調(diào)整隸屬矩陣和聚類中心使目標(biāo)函數(shù)值最小,為保證FCM算法每次的迭代都朝著全局最優(yōu)的方向逼近，其關(guān)鍵就在于保證確定V的下一次迭代值，加快收斂于全局最優(yōu)點的速度。在此采用修正隸屬矩陣來計算下一次迭代的聚類中心，使得到的V更靠近聚類中心，更合理，從而提高FCM算法的收斂速度。因此修正隸屬度矩陣[5]可以提高聚類速度，使聚類效果更好。

樣本離聚類中心距離越遠(yuǎn)屬于該聚類中心的程度越小，反之越大，樣本對類中心的影響即稱為樣本對類中心施加的吸引力，在這里設(shè)定了一個抑制因子，由它來控制對離樣本點次最近的類中心的抑制作用。

當(dāng)α＝1時，算法退化為 FCM算法，對離樣本點次最近的類中心沒有任何抑制作用。

當(dāng)α=0時，算法完全抑制了樣本對離它次最近類中心的吸引力，對離樣本最近類中心的吸引力的增強力度最大。

當(dāng)1＜α＜0時，算法對離樣本次最近類中心的吸引力有一定的抑制作用，對離樣本最近類中心的吸引力有一定的增加作用。

修正隸屬度矩陣的過程如下：

(1)初始化類中心為V(0)。迭代次數(shù)L=0給定模糊指數(shù)m，m∈(1，∞)置吸引力抑制因子α(即樣本點對離它最近的類的吸引力)，α∈[0，1]。

(2)計算出 U(L)：

當(dāng) Ij＝φ 時；

當(dāng) Ij≠φ 時,?i∈Ij，uij=0,

(3)修正隸屬度矩陣 U(L)：假設(shè)樣本 xi對第 q類的隸屬度最大，值為uqi;它對第s類的隸屬度次最大，值為usi。

對其進(jìn)行修正后，樣本xi對第q類的隸屬度為：

對第s類的隸屬度為：

除此之外各類的隸屬度不變。

(4)用修正后的U(L)計算下一次的迭代中心V(L+1)(加 權(quán) 后 的 Vi)。

(5)判斷是否終止迭代。終止而退出，否則，L=L+1，返回步驟(2)，繼續(xù)迭代。

經(jīng)過對隸屬度矩陣的修正可知：改進(jìn)后的算法，樣本點增大了對離它最近的類中心的吸引力強度；樣本點減小了對離它次最近的類中心的吸引力強度，從而減弱了離樣本次最近類中心對離樣本最近的類中心收斂速度的延緩作用。對其余類中心的吸引力強度不變，從而提升了FCM算法的收斂速度。

2．3基于減法聚類改進(jìn)的模糊c-均值算法過程

為保證改進(jìn)的FCM聚類結(jié)果為全局最優(yōu)解，采用減法聚類的聚類中心作為改進(jìn)的FCM聚類的初始聚類中心。算法步驟如下：

(1)設(shè)定聚類參數(shù)：領(lǐng)域的半徑 ra、rb,比例參數(shù) δ，F(xiàn)CM聚類數(shù)c,模糊指數(shù)m和最小誤差ε,迭代次數(shù)L,吸引力抑制因子α。

(2)應(yīng)用式(4)計算所有樣本點的密度指標(biāo)，將密度指標(biāo)最高的一個作為第一個聚類中心點xc1。

(3)依據(jù)公式(5)利用減法步驟(2)中的 xc1進(jìn)一步計算余下的n-1個數(shù)據(jù)點的密度指標(biāo)，找出最高的作為第二個聚類中心xc2，依此類推，找到 p個聚類中心，從中選取前c個作為FCM的初始聚類中心v(0)。

減法聚類中心中，密度指標(biāo)越大的聚類中心出現(xiàn)得越早，越有可能成為改進(jìn)的FCM初始聚類中心。所以，當(dāng)聚類數(shù)為c時，取減法聚類產(chǎn)生的前c個聚類中心作為改進(jìn)的FCM的初始中心，無須再重新初始化，從而提高了聚類的效率。

(4)求式(10)的最小值

(5)按式(11)和式(12)計算出隸屬度U(L)

(6)依據(jù)式(13)和式(14)修正隸屬度矩陣 U(L)。

(7)依據(jù)式(15)，用修正后的 U(L)計算下一次的迭代中心 V(L+1)。

(8)判斷是否滿足終止迭代條件。對給定的閾值，‖U(L+1)-U(L)‖＜ε如果終止而退出，否則，L=L+1，返回步驟(5)，繼續(xù)迭代。

3仿真與結(jié)果分析

為驗證基于減法聚類的改進(jìn)的FCM算法的效果，利用Iris植物樣本數(shù)據(jù)進(jìn)行仿真實驗,將結(jié)果與傳統(tǒng)FCM進(jìn)行對比。Iris數(shù)據(jù)集是公認(rèn)的最適用于數(shù)據(jù)挖掘的數(shù)據(jù)集，它有四個屬性、三種植物種類(setosa、versicolor、virginica),每個種類含有50個樣本。Iris的實際中心分別為(6.588、2.974、5.552、2..026)、(5.006、3.418、1.464、0.244）、(5.936、2.77、4.26、1.326)。分別用傳統(tǒng)的 FCM 和基于減法聚類的改進(jìn)的FCM對Iris數(shù)據(jù)集進(jìn)行聚類分析。實驗中，設(shè)定允許最小誤差ε均為10-3,模糊指數(shù)m=2，ra=0.5,rb=0.6,α=0,Iris數(shù)據(jù)集的聚類結(jié)果如圖 1、圖 2所示。Iris數(shù)據(jù)集的比較如表1所示。

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

圖1兩種算法收斂速度的比較

基于減法聚類的改進(jìn)的FCM算法很好地解決了FCM算法對初始值敏感及易陷入局部最優(yōu)的問題，同時也改善了FCM對孤立點敏感的問題，提高了聚類的速度，具有很高的實用價值。

表1 Iris數(shù)據(jù)集的性能比較

[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-均值聚類算法研究[J].計算機(jī)工程與應(yīng)用,2009,45(20).

[5]閆兆振.自適應(yīng)模糊c-均值聚類算法研究[D].濟(jì)南：山東科技大學(xué),2006.