基于減法聚類改進的模糊c-均值算法的模糊聚類研究*

于 迪，李義杰

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

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

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

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

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

1模糊c-均值算法分析

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

2基于減法聚類的改進的模糊c-均值算法

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

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

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

減法聚類的過程如下：

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

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

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

2.2改進的FCM算法

(1)為樣本加權

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

則計算聚類中心的公式變為：

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

(2)修正隸屬度矩陣

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

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

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

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

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

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

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

(2)計算出 U(L)：

當 Ij＝φ 時；

當 Ij≠φ 時,?i∈Ij，uij=0,

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

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

對第s類的隸屬度為：

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

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

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

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

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

為保證改進的FCM聚類結果為全局最優解，采用減法聚類的聚類中心作為改進的FCM聚類的初始聚類中心。算法步驟如下：

(1)設定聚類參數：領域的半徑 ra、rb,比例參數 δ，FCM聚類數c,模糊指數m和最小誤差ε,迭代次數L,吸引力抑制因子α。

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

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

減法聚類中心中，密度指標越大的聚類中心出現得越早，越有可能成為改進的FCM初始聚類中心。所以，當聚類數為c時，取減法聚類產生的前c個聚類中心作為改進的FCM的初始中心，無須再重新初始化，從而提高了聚類的效率。

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

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

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

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

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

3仿真與結果分析

為驗證基于減法聚類的改進的FCM算法的效果，利用Iris植物樣本數據進行仿真實驗,將結果與傳統FCM進行對比。Iris數據集是公認的最適用于數據挖掘的數據集，它有四個屬性、三種植物種類(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)。分別用傳統的 FCM 和基于減法聚類的改進的FCM對Iris數據集進行聚類分析。實驗中，設定允許最小誤差ε均為10-3,模糊指數m=2，ra=0.5,rb=0.6,α=0,Iris數據集的聚類結果如圖 1、圖 2所示。Iris數據集的比較如表1所示。

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

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

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

表1 Iris數據集的性能比較

[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]齊淼，張化祥.改進的模糊c-均值聚類算法研究[J].計算機工程與應用,2009,45(20).

[5]閆兆振.自適應模糊c-均值聚類算法研究[D].濟南：山東科技大學,2006.