一種加權模糊C均值聚類算法及其在圖像分割中的應用

薛艷鋒　劉繼華　高永強　高志娥　武彩紅

(呂梁學院計算機科學與技術系　山西 呂梁 033000)

?

一種加權模糊C均值聚類算法及其在圖像分割中的應用

薛艷鋒劉繼華高永強高志娥武彩紅

(呂梁學院計算機科學與技術系山西 呂梁 033000)

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

關鍵詞模糊C均值聚類Fisher線性判別率屬性加權分配系數劃分熵隸屬度彩色圖像分割顏色空間

0引言

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

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

(1)

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

(2)

(3)

終止條件為：

(4)

其中，ε為終止準則；k為迭代次數。詳細步驟如下：

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

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

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

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

由于各個屬性對聚類的貢獻程度不等，所以需要為各個屬性賦予對應的權重[5-8]，文獻[9]采用的Bootstrap方法證明了屬性加權對聚類效果作用明顯。

Bootstrap方法需要重復選取不斷調整屬性權重直到聚類結束，或者需要通過計算大量的屬性加權最后求取平均值。本文采用基于Fisher線性判別率的方法無需迭代直接計算各屬性權重，在減少迭代次數的基礎上提高了聚類效果。

1基于Fisher準則的屬性加權模糊C均值聚類

1.1Fisher線性判別率

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

(5)

(6)

(7)

(8)

(9)

Jfisher就是Fisher線性判別率，值越大，說明該維屬性對聚類的影響越明顯，應該賦予更大的加權系數。

1.2基于Fisher準則的屬性加權模糊C均值聚類

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

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

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

(3) 通過模糊劃分矩陣U的最大值，指派對應數據元素屬于C個聚類中的某一類。其次，通過Fisher線性判別率計算各個屬性分量在聚類中的貢獻度Jfisher，進而計算出各個屬性權重W′：

(10)

(4) 依據公式：

(11)

(12)

更新模糊劃分矩陣U。

(5) 計算目標函數

(13)

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

2實驗結果

2.1度量標準

聚類有效性函數[11]主要從不同方面衡量聚類的效果。近來十幾年，出現了諸多的聚類有效性函數作為度量標準，其中最重要的兩種度量標準分別針對數據元素集合的模糊劃分以及數據元素集合的幾何結構。

針對數據元素集合模糊劃分標準的主要思想是：劃分的模糊度越小，聚類效果越好。這類度量標準的兩個代表函數分別是分配系數Vpc[12]以及劃分熵Vpe[11]：

(14)

(15)

2.2實驗1人造數據集

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

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

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

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

2.3實驗2標準數據集

繼續選擇兩個著名的真實數據集Iris和Wine進行測試，情況描述見表3所示。

表3　兩類真實數據集

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

表4　Iris數據集的聚類結果比較

表5　Wine數據集的聚類結果比較

2.4實驗3屬性加權測試集

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

圖3　″*″代表第一聚類數據元素以及″○″代表第二聚類數據元素

3種算法分別對這個屬性加權測試集進行聚類，聚類效果見表6所示。需要補充的是：在最后的屬性加權里，兩個相關屬性加權在前，三個無關屬性在后。

表6　屬性加權測試集的聚類結果比較

這部分只針對屬性加權的結果。由圖3可知：第一相關屬性在聚類上不起作用，相反，第二相關屬性在聚類上起決定性作用。就這點而言，本文方法產生的加權結果表現最為突出。后三個無關屬性與第一相關屬性作用相同，所以加權也應該相同且接近為0。同時不難發現，FCM算法、BFWFCM算法得到的屬性加權不符合實際。其他四個度量標準在此不在贅述。

通過以上三個實驗結果可以看出，在上表所列的四個衡量系數以及屬性加權上，本文所提算法總體上要顯著優于模糊C均值聚類算法以及文獻[9]提出的加權模糊C均值聚類算法。

2.5實驗4彩色圖像集

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

圖4　樹

圖5　褲子

圖6　衣服

圖7　奶牛

從圖4實驗結果明顯看出，Bootstrap方法把天空分割成兩部分，而把目標對象與土坡當成同一對象進行了分割。而本文所提方法與經典FCM方法卻分別把天空，樹(目標對象)，土坡分別分割出來，但就目標對象(樹)而言，本文所提算法得到了目標對象更加具體，即樹干和樹枝有更加明顯的區分。

從圖5的實驗結果可以明顯看出，Bootstrap方法把褲子上的小黑色區域分割成兩部分，不符合原圖像。而本文所提方法與經典FCM方法效果相當。

從圖6的實驗結果可以明顯看出，Bootstrap方法沒能把上面腰部那條紅色的帶子分割成功。而本文所提方法與經典FCM方法卻能清楚地分割成功，但從顏色深淺來說，本文方法明顯優于經典FCM方法。

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

3結語

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

參考文獻

[1] 常茜茜,張月琴.一種基于劃分的混合數據聚類算法[J].計算機應用與軟件,2014,31(6):154-157.

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

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

[4] 陳志飛,時宏偉,呂學斌,等.基于均值漂移和模糊C均值聚類的圖像分割算法[J].計算機應用與軟件,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] 邊肇祺,張學工.模式識別[M].2版.北京:清華大學出版社,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。呂梁學院校內自然科學基金項目(zrxn 201308)。薛艷鋒，講師，主研領域：數據挖掘。劉繼華，副教授。高永強，講師。高志娥，助教。武彩紅，助教。

中圖分類號TP311

文獻標識碼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