馬 寶 秋

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

?

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

馬 寶 秋

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

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

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

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

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

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

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

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

1FCM算法介紹

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

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

(1)

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

(2)

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

圖2　模糊隸屬度矩陣

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

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

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

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

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

(3)

步驟2，計(jì)算每一個(gè)聚類的中心點(diǎn)，公式為：

(4)

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

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

(5)

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

(6)

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

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

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

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

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

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

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

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

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

(7)

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

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

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

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

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

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

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

(8)

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

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

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

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

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

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

圖3FCM分割算法處理效果

5FCM算法總結(jié)

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

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

6結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]蔡元萃,陳立潮.聚類算法研究綜述[J].科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì),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].中國(guó)造船,2007,48(4):98-103.

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

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

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

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

[10]楊燕,靳蕃,KAMEL MOHAMED.聚類有效性評(píng)價(jià)綜述[J].計(jì)算機(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

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

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

中圖分類號(hào)：TP301.6

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