薛艷鋒　劉繼華　高永強(qiáng)　高志娥　武彩紅

(呂梁學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系　山西 呂梁 033000)

?

一種加權(quán)模糊C均值聚類算法及其在圖像分割中的應(yīng)用

薛艷鋒劉繼華高永強(qiáng)高志娥武彩紅

(呂梁學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系山西 呂梁 033000)

摘要現(xiàn)有的加權(quán)模糊C均值聚類算法中，屬性加權(quán)是一個(gè)不斷迭代、重復(fù)計(jì)算的過(guò)程，費(fèi)時(shí)費(fèi)力。針對(duì)這種情況，提出Fisher線性判別率進(jìn)行屬性加權(quán)。算法首先直接計(jì)算每一維屬性對(duì)模糊聚類的貢獻(xiàn)度，其次對(duì)所有屬性的貢獻(xiàn)度進(jìn)行歸一化處理然后加權(quán)聚類。在人工和實(shí)際數(shù)據(jù)集所做實(shí)驗(yàn)表明：該算法在提高聚類速度的同時(shí)，聚類效果上也優(yōu)于其他同類加權(quán)模糊C均值聚類算法。

關(guān)鍵詞模糊C均值聚類Fisher線性判別率屬性加權(quán)分配系數(shù)劃分熵隸屬度彩色圖像分割顏色空間

0引言

數(shù)據(jù)聚類是通過(guò)分類的方法把相似的數(shù)據(jù)元素分成不同的子集，讓在同一個(gè)子集中的數(shù)據(jù)元素具有相似的屬性，不同子集中的數(shù)據(jù)元素具有相異的屬性的過(guò)程[1]。依據(jù)數(shù)據(jù)聚類的方式，可以將數(shù)據(jù)聚類分為硬聚類和模糊聚類(也稱為軟聚類)兩種。在硬聚類中，數(shù)據(jù)元素被劃分成不同的類，其中每個(gè)數(shù)據(jù)元素只能屬于同一個(gè)類；在模糊聚類中，數(shù)據(jù)元素可以屬于多個(gè)類，且每個(gè)數(shù)據(jù)元素都與每個(gè)類存在著對(duì)應(yīng)的隸屬度以表明數(shù)據(jù)元素和一個(gè)特定的類之間的關(guān)聯(lián)強(qiáng)度。就模糊方法而言，在不同聚類中的隸屬度是相互關(guān)聯(lián)的，同時(shí)硬聚類也可以看成是模糊聚類的一個(gè)特例[2]。

模糊C-均值聚類(FCM)算法應(yīng)用最廣，它的模糊性允許一個(gè)數(shù)據(jù)元素屬于2個(gè)或2個(gè)以上的聚類(通過(guò)隸屬度體現(xiàn))。然后不斷優(yōu)化各個(gè)數(shù)據(jù)元素的隸屬度以及聚類中心達(dá)到數(shù)據(jù)聚類效果最優(yōu)的目的[3,4]。具體做法是將一組有限的數(shù)據(jù)元素集合X={x1,…,xn,…,xN}聚集為C個(gè)模糊聚類并使目標(biāo)函數(shù)最小化：

(1)

其中：m為模糊器，它能影響每個(gè)數(shù)據(jù)隸屬度的模糊性；unc是數(shù)據(jù)元素xn與第c個(gè)聚類相對(duì)應(yīng)的隸屬度；‖xn-vc‖2為數(shù)據(jù)元素xn與對(duì)應(yīng)的聚類中心vc之間的歐式距離。每個(gè)數(shù)據(jù)元素包含D個(gè)屬性F={f1,…,fd,…,fD}，即每個(gè)數(shù)據(jù)元素可表示為xn=(xn1,…,xnd,…,xnD)，其中xnd是數(shù)據(jù)元素xn在d維屬性上的映射。隸屬度unc以及聚類中心vc的迭代公式如下：

(2)

(3)

終止條件為：

(4)

其中，ε為終止準(zhǔn)則；k為迭代次數(shù)。詳細(xì)步驟如下：

(1) 初始化U=[unc]矩陣，U(0);

(2) 在第k次迭代時(shí)，通過(guò)U(k)計(jì)算聚類中心V(k)=[vc]，如式(3)；

(3) 更新U(k)為U(k+1)，如式(2)；

(4) 如果‖U(k+1)-U(k)‖<ε,算法結(jié)束，否則，跳轉(zhuǎn)至第(2)步；

由于各個(gè)屬性對(duì)聚類的貢獻(xiàn)程度不等，所以需要為各個(gè)屬性賦予對(duì)應(yīng)的權(quán)重[5-8]，文獻(xiàn)[9]采用的Bootstrap方法證明了屬性加權(quán)對(duì)聚類效果作用明顯。

Bootstrap方法需要重復(fù)選取不斷調(diào)整屬性權(quán)重直到聚類結(jié)束，或者需要通過(guò)計(jì)算大量的屬性加權(quán)最后求取平均值。本文采用基于Fisher線性判別率的方法無(wú)需迭代直接計(jì)算各屬性權(quán)重，在減少迭代次數(shù)的基礎(chǔ)上提高了聚類效果。

1基于Fisher準(zhǔn)則的屬性加權(quán)模糊C均值聚類

1.1Fisher線性判別率

Fisher準(zhǔn)則[10]的基本方法是，對(duì)于一個(gè)包含N個(gè)D維數(shù)據(jù)元素的集合Ω，假設(shè)有N1個(gè)數(shù)據(jù)元素屬于子集Ω1，N2個(gè)數(shù)據(jù)元素屬于子集Ω2。為了在投影方向y=WTX上使兩個(gè)子集的數(shù)據(jù)元素分得更開，每一個(gè)子集的數(shù)據(jù)元素聚得更緊，需要尋找W向量，使得Fisher準(zhǔn)則函數(shù)J(W)值盡可能大。

(5)

(6)

(7)

(8)

(9)

Jfisher就是Fisher線性判別率，值越大，說(shuō)明該維屬性對(duì)聚類的影響越明顯，應(yīng)該賦予更大的加權(quán)系數(shù)。

1.2基于Fisher準(zhǔn)則的屬性加權(quán)模糊C均值聚類

本文所提算法就是把Fisher線性判別率準(zhǔn)則運(yùn)用于模糊C均值聚類算法，步驟如下：

(1) 選取一個(gè)整數(shù)c(2≤c≤N-1)和一個(gè)閾值ε(ε=1e-5)。初始化模糊劃分矩陣U，得到取值為0到1的矩陣隸屬度元素。

(2) 依據(jù)式(3)計(jì)算vc(1≤c≤C)。

(3) 通過(guò)模糊劃分矩陣U的最大值，指派對(duì)應(yīng)數(shù)據(jù)元素屬于C個(gè)聚類中的某一類。其次，通過(guò)Fisher線性判別率計(jì)算各個(gè)屬性分量在聚類中的貢獻(xiàn)度Jfisher，進(jìn)而計(jì)算出各個(gè)屬性權(quán)重W′：

(10)

(4) 依據(jù)公式：

(11)

(12)

更新模糊劃分矩陣U。

(5) 計(jì)算目標(biāo)函數(shù)

(13)

(6) 如果相鄰兩次的差值小于閾值ε，算法結(jié)束，否則，轉(zhuǎn)到第(2)步。

2實(shí)驗(yàn)結(jié)果

2.1度量標(biāo)準(zhǔn)

聚類有效性函數(shù)[11]主要從不同方面衡量聚類的效果。近來(lái)十幾年，出現(xiàn)了諸多的聚類有效性函數(shù)作為度量標(biāo)準(zhǔn)，其中最重要的兩種度量標(biāo)準(zhǔn)分別針對(duì)數(shù)據(jù)元素集合的模糊劃分以及數(shù)據(jù)元素集合的幾何結(jié)構(gòu)。

針對(duì)數(shù)據(jù)元素集合模糊劃分標(biāo)準(zhǔn)的主要思想是：劃分的模糊度越小，聚類效果越好。這類度量標(biāo)準(zhǔn)的兩個(gè)代表函數(shù)分別是分配系數(shù)Vpc[12]以及劃分熵Vpe[11]：

(14)

(15)

2.2實(shí)驗(yàn)1人造數(shù)據(jù)集

圖1　″○″代表第一聚類以及″*″代表第二聚類

聚類算法FCMBFWFCMFFWFCM迭代次數(shù)15.72096.56015.340分配系數(shù)(PC)0.7710.7890.837劃分熵(PE)0.5300.4940.393目標(biāo)函數(shù)(OF)139.688139.482113.050聚類中心距離誤差0.5870.7060.483最后屬性加權(quán)(0.50,0.50)(0.40,0.60)(0.06,0.94)

圖2　″○″代表第一聚類以及″*″代表第二聚類

聚類算法FCMBFWFCMFFWFCM迭代次數(shù)17.28099.12013.500分配系數(shù)(PC)0.7450.7630.828劃分熵(PE)0.5770.5480.419目標(biāo)函數(shù)(OF)121.141120.04490.397聚類中心距離誤差0.2690.3970.334最后屬性加權(quán)(0.50,0.50)(0.41,0.59)(0.07,0.93)

2.3實(shí)驗(yàn)2標(biāo)準(zhǔn)數(shù)據(jù)集

繼續(xù)選擇兩個(gè)著名的真實(shí)數(shù)據(jù)集Iris和Wine進(jìn)行測(cè)試，情況描述見(jiàn)表3所示。

表3　兩類真實(shí)數(shù)據(jù)集

通過(guò)與上述兩種算法的比較，我們得到實(shí)驗(yàn)結(jié)果如表4、表5所示。從表4中，可以清楚地看到：在迭代次數(shù)、分配系數(shù)(PC)、劃分熵(PE)度量標(biāo)準(zhǔn)上，本文所提算法都取得最好的效果。而在目標(biāo)函數(shù)(OF)度量標(biāo)準(zhǔn)上，本文所提方法略遜于BFWFCM算法，但優(yōu)于MFC算法。從表5中，可以清楚地看到：在迭代次數(shù)上，本文所提算法略遜于MFC算法，但明顯優(yōu)于BFWFCM算法；在分配系數(shù)(PC)、劃分熵(PE)度量標(biāo)準(zhǔn)上，本文所提方法略優(yōu)于上述兩種算法。而在目標(biāo)函數(shù)(OF)度量標(biāo)準(zhǔn)上，本文所提算法顯著優(yōu)于其他兩個(gè)算法，得到最好的聚類效果。

表4　Iris數(shù)據(jù)集的聚類結(jié)果比較

表5　Wine數(shù)據(jù)集的聚類結(jié)果比較

2.4實(shí)驗(yàn)3屬性加權(quán)測(cè)試集

這個(gè)實(shí)驗(yàn)主要用來(lái)測(cè)試描述每個(gè)數(shù)據(jù)元素的屬性在聚類中的貢獻(xiàn)度，依據(jù)屬性加權(quán)顯示。文獻(xiàn)[6]提出一種基于高斯混合分布的屬性加權(quán)測(cè)試集，每一個(gè)屬性加權(quán)測(cè)試集包含50個(gè)數(shù)據(jù)元素，每一數(shù)據(jù)元素有5個(gè)屬性組成，其中2個(gè)屬性相關(guān)，與剩余3個(gè)屬性無(wú)關(guān)。兩個(gè)屬性的相關(guān)值通過(guò)K(K=2)分量高斯混合模型(參數(shù)：均值分別為μ1=(0,0),μ2=(0,3)，協(xié)方差矩陣都等于2維單位矩陣，即∑1=∑2=I2)得到。剩余三個(gè)屬性的相關(guān)值通過(guò)隨機(jī)變量(參數(shù)：均值為0，方差為1)得到。圖3描述了這兩個(gè)相關(guān)屬性的分布情況。

圖3　″*″代表第一聚類數(shù)據(jù)元素以及″○″代表第二聚類數(shù)據(jù)元素

3種算法分別對(duì)這個(gè)屬性加權(quán)測(cè)試集進(jìn)行聚類，聚類效果見(jiàn)表6所示。需要補(bǔ)充的是：在最后的屬性加權(quán)里，兩個(gè)相關(guān)屬性加權(quán)在前，三個(gè)無(wú)關(guān)屬性在后。

表6　屬性加權(quán)測(cè)試集的聚類結(jié)果比較

這部分只針對(duì)屬性加權(quán)的結(jié)果。由圖3可知：第一相關(guān)屬性在聚類上不起作用，相反，第二相關(guān)屬性在聚類上起決定性作用。就這點(diǎn)而言，本文方法產(chǎn)生的加權(quán)結(jié)果表現(xiàn)最為突出。后三個(gè)無(wú)關(guān)屬性與第一相關(guān)屬性作用相同，所以加權(quán)也應(yīng)該相同且接近為0。同時(shí)不難發(fā)現(xiàn)，F(xiàn)CM算法、BFWFCM算法得到的屬性加權(quán)不符合實(shí)際。其他四個(gè)度量標(biāo)準(zhǔn)在此不在贅述。

通過(guò)以上三個(gè)實(shí)驗(yàn)結(jié)果可以看出，在上表所列的四個(gè)衡量系數(shù)以及屬性加權(quán)上，本文所提算法總體上要顯著優(yōu)于模糊C均值聚類算法以及文獻(xiàn)[9]提出的加權(quán)模糊C均值聚類算法。

2.5實(shí)驗(yàn)4彩色圖像集

本文所提的屬性加權(quán)聚類算法中，參數(shù)設(shè)置如下：(1) 模糊度系數(shù)m=2；(2) 終止準(zhǔn)則ε=0.00001；(3) 采取文獻(xiàn)[9]設(shè)置的參數(shù)系數(shù)。在圖像樹中，c=3；在圖像褲子中，c=4，以及在圖像衣服中，c=3；(4) 設(shè)置Bootstrap方法中的B=200。此外，本文還選取了另外一幅圖像，奶牛作為實(shí)驗(yàn)圖像，它取c=3，如圖7所示。通常，原始圖像的表達(dá)空間是RGB顏色空間，但是在許多彩色圖像的應(yīng)用領(lǐng)域研究表明[13]：跟RGB彩色空間相比，把圖像映射到CIELAB彩色空間更有利于對(duì)圖像進(jìn)行處理。最后，這些圖像的分割結(jié)果分別見(jiàn)圖4-圖7所示。

圖4　樹

圖5　褲子

圖6　衣服

圖7　奶牛

從圖4實(shí)驗(yàn)結(jié)果明顯看出，Bootstrap方法把天空分割成兩部分，而把目標(biāo)對(duì)象與土坡當(dāng)成同一對(duì)象進(jìn)行了分割。而本文所提方法與經(jīng)典FCM方法卻分別把天空，樹(目標(biāo)對(duì)象)，土坡分別分割出來(lái)，但就目標(biāo)對(duì)象(樹)而言，本文所提算法得到了目標(biāo)對(duì)象更加具體，即樹干和樹枝有更加明顯的區(qū)分。

從圖5的實(shí)驗(yàn)結(jié)果可以明顯看出，Bootstrap方法把褲子上的小黑色區(qū)域分割成兩部分，不符合原圖像。而本文所提方法與經(jīng)典FCM方法效果相當(dāng)。

從圖6的實(shí)驗(yàn)結(jié)果可以明顯看出，Bootstrap方法沒(méi)能把上面腰部那條紅色的帶子分割成功。而本文所提方法與經(jīng)典FCM方法卻能清楚地分割成功，但從顏色深淺來(lái)說(shuō)，本文方法明顯優(yōu)于經(jīng)典FCM方法。

從圖7的實(shí)驗(yàn)結(jié)果可以明顯看出，經(jīng)典FCM方法把奶牛與自己在草地的影子分割為一個(gè)整體，這明顯是不準(zhǔn)確的。而Bootstrap方法與本文所提方法卻清楚地把奶牛分割成一個(gè)完整的整體。但是，Bootstrap方法由于受到光照的影響，把奶牛大腿部分的陰影部分分割到背景上去，而本文所提方法分割得到的奶牛更完整一些，說(shuō)明光照對(duì)本文所提算法的分割影響較小。同時(shí)，通過(guò)圖7與圖4-圖6的比較可知，這幅圖像的像素點(diǎn)總數(shù)平均是它們的9倍左右，同時(shí)仍然取得明顯的效果，說(shuō)明本文所提算法在圖像的擴(kuò)展方面也具有良好的性能。此外，從實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)，Bootstrap方法分割圖像所耗時(shí)間遠(yuǎn)遠(yuǎn)大于經(jīng)典FCM算法與本文所提算法，即時(shí)間復(fù)雜度較大，但它不是本文討論的重點(diǎn)，所以這里不再贅述。

3結(jié)語(yǔ)

由實(shí)驗(yàn)結(jié)果可知，本文所提算法在保證模糊C均值聚類算法優(yōu)點(diǎn)的同時(shí)，提高了聚類效果與圖像分割的效果。今后將繼續(xù)研究模糊聚類在圖像分割中的應(yīng)用，同時(shí)著重挖掘圖像的屬性信息，比如考慮圖像的空間信息、多張圖像的共有屬性等。

參考文獻(xiàn)

[1] 常茜茜,張?jiān)虑?一種基于劃分的混合數(shù)據(jù)聚類算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(6):154-157.

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

[3] 李麗娟,唐文紀(jì).基于人工免疫網(wǎng)絡(luò)和模糊C-均值聚類的入侵檢測(cè)方法[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(3):282-284,299.

[4] 陳志飛,時(shí)宏偉,呂學(xué)斌,等.基于均值漂移和模糊C均值聚類的圖像分割算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(11):13-17.

[5] Huang J Z,Ng M K,Hongqiang R,et al.Automated variable weighting in k-means type clustering[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2005,27(5):657-668.

[6] Tsai C Y,Chiu C C.Developing a feature weight self-adjustment mechanism for a K-means clustering algorithm[J].Computational Statistics & Data Analysis,2008,52(10):4658-4672.

[7] Lim Y B,Park Y J,Huh M H.D-optimality criterion for weighting variables in K-means clustering[J].Journal of the Korean Statistical Society,2009,38(4):391-396.

[8] Liping J,Ng M K,Huang J Z.An Entropy Weighting K-means Algorithm for Subspace Clustering of High-Dimensional Sparse Data[J].Knowledge and Data Engineering,IEEE Transactions on,2007,19(8):1026-1041.

[9] Hung W L,Yang M S,Chen D H.Bootstrapping approach to feature-weight selection in fuzzy c-means algorithms with an application in color image segmentation[J].Pattern Recognition Letters,2008,29(9):1317-1325.

[10] 邊肇祺,張學(xué)工.模式識(shí)別[M].2版.北京:清華大學(xué)出版社,2000:87-90.

[11] Wang X,Wang Y,Wang L.Improving fuzzy c-means clustering based on feature-weight learning[J].Pattern Recognition Letters,2004,25(10):1123-1132.

[12] Bezdek J C.Cluster Validity with Fuzzy Sets[J].Journal of Cybernetics,1973,3(3):58-73.

[13] Kim D,Lee K,Lee D.A novel initialization scheme for the fuzzy c-means algorithm for color clustering[J].Pattern Recognition Letters,2004,25(2):227-237.

收稿日期：2015-01-21。呂梁學(xué)院校內(nèi)自然科學(xué)基金項(xiàng)目(zrxn 201308)。薛艷鋒，講師，主研領(lǐng)域：數(shù)據(jù)挖掘。劉繼華，副教授。高永強(qiáng)，講師。高志娥，助教。武彩紅，助教。

中圖分類號(hào)TP311

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.07.062

A WEIGHTED FUZZY C-MEANS CLUSTERING ALGORITHM AND ITS APPLICATION IN IMAGE SEGMENTATION

Xue YanfengLiu JihuaGao YongqiangGao ZhieWu Caihong

(DepartmentofComputerScienceandTechnology,LvliangUniversity,Lvliang033000,Shanxi,China)

AbstractIn existing weighted fuzzy C-means clustering algorithm, attribute weighting is a process of ongoing iteration and repeated calculation, which is time-consuming and laborious. In view of this situation, we proposed to use Fisher linear discriminant rate in attribute weighting. First, the algorithm calculates directly the contribution degree of every dimension attribute on fuzzy clustering; secondly it makes the normalisation processing on the contribution degrees of all attributes followed by weighted clustering. The experiments carried out on artificial and real datasets show that while improving the clustering speed, the method has the superiority over other similar weighted fuzzy C-means clustering algorithm in terms of clustering effect.

KeywordsFuzzy C-means clusteringFisher’s linear discriminantAttribute weightingDistribution coefficient partitionEntropyDegree of membershipColour image segmentationColour spaces