模糊C均值聚類算法編程實現(xiàn)及應(yīng)用

馬 寶 秋

(石家莊職業(yè)技術(shù)學(xué)院 機電工程系，河北 石家莊　050081)

?

模糊C均值聚類算法編程實現(xiàn)及應(yīng)用

馬 寶 秋

(石家莊職業(yè)技術(shù)學(xué)院 機電工程系，河北 石家莊050081)

摘要：模糊C均值(Fuzzy C-Means)算法是在K-Means聚類算法的基礎(chǔ)上，利用模糊數(shù)學(xué)的原理進行的改進，討論了它的數(shù)學(xué)原理及使用C++語言編程實現(xiàn)的步驟，將其應(yīng)用于超聲圖像感興趣區(qū)域(ROI)的檢測，取得了可信的結(jié)果.

關(guān)鍵詞：Fuzzy C-Means；聚類；算法；編程

分類問題廣泛地存在于社會和自然科學(xué)中.所謂分類，就是把相似或相近的對象分到一組，讓在同一個組中的成員對象都有一些相似的屬性，在一個組中的各成員對象之間比不在同一組中的成員對象之間具有更多的相似性.聚類(Cluster)分析是解決分類問題的一個重要的統(tǒng)計分析方法[1].聚類時，不關(guān)心或者說根本不知道某一類是什么，目標(biāo)是把相似的東西聚到一起.因此，聚類算法可以開始工作的前提是僅需知道如何計算相似度[1].

聚類方法非常豐富[2-3].根據(jù)K-Means聚類算法，每個數(shù)據(jù)對象都有其權(quán)重wji，由wji可構(gòu)成一個矩陣，該矩陣稱為隸屬度矩陣，表示每個數(shù)據(jù)對象屬于某個分類的“度”.由K-Means聚類的定義可知，wji不是1就是0，1代表該數(shù)據(jù)對象屬于某一分類，0則相反.因為每一個數(shù)據(jù)對象只能屬于一個分類，所以K-Means聚類的分類劃分是一種硬聚類，它把每個數(shù)據(jù)對象嚴(yán)格地劃分到某個類中，具有非此即彼的性質(zhì).

但是，由于分類的復(fù)雜性，硬聚類劃分往往力不從心.如，對于圖1所示的蝴蝶型數(shù)據(jù)，中間的點到底應(yīng)該歸屬于左邊一組還是右邊一組，K-Means聚類算法就無法完成準(zhǔn)確的劃分.這種無法劃分是由于蝴蝶型數(shù)據(jù)分類問題本身的硬不可分性造成的.對硬劃分這是無法避免的[4].

圖1　蝴蝶型數(shù)據(jù)

本文論述的Fuzzy C-Means(FCM)算法是在K-Means硬聚類算法的基礎(chǔ)上，利用模糊數(shù)學(xué)的概念，引入概率的表示方法，對K-Means進行的“軟”改進.

1FCM算法介紹

Jim Bezdek提出了基于模糊度m的基本Fuzzy C-Means(FCM)的模糊劃分算法[5].FCM的目標(biāo)函數(shù)定義如同K-Means聚類劃分，但其權(quán)重矩陣W不再是非0即1的二元矩陣，而是應(yīng)用模糊理論的概念，使用概率的表示方法，它的每一個數(shù)據(jù)對象不是僅屬于某一個聚類，而是以概率的形式表現(xiàn)數(shù)據(jù)對象屬于各個聚類的程度，稱之為軟聚類劃分(Soft Clustering).

FCM的數(shù)學(xué)表達式為：

(1)

其中，N為數(shù)據(jù)的總數(shù)；K為聚類分類的個數(shù)；Ji為第i類聚類分類的目標(biāo)函數(shù)；Xj為第j個數(shù)據(jù)；Ci為第i個聚類的中心；m為權(quán)重指數(shù)(也稱為模糊度)；wji為隸屬度，即Xj屬于聚類Ci的程度，或者說Xj屬于聚類Ci的概率. wji滿足以下關(guān)系：

(2)

這里的隸屬度wji不再是非0即1，而是一個屬于[0,1]的數(shù)值.圖2是一個具有10個數(shù)據(jù)、2個聚類的隸屬度矩陣.

圖2　模糊隸屬度矩陣

從圖2可以看出，每一行代表一個聚類，每一列上的數(shù)值表示該數(shù)據(jù)對象在每一個聚類中的隸屬度，實際也就是屬于每一個聚類的概率，即每一列數(shù)值之和為1.也就是說，每一個數(shù)據(jù)對象并不是完全屬于某一個聚類，而是通過概率的形式表達該數(shù)據(jù)對象在某一個聚類中的隸屬度.

2FCM算法的實現(xiàn)

2.1FCM算法的實現(xiàn)步驟

根據(jù)FCM的數(shù)學(xué)表達式所表達的算法，按照以下幾個步驟即可實現(xiàn)本算法[5-6].

步驟1，設(shè)定K為分類個數(shù)，W為初始隸屬度矩陣，W中的每個數(shù)據(jù)元素wji采用計算機偽隨機給定[0,1]之間的數(shù)值，并滿足(3)式.

(3)

步驟2，計算每一個聚類的中心點，公式為：

(4)

步驟3，根據(jù)(1)式計算第t次和第t-1次迭代的目標(biāo)函數(shù)J(t)和J(t-1)，并計算J(t)和J(t-1)之間的差值.當(dāng)這個差值小于設(shè)定的某個容忍誤差ε時，可結(jié)束迭代運算過程，否則，執(zhí)行步驟4.

E(t)=‖J(t)-J(t-1)‖<ε

(5)

步驟4，重新計算隸屬度矩陣W，公式如(6)式，并返回到步驟2.

(6)

其中，Cs為本次迭代所得的每一個聚類中心.

2.2FCM算法的實現(xiàn)步驟

FCM算法可應(yīng)用于二維灰度圖像的處理，主要是將圖像中的像素進行分類.例如，在人體的CT、核磁或超聲圖像中將人體組織的器官圖像區(qū)分出來，某一個像素的灰度值與某個器官組織的整體灰度值接近的概率比較大，則其在圖像中就代表該器官組織的一個像素，也就是本文所說的感興趣區(qū)域(ROI).

與此相對應(yīng)，公式(1)中的部分參數(shù)的含義變?yōu)椋篘為圖像像素的總數(shù)，K為圖像中分類的數(shù)量，Ji為第i個分類的目標(biāo)函數(shù)，Xj為第j個圖像像素的灰度值，Ci為第i個分類的像素灰度的中心值.

灰度圖像的FCM算法在計算機中實現(xiàn)的步驟如下：

第一步，設(shè)定常數(shù)，包括需要分類的數(shù)目K，最大執(zhí)行步驟tmax，還有一個很小但大于0的容忍誤差ε以及其他需要使用的變量等.

第三步，利用嵌套循環(huán)實現(xiàn)算法的迭代.fort=1，2,…，tmax.

(a)forj= 1，2，…，N，計算每一個像素的隸屬度，即算出隸屬度矩陣.

(b)fori=1，2，…，K，更新每一個聚類分類灰度中心值.

(7)

其中，m為權(quán)重指數(shù).

(c)判斷迭代是否收斂，若式(5)成立則停止運算，否則進行下一輪迭代.

第四步，若第三步的t循環(huán)未到tmax次就結(jié)束，則表示聚類分類灰度中心值已不發(fā)生變化，誤差小于ε，所得到的Ci(i= 1，…，K)即可認為是每個聚類分類的灰度中心值，即已經(jīng)收斂.若t循環(huán)是因為達到tmax而結(jié)束，則表示在限定的tmax循環(huán)次數(shù)內(nèi)聚類分類的灰度中心值還不穩(wěn)定，可以通過增大循環(huán)次數(shù)來解決；當(dāng)然，也可能是因為所聚類的灰度圖像數(shù)據(jù)是發(fā)散的而沒有灰度中心值.

3算法實現(xiàn)的注意事項

第一，在具體計算時，算法中權(quán)重指數(shù)m的取值有很多種，筆者在“基于實時超聲影像的軟組織形變跟蹤技術(shù)”課題中，經(jīng)過多次篩選，取m為2[7].

第二，判斷算法收斂的方法不僅僅是利用式(5)，還可以通過判斷鄰近兩次迭代聚類中心的變化足夠小，即聚類分類灰度中心值的變化小于ε來確定.

E(t)=‖C(t)-C(t-1)‖<ε

(8)

其中，C(t)和C(t-1)分別代表第t次和第t-1次迭代所得到的聚類中心.

第三，一般情況下可以采用計算機隨機函數(shù)產(chǎn)生K個聚類中心，但是針對具體的問題可以采用其他算法粗略得到一些聚類中心的灰度值，或者直接人工選取.

第四，在二維灰度圖像的應(yīng)用中，通過判斷計算得到的每一個圖像灰度數(shù)據(jù)的隸屬度，來決定其屬于哪一個聚類分類，即通過判斷隸屬度值wji在哪一個聚類中的值最大來決定該數(shù)據(jù)的歸屬.

4FCM算法的應(yīng)用

筆者通過上述方法在“基于實時超聲影像的軟組織形變跟蹤技術(shù)”課題的研究中實現(xiàn)了FuzzyC-Means的聚類算法，并成功地應(yīng)用于對軟組織超聲圖像ROI的辨別中，所得到的FCM分割效果見圖3.本應(yīng)用中K取值為3，即分為3類.從圖3(b)中可以看出，F(xiàn)CM雖然不能得到完美的ROI邊緣，但是從目視的角度可以明確地區(qū)分出邊緣，用于定性對比就已經(jīng)足夠了.

(a)腎臟原始超聲圖像 (b)去噪后FCM的處理效果

圖3FCM分割算法處理效果

5FCM算法總結(jié)

FCM算法應(yīng)用了模糊理論的概念，使得每一個輸入數(shù)據(jù)不再僅歸屬于某一特定的聚類，而是以其歸屬的概率來表現(xiàn)它屬于各聚類的程度，在運算過程中沒有任何先驗的知識也可以應(yīng)用[1].FCM算法大多數(shù)情況下能夠給出令人滿意的結(jié)果，在應(yīng)用中一般作為其他分析算法的預(yù)處理步驟.

FCM聚類算法也有其局限性.首先，計算前需確定聚類的數(shù)目，因此不能實現(xiàn)自動分類.其次，該算法對初值較敏感.初始聚類中心位置若不是理想的位置，目標(biāo)函數(shù)J容易落入局部解，不能保證全局最優(yōu)，可能導(dǎo)致分類出來的結(jié)果不理想[2].所以在實踐應(yīng)用中，可以多次選取初值進行運算，取其中最好的一次結(jié)果即可.再次，目前還沒有確定m值的較好方法[8].文獻中記載m的取值一般為[1.5，2.5]，也有人提出了m的優(yōu)選方法[9].m值的選擇一般是從對分類結(jié)果評價的角度來進行的[10]，所以m的取值仍有待于進一步研究.第四，運算量大.因為每迭代一次就需要將所有數(shù)據(jù)計算一遍，其時間復(fù)雜度為O(n3)，其中n為數(shù)據(jù)對象的數(shù)量，因此，該算法的數(shù)值運算量很大，對于大的數(shù)據(jù)量往往不能進行實時運算.

6結(jié)語

本文詳細講述了FCM算法，并使用C++編程實現(xiàn)了本文的算法，并應(yīng)用于“基于實時超聲影像的軟組織形變跟蹤技術(shù)”課題中，實現(xiàn)了對軟組織超聲圖像ROI的前期分類，為后續(xù)的圖像處理打下了堅實的基礎(chǔ).

參考文獻：

[1]李麗麗.模糊C-均值聚類算法及其在圖像分割中的應(yīng)用[D].濟南:山東師范大學(xué),2009.

[2]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報,2008,19(1):48-61.

[3]蔡元萃,陳立潮.聚類算法研究綜述[J].科技情報開發(fā)與經(jīng)濟,2007,17(1):145-146.

[4]BEZDEK J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York：Plenum Press，1981:95-107.

[5]孟憲堯,韓新潔.模糊C-均值聚類算法及其在船舶故障診斷中的應(yīng)用[J].中國造船,2007,48(4):98-103.

[6]張翡,范虹.基于模糊C均值聚類的醫(yī)學(xué)圖像分割研究[J].計算機工程與應(yīng)用,2014,50(4):144-151.

[7]黃蓉.模糊C-均值聚類算法的若干研究及其在IDS中的應(yīng)用[D].南京:南京郵電大學(xué)，2014.

[8]于劍.論模糊C均值算法的模糊指標(biāo)[J].計算機學(xué)報,2003,26(8):968-973.

[9]高新波,裴繼紅,謝維信.模糊C-均值聚類算法中加權(quán)指數(shù)m的研究[J].電子學(xué)報,2000,28(4):80-83.

[10]楊燕,靳蕃,KAMEL MOHAMED.聚類有效性評價綜述[J].計算機應(yīng)用研究,2008,25(6):1630-1632.

責(zé)任編輯：金欣

Realization of fuzzy C-Means clustering algorithm and its application

MA Bao-qiu

(Department of Mechanics and Electrics, Shijiazhuang Vocational Technology Institute, Shijiazhuang, Hebei 050081, China)

Abstract：Fuzzy C-Means is a type of clustering algorithm that is improved by the principle of fuzzy mathematics in the K-Means algorithm. This paper discusses the mathematical principle of the fuzzy C-means clustering algorithm and the steps of using the C++ language programming. The author has applied it to the detection of the region of interest (ROI) in ultrasound images.

Key words：fuzzy C-Means; clustering; algorithm; programming

收稿日期：2016-03-02

作者簡介：馬寶秋(1973-)，男，河北石家莊人，石家莊職業(yè)技術(shù)學(xué)院講師.

文章編號：1009-4873(2016)02-0030-04

中圖分類號：TP301.6

文獻標(biāo)志碼：A