一種改進的FCM算法及仿真實驗研究

劉杰

(陜西理工學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院， 陜西 漢中 723000)

[摘要]針對模糊C均值(FCM)算法的缺陷，提出了一種改進的FCM算法。將物理學(xué)中的信息熵概念引入聚類分析中，用熵值法度量樣本的各種屬性對分類不同程度的影響，并用模糊劃分系數(shù)FC(μ)和平均模糊熵HC(μ)對改進后的算法性能進行了評價。仿真實驗結(jié)果表明，改進后算法的FC(μ)和HC(μ)分別為0.919和-0.096，改進后的FCM算法在實際的聚類分析中能取得更好的分類效果。

[關(guān)鍵詞]模糊C均值算法；改進；信息熵；模糊劃分系數(shù)；平均模糊熵

[文章編號]1673-2944(2015)04-0040-05

[中圖分類號]TP301.6

收稿日期：2014-11-07

基金項目：陜西省科技廳重大科技創(chuàng)新專項(2011ZKC05-16)；陜西省教育廳科學(xué)研究計劃項目(12JK0982)

作者簡介：劉杰(1982—)，女，陜西省漢中市人，陜西理工學(xué)院講師，碩士，主要研究方向為智能算法及應(yīng)用。

聚類就是按照一定的要求和規(guī)律對事物進行區(qū)分和分類的過程。聚類分析是多元統(tǒng)計分析的一種，它將沒有類別標(biāo)記的樣本按照某種準(zhǔn)則劃分成若干子集，使相似的樣本盡可能歸為一類，而不相似的樣本盡量劃分到不同類。由于在該過程中沒有任何關(guān)于分類的先驗知識而僅靠事物間的相似性作為類屬劃分的準(zhǔn)則，因此屬于無監(jiān)督分類方法。該方法已經(jīng)被廣泛應(yīng)用于模式識別、數(shù)據(jù)挖掘及圖像處理等各個領(lǐng)域。

傳統(tǒng)的聚類分析是一種硬劃分，將每一個樣本嚴格地歸屬于某一類中，具有非此即彼的絕對性，分類界限明確。而在實際的分類中，很多對象在性態(tài)和類屬方面具有中介性，那么采用硬劃分的方法就因為出現(xiàn)爭議而缺乏合理性，因此通常采用軟劃分。Zadeh提出的模糊集理論為這種軟劃分提供了重要的理論依據(jù)，通過度量樣本屬于各類別的不確定性程度來描述樣本類屬的中介性，更客觀地反映現(xiàn)實世界，最終實現(xiàn)樣本的模糊聚類分析。在各種模糊聚類算法中，Bezdek于1973年提出的FCM(模糊C均值，F(xiàn)uzzy C-Means)聚類算法是非監(jiān)督模式識別中最經(jīng)典且應(yīng)用最廣泛的算法[1]。該算法通過隸屬度來描述每個樣本屬于某個聚類的程度，并利用極小化目標(biāo)函數(shù)求得最優(yōu)解較好地實現(xiàn)了空間聚類[2-3]。但是FCM算法也存在自身的缺陷：算法事先假設(shè)待分類樣本的各項屬性對分類的貢獻相同，忽略了各種屬性對分類的不同程度的影響[4]?；谶@一點，本文提出了一種FCM算法的改進方法，通過信息熵權(quán)重來度量樣本各項屬性對分類的影響，將該權(quán)重引入到FCM算法中。為了驗證改進后算法的有效性，通過具體實例進行仿真實驗。

1經(jīng)典的FCM算法

設(shè)待劃分的樣本集X={X1,X2,…,Xn}，n為樣本個數(shù)，聚類的類別數(shù)為C，則有C個聚類中心V=(v1,v2,,…,vC)，其中2≤C≤n，則n個樣本對應(yīng)于C個類簇的隸屬矩陣表示為：

(1)

其中μij代表第j個樣本屬于第i類的隸屬度。并且它滿足以下幾個條件：

(2)

(3)

(4)

經(jīng)典FCM算法的基本思想是同一類簇中的樣本之間的距離盡可能最小，而不同類簇中樣本的距離盡可能的大。算法采用的具體步驟如下：

Step 1：由用戶給定聚類的數(shù)目C；

Step 2：隨機選擇C個樣本，選出的每一個樣本被稱為一個種子，代表一個類的均值或中心；

Step 3：將剩余的每個樣本賦給離它最近的類；

Step 4：重新計算每個類中樣本的平均值，形成新的聚類中心；

Step 5：判斷新的聚類中心是否和上次的完全相同，若相同則算法停止，否則返回到Step3。

將該算法表示為極小化的目標(biāo)函數(shù)為：

(5)

其中vi為每一類的類簇中心；(xj-vi)2表示第j個樣本Xj到第i類類簇中心vi的歐氏距離；m為加權(quán)指數(shù)，它的最佳取值范圍為[1.5，2.5]，Bezdek在研究中發(fā)現(xiàn)m=2時具有明確的物理意義[5]。

由拉格朗日算法聯(lián)合式(4)，可得類簇中心vi和隸屬度μij的迭代公式為：

(6)

(7)

2改進的FCM算法

由于FCM算法事先假設(shè)待分類樣本的各項屬性對分類的貢獻相同，忽略了各種屬性對分類的不同程度的影響?；谶@一點，本文提出基于屬性信息熵權(quán)重的FCM改進算法。

2.1信息熵

“熵”是德國物理學(xué)家克勞修斯于1850年提出的概念，是熱力學(xué)和統(tǒng)計物理學(xué)中特有的宏觀量，它用來表示任何一種能量在空間中分布的均勻程度。信息論之父C.E.Shannon在1948年發(fā)表的論文《通信的數(shù)學(xué)理論》中將熵的概念引入信息論，稱為“信息熵”。系統(tǒng)的熵值直接反映了它所處狀態(tài)的均勻程度。個體之間越是接近，表示他們的差異越不顯著，熵值就越大，反之，個體差異越明顯其熵值就越小[6]。

(8)

2.2熵值法確定權(quán)重

根據(jù)信息熵理論，信息熵是信息不確定性的度量，若某個屬性的熵值越小，則說明該屬性在決策時所起的作用越大，應(yīng)賦予該屬性較大的權(quán)重。即可以用熵值法來確定樣本各屬性的權(quán)重[8]。對于給定樣本集的第s項屬性，若該屬性的信息熵值越大，則表示樣本間該屬性的差異性越小，那么其表示該屬性在決定樣本分類時所起的作用就越小。相反的，若該屬性的信息熵值越小，那么其表示該屬性在決定樣本分類時所起的作用就越大。根據(jù)屬性的熵值大小ej與該屬性下的分類歸屬相反的原則，定義屬性s的差異因數(shù)即偏差程度系數(shù)為：

(9)

當(dāng)gs越大時，第s項屬性就越重要，那么假設(shè)樣本集有z項屬性，用差異性因數(shù)gs來確定第s項屬性的權(quán)重：

(10)

2.3基于信息熵權(quán)重的FCM改進算法

設(shè)第j個樣本Xj有z個屬性，記為Xj=(xj1，xj2，…，xjz)，1≤j≤n。根據(jù)信息熵值法得到的屬性權(quán)重為W=(w1，w2，…，wz)，將經(jīng)典的FCM算法進行改進如下：

(11)

基于該改進算法的類簇中心vi和隸屬度μij的迭代公式為：

(12)

(13)

3實例仿真

3.1實驗數(shù)據(jù)

以漢江水源地漢中市的水污染物COD分配為例，采用改進后的FCM算法對漢中市的11個行政區(qū)域水污染物削減程度進行分類，依據(jù)各區(qū)域的經(jīng)濟環(huán)境發(fā)展情況和COD的排放量將各個行政區(qū)域歸屬為重點削減區(qū)域、加強削減區(qū)域和普通削減區(qū)域3大類。

選取2010年漢中市11個行政區(qū)作為樣本集，區(qū)域水資源量、區(qū)域水環(huán)境容量、區(qū)域人口、區(qū)域生產(chǎn)總值(GDP)為樣本集的4項屬性，樣本集及其屬性數(shù)據(jù)如表1所示(數(shù)據(jù)均來自于《2010年漢中市統(tǒng)計年鑒》和《2010年漢中市環(huán)保局環(huán)境統(tǒng)計公報》)。

表1　2010年漢中市各縣區(qū)社會經(jīng)濟環(huán)境指標(biāo)

續(xù)表

3.2數(shù)據(jù)歸一化處理

為了消除不同量綱對結(jié)果的影響，先對表1中的基礎(chǔ)數(shù)據(jù)按照式(14)進行歸一化處理：

(14)

式中xjs表示第j樣本的第s項屬性值，minxs和maxxs分別表示所有樣本第s項屬性的最小值和最大值。

3.3計算各屬性的權(quán)重

按照本文2.2中的熵值法計算出樣本數(shù)據(jù)的4項屬性的權(quán)重如表2所示。

表2　樣本各項屬性的權(quán)重

3.4兩種算法的聚類結(jié)果

采用以上實驗數(shù)據(jù)分別利用兩種算法對該問題進行聚類。在兩種算法中，分類數(shù)C=3，分別表示重點削減A類、加強削減B類和普通削減C類。樣本數(shù)n=11，加權(quán)指數(shù)m=2，F(xiàn)CM算法采用式(5)，迭代方式采用式(6)和(7)，改進的FCM算法采用式(11)，迭代方式采用式(12)和(13)。利用Matlab進行算法實現(xiàn)，得到如表3的分類結(jié)果。

表3　兩種算法的分類結(jié)果

3.5改進的FCM算法的性能評價

為了判定改進后的FCM算法的性能，引入聚類分析算法中的兩個主要性能指標(biāo)，即模糊劃分系數(shù)FC(μ)和平均模糊熵HC(μ)：

(15)

(16)

分別計算兩種算法的兩個性能指標(biāo)，計算結(jié)果如表4所示。

表4　兩種算法的性能指標(biāo)

從表4中可以看出，在該應(yīng)用中，改進后的FCM算法的模糊劃分系數(shù)和平均模糊熵兩項主要的性能指標(biāo)都比FCM原型算法有所增大。從表1的基礎(chǔ)數(shù)據(jù)不難看出，漢臺和城固兩個區(qū)域的水資源量和環(huán)境容量僅占全市的6.7%和5.6%，水污染物COD的排放量卻占到全市總量的23%，尤其是漢臺區(qū)的水資源量僅僅占0.7%，COD排放量卻占到全市的6%，因此這兩個區(qū)域?qū)儆谥攸c削減區(qū)域。其次，勉縣和洋縣兩個區(qū)域占全市16%的環(huán)境容量，卻占全市30%的COD排放量，屬于加強削減區(qū)域。其余的7個區(qū)域均屬于普通削減區(qū)域。該分類結(jié)果與實際情況和實際需要更加相符。從該實驗的分類結(jié)果來看，改進后的FCM算法考慮了各屬性在聚類分析中的影響程度，在實際應(yīng)用中能更切實際地進行類屬的劃分。

4結(jié)論

改進后的FCM算法克服了在分類時屬性對分類結(jié)果的影響，在原型算法中增加了屬性權(quán)重的因素，利用屬性的信息熵反映并度量屬性在分類時的重要性，采用熵權(quán)法確定各屬性權(quán)重，同時對迭代過程中類簇中心和隸屬矩陣的更新做出了相應(yīng)的修正。數(shù)據(jù)的仿真實驗證明改進后的算法分類能更好地反映客觀現(xiàn)實。

[參考文獻]

[1]KONG Yue-ping,ZENG Ping.A robust method for inverse halftoningvia 2-D nonlinear pyramid[J].Chinese Optics Letters,2007,5(11):573-576.

[2]肖春景,張敏.基于減法聚類與模糊C-均值的模糊聚類的研究[J].計算機工程,2005(31):135-137.

[3]孫惠琴,熊璋.改進的FCM算法及其在腦電信號處理中的應(yīng)用[J].重慶大學(xué)學(xué)報:自然科學(xué)版,2014,37(6):83-88.

[4]張翡,范虹,郝艷榮.結(jié)合非局部均值的快速FCM算法分割MR圖像研究[J].計算機科學(xué),2014,41(5):304-307.

[5]BEZDEK J C.A Physical Interpretation of Fuzzy ISODATA[J].IEEET rans SMC,1976,6(3):387-390.

[6]黃定軒.基于客觀信息熵的多因素權(quán)重分配方法[J].系統(tǒng)工程理論方法應(yīng)用,2003,12(4):321-324.

[7]許友權(quán),吳陳,楊習(xí)貝.初始聚類中心優(yōu)化的加權(quán)最大熵核FCM算法[J].計算機系統(tǒng)應(yīng)用,2014,23(8):139-143.

[8]朱方霞,陳華友.確定區(qū)間數(shù)決策矩陣屬性權(quán)重的方法——熵值法[J].安徽大學(xué)學(xué)報:自然科學(xué)版,2005,30(5):4-6.

[責(zé)任編輯：謝 平]

An improved FCM algorithm and its simulation experiments

LIU Jie

(School of Mathematics and Computer Science, Shaanxi University of Technology,

Hanzhong 723000, China)

Abstract:Considering the defects of the traditional Fuzzy C-Means (FCM) algorithm, an improved FCM algorithm has been proposed in this paper. The information entropy which is the concept of the physics is introduced into the fuzzy cluster analysis and the entropy evaluation method is used to measure the varying degree of influence of the various attributes in cluster analysis. At the same time, the fuzzy division coefficient FC(μ) and the average fuzzy entropy HC(μ) are used to evaluate the performance of the improved FCM algorithm. The simulation results show that the FC(μ) and the HC(μ) are 0.919 and -0.096 respectively which show that the improved FCM algorithm can obtain better classification effect than the traditional FCM algorithm in practical application.

Key words:Fuzzy C-Means algorithm;improve;information entropy;fuzzy partition coefficient;average fuzzy entropy