一種協同的可能性模糊聚類算法

譚欣，徐蔚鴻

長沙理工大學計算機與通信工程學院，長沙 410004

一種協同的可能性模糊聚類算法

譚欣，徐蔚鴻

長沙理工大學計算機與通信工程學院，長沙 410004

模糊C-均值聚類（FCM）對噪聲數據敏感和可能性C-均值聚類（PCM）對初始中心非常敏感易導致一致性聚類。協同聚類算法利用不同特征子集之間的協同關系并與其他算法相結合，可提高原有的聚類性能。對此，在可能性C-均值聚類算法（PCM）基礎上將其與協同聚類算法相結合，提出一種協同的可能性C-均值模糊聚類算法（C-FCM）。該算法在改進的PCM的基礎上，提高了對數據集的聚類效果。在對數據集Wine和Iris進行測試的結果表明，該方法優于PCM算法，說明該算法的有效性。

可能性C-均值聚類（PCM）；模糊C均值（FCM）；協同模糊聚類

1 引言

以上聚類算法都是根據數據集的所有特征進行聚類的，每個特征的權值是不同的。若能充分利用特征之間的關系，則聚類的結果會更加精確。協同模糊聚類[15]是一種利用不同特征子集之間的協同關系進行聚類的一種方法。這種方法可與其他的聚類算法相結合，從而提高聚類效果。利用不同特征子集之間的協同系數，得到模糊劃分矩陣。優于模糊劃分矩陣受不同子集間協同系數的影響，因此要比其他的模糊聚類算法得到的模糊劃分矩陣精確、聚類效果好。

本文在上述工作的基礎上，對UMPFCA算法進行改進，將協同模糊聚類算法和UMPFCA算法相結合，并將其用于標準數據集的測試，使得聚類性能得到提高。

2 隸屬關系不確定的可能性模糊聚類算法

UMPFCA算法將改進的FCM算法與兩個新的隸屬度參數tik、pik進行融合，其目標函數如下所示：

不確定隸屬度pik的優點在于有記憶功能，每次迭代中更新數據對象與最近距離聚類間的隸屬度值，其他隸屬度保持上一次迭代的數值，這樣可以“記憶”以前歷次迭代過程中的pik，此算法中的不確定性不同于一般概念的不確定性，只有當不同聚類的隸屬度都為1時才被定義為不確定性隸屬度關系。T，P，V分別為可能隸屬度矩陣、不確定性隸屬度矩陣及聚類中心矩陣，r為可能性權重指數，r∈(1，∞)。dik表示樣本xk與第i類聚類中心Vi之間的歐式距離度量。

根據拉格朗日極值方法求得可能隸屬度：

度不會受到其他聚類中心的牽制。

不確定隸屬度關系為在聚類算法迭代過程中，當數據集X中第k個數據樣本xk對C個聚類中第i個類的隸屬度相等的情形，即存在如下情況：

其中，C為聚類個數，表示樣本xk對i個聚類ci(1＜i≤c)的隸屬關系是不確定的。目前在值域μ上變量取值的分布形式可以分成兩種分布情況：概率性分布和可能性分布。在聚類方法中可以分布對應模糊性理論和可能性理論，這兩個分布之間有著不同之處，可能性分布取消了概率性分布的約束條件。以上出現的不確定性分布與這兩種分布之間有本質區別。不確定模糊聚類算法不同于一般的模糊聚類算法，該算法體現了數據對象對聚類簇隸屬關系亦此亦彼的不確定性。

3 協同的可能性模糊聚類算法

協同模糊聚類[14]在普通聚類算法的基礎上，將數據的特征分成不同的p個特征子集。每個特征子集的向量個數要相等，并確定不同特征子集之間的協同系數β[ii，kk]，根據協同系數確定不同子集的模糊劃分矩陣和原形矩陣。不同特征子集之間的關系強度由協同系數確定，協同系數越大，特征子集之間的協同關系就越強，對模糊劃分矩陣和原形矩陣的影響越大；反之，協同系數越小，則相反。

根據此方法，在UMPFCA目標函數的基礎上，考慮不同特征子集的模糊劃分矩陣之間的協同關系，為此提出如下目標函數：其中，第一部分為UMPFCA目標函數，第二部分是根據各個特征子集的模糊劃分矩陣之間的關系而確定。β[ii，jj]是特征子集ii與特征子集jj之間的協同系數矩陣。

根據拉格朗日求極值方法給出vst[ii]的計算公式，首先構造拉格朗日函數V[ii]：

值得注意的是，初始化聚類中心在根據式（6）計算時，需要比隨機選取較真實的聚類中心，這樣能得到較合理的權值。即先通過FCM得到近似聚類中心，然后使用UMPFCA算法計算其可能隸屬度，則得到的以下算法稱為C-FCA算法。

C-FCA算法基本分為兩個部分：

步驟1初始化過程。對中心矩陣V(0)和可能隸屬度矩陣T(0)、非確定性隸屬度矩陣P(0)以及一些參數初始化。

步驟2計算中心矩陣V(0)和可能隸屬度矩陣T(0)、非確定性隸屬度矩陣P(0)。通過內循環和外循環迭代使得兩次迭代中心矩陣V(0)差值小于閾值或迭代次數大于TS1，TS2為止。

4 實驗結果

為了檢驗此算法的聚類有效性，使用FCM、WFCM、UMPFCA、C-FCA算法對UCI機器學習庫中常被用來檢驗聚類算法性能的IRIS、Wine數據集進行聚類，用MATLAB7.0編程實現。

IRIS數據是包含3類鳶尾植物Setosa、versicolor、virginica的隨機樣本，每一類有50個表示IRIS的花瓣長（Petal length）、花瓣寬（Petal width）、萼片長（Sepal length）、萼片寬（Sepal width）的四維空間的樣本組成。該數據集的相關資料中的IRIS數據的類中心為(V1= (5.00，3.42，1.46，0.24)，V2=(5.93，2.77，4.26，1.32)，V3= (6.58，2.97，5.55，2.02))。Wine數據集是178個樣本構成。

下面用FCM、WFCM、UMPFCA、C-FCA這四種聚類算法對IRIS和Wine數據集進行測試。C-FCA算法中：設置最大迭代次數T1=T2=100，閾值ε=0.01，協同系數β[1.2]=β[2.1]=0.1。IRIS數據集的結果如表1所示。

表1 IRIS數據集上四種聚類算法的聚類結果對比1）

在IRIS中，第一類和其他兩類完全分離，第二類和第三類有重疊。從表1中可以得到對于IRIS數據，PCM算法最終的誤分數僅有10個，但第2個與第3個聚類中心幾乎出現了重合，與實際的聚類中心有偏差。UMPFCA有較高的正確率，聚類中心更加接近于真實的聚類中心。C-FCA因為協同系數的影響，得到了較高的準確率。同時C-FCA在聚類結果較好的PCM算法基礎上，正確聚類數據進一步提高到96%。表2為FCM、UMPFCA、C-FCA算法對Wine數據集的正確聚類結果。

表2 Wine數據集上三種聚類算法的聚類結果對比

可以看出對于Wine數據集，C-FCA正確聚類的數據點數目為140，聚類結果較好，UMPFCA只有110正確聚類結果。C-FCA的正確率達到78.65%。從實驗結果可以看到，三種聚類算法中C-FCA聚類算法最好。

二維的IRIS數據集原始分布圖如圖1所示。

圖1 二維的IRIS數據集原始分布圖

圖2是協同系數β[1，2]=β[2，1]=0.1時的實驗結果，協同系數β的取值會影響聚類性能：影響算法的效率。不同值時的結果進行比較如表3，從表中可以看出β取值大于等于0.3時，正確聚類數據的百分比很低。當協同系數取值小于0.08時，聚類結果變動不明顯。當取值在[0.08，0.25]區間上，正確聚類數目的百分比為95%，到達最好的聚類結果。

表3 取不同值對IRIS聚類的不同結果比較

圖2 二維的IRIS數據集采用三種算法的聚類效果

在對數據集進行C-FCA算法之前，要先對數據集經過特征選擇，IRIS數據集有兩個特征子集，分別為2，1，3和2，3，4。經過β取大量的值，當協同系數不斷增加時，δ在（0.665，0.669）之間，Δ趨于穩定，所以當協同系數在一定程度上不斷增加時，不會影響到δ和Δ，UMFCA和C-FCA算法對IRIS的第二類和第三類的隸屬度矩陣的分布情況如圖3，圖4所示。圖4的C-FCA算法得到的同一數據屬于兩類的隸屬度差別更大，較好地描述了聚類的效果。

圖3 UMPFCA

圖4 C-FCA

為了驗證算法聚類，引入兩個準則來對協同系數與隸屬度矩陣的關系進行有效性測度。這里引進評估聚類的影響，在后文中對沒有任何協同影響作為對比。

在數據集之間，引入數據集1和2協同的影響用兩種方式在圖中展示，同樣的，標記的1-ref和2-ref表示沒有任何協同的作用。首先，表達兩個劃分矩陣的兩個特征子集受到協同系數的影響隸屬度矩陣的差距，特征子集的劃分矩陣分別表示為：U1=[μik[1]]和U2=[μik[2]]。

那么測度函數就是：

顯而易見，協同作用越強，即β越大時，δ的值越小，因此，這個參數可以分析協同參數對隸屬度的有效影響。協同作用是對稱的，β[1，2]=β[2，1]。它反映了數據集被其他模式子集的協同影響。比如，對于數據集結構之間很大不同，那么隨著β值的增加δ值就沒有變化。

第二個準則是考慮到兩個未經過協同計算得到的隸屬度矩陣，經過協同聚類計算得到的協同隸屬度矩陣和未經過協同計算得到的普通隸屬度矩陣的差值與協同系數之間的關系，即

上述的兩個測度函數體現了全局特征，那么方便研究單獨的特征子集和數據集整體結構。其結果對定義隸屬度變化被協同的影響很大而結構在所有數據集中是相容的。

5 結論

本文將UMPFCA算法進行改進，并將其同協同模糊聚類相結合，提出了一種協同的可能性模糊聚類算法（C-FCA）。利用協同模糊聚類在隸屬度上的優勢和UMPFCA對聚類簇隸屬度關系亦此亦彼的不確定上的優勢，通過該方法對數據集進行檢驗，實驗結果表明該方法是非常有效的。但本文提出的聚類算法同樣存在一些問題，數據量大導致計算量大，費時，協同系數要根據經驗確定，且需要大量實驗得出合適的值。選擇特征子集的參數對數據檢驗也會影響到最后結果，這些方向的問題有待于進一步的研究。

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008，19（1）：48-61.

[2]Kirindis S，Chatzis V.A robust fuzzy local information c-means clusteringalgorithm[J].IEEE Trans onImage Process，2010，19（5）：1328-1337.

[3]Cai W，Chen S，Zhang D.Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J].Pattern Recognition，2007，40（3）：825-838.

[4]張敏，于劍.基于劃分的模糊聚類算法[J].軟件學報，2004，15（6）.

[5]田軍委，黃永宣，于亞琳.基于熵約束的快速FCM聚類多閾值圖像分割算法[J].模式識別與人工智能，2008，21（21）：221-226.

[6]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].New York：Plenum，1981.

[7]Pal N R，Pal K，Bezdek J C.A new hybrid c-means clustering model[C]//Proc of the IEEE Int Conf on Fuzzy Systems.Piscataway：IEEE Press，2004：179-184.

[8]高新波.模糊聚類分析及其應用[M].西安：西安電子科技大學出版社，2004.

[9]宋魚慶.醫學圖像數據挖掘若干技術研究[D].南京：東南大學，2005.

[10]Setnets M.Supervised fuzzy clustering for rule extraction[J].IEEE Trans on Fuzzy Systems，2000，8（4）：416-424.

[11]Krishnapuram R，Keller J M.A possibilistic approach to clustering[J].IEEE Trans on Fuzzy Systems，1993，1（2）：98-110.

[12]劉兵，夏士雄.基于樣本加權的可能性模糊聚類算法[J].電子學報，2012，40（2）：371-375.

[13]Pal N R，Pal K，Bezdek J C.A possibilistic fuzzy c-means clusting alogorithm[J].IEEE Trans on Fuzzy Systems，2005，13（4）：517-530.

[14]陳健美，路虎，宋余慶，等.一種隸屬關系不確定的可能性模糊聚類方法[J].計算機研究與發展，2008，45（9）：1486-1492.

[15]Pedrycz W.Collaborative fuzzy clustering[J].Pattern Recognition Letters，2002，23（14）：173-186.

[16]祁宏宇，吳小俊，王士同，等.一種協同的FCPM模糊聚類算法[J].模式識別與人工智能，2010，23（1）：120-125.

TAN Xin,XU Weihong

School of Computer&Communication Engineering,Changsha University of Science&Technology,Changsha 410004,China

Fuzzy C-Means（FCM）algorithm is sensitive to noise and Possibilistic C-Means（PCM）algorithm is very sensitive to the initialization of cluster center and generates coincident clusters.With the collaborative relations among different feature subsets,the collaborative fuzzy clustering is combined with other clustering algorithms to make its clustering result better than that of the one with the original algorithm.An improved fuzzy clustering algorithm is proposed based on the combination of PCM and collaborative fuzzy clustering.The experimental results on the data sets show the effectiveness of the proposed method.

Possibilistic C-Means clustering（PCM）;Fuzzy C-Means（FCM）;collaborative fuzzy clustering

A

TP311

10.3778/j.issn.1002-8331.1211-0251

TAN Xin,XU Weihong.Collaborative PCM fuzzy clustering algorithm.Computer Engineering and Applications, 2014,50（21）：147-151.

國家教育部重點科研項目（No.208098）；湖南省科技計劃項目（No.2012FJ3005）。

譚欣（1988—），女，碩士研究生，主要研究方向：人工智能與圖像處理；徐蔚鴻（1963—），男，教授，博士生導師，主要研究方向：模式識別，人工智能，圖像處理。E-mail：tanxincl@163.com

2012-11-21

2013-02-25

1002-8331（2014）21-0147-05

CNKI出版日期：2013-05-13，http://www.cnki.net/kcms/detail/11.2127.TP.20130513.1601.006.html