一種協(xié)同的可能性模糊聚類算法

譚欣，徐蔚鴻

長沙理工大學(xué)計算機(jī)與通信工程學(xué)院，長沙 410004

一種協(xié)同的可能性模糊聚類算法

譚欣，徐蔚鴻

長沙理工大學(xué)計算機(jī)與通信工程學(xué)院，長沙 410004

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

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

1 引言

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

本文在上述工作的基礎(chǔ)上，對UMPFCA算法進(jìn)行改進(jìn)，將協(xié)同模糊聚類算法和UMPFCA算法相結(jié)合，并將其用于標(biāo)準(zhǔn)數(shù)據(jù)集的測試，使得聚類性能得到提高。

2 隸屬關(guān)系不確定的可能性模糊聚類算法

UMPFCA算法將改進(jìn)的FCM算法與兩個新的隸屬度參數(shù)tik、pik進(jìn)行融合，其目標(biāo)函數(shù)如下所示：

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

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

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

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

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

3 協(xié)同的可能性模糊聚類算法

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

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

根據(jù)拉格朗日求極值方法給出vst[ii]的計算公式，首先構(gòu)造拉格朗日函數(shù)V[ii]：

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

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

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

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

4 實驗結(jié)果

為了檢驗此算法的聚類有效性，使用FCM、WFCM、UMPFCA、C-FCA算法對UCI機(jī)器學(xué)習(xí)庫中常被用來檢驗聚類算法性能的IRIS、Wine數(shù)據(jù)集進(jìn)行聚類，用MATLAB7.0編程實現(xiàn)。

IRIS數(shù)據(jù)是包含3類鳶尾植物Setosa、versicolor、virginica的隨機(jī)樣本，每一類有50個表示IRIS的花瓣長（Petal length）、花瓣寬（Petal width）、萼片長（Sepal length）、萼片寬（Sepal width）的四維空間的樣本組成。該數(shù)據(jù)集的相關(guān)資料中的IRIS數(shù)據(jù)的類中心為(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數(shù)據(jù)集是178個樣本構(gòu)成。

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

表1 IRIS數(shù)據(jù)集上四種聚類算法的聚類結(jié)果對比1）

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

表2 Wine數(shù)據(jù)集上三種聚類算法的聚類結(jié)果對比

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

二維的IRIS數(shù)據(jù)集原始分布圖如圖1所示。

圖1 二維的IRIS數(shù)據(jù)集原始分布圖

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

表3 取不同值對IRIS聚類的不同結(jié)果比較

圖2 二維的IRIS數(shù)據(jù)集采用三種算法的聚類效果

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

圖3 UMPFCA

圖4 C-FCA

為了驗證算法聚類，引入兩個準(zhǔn)則來對協(xié)同系數(shù)與隸屬度矩陣的關(guān)系進(jìn)行有效性測度。這里引進(jìn)評估聚類的影響，在后文中對沒有任何協(xié)同影響作為對比。

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

那么測度函數(shù)就是：

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

第二個準(zhǔn)則是考慮到兩個未經(jīng)過協(xié)同計算得到的隸屬度矩陣，經(jīng)過協(xié)同聚類計算得到的協(xié)同隸屬度矩陣和未經(jīng)過協(xié)同計算得到的普通隸屬度矩陣的差值與協(xié)同系數(shù)之間的關(guān)系，即

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

5 結(jié)論

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

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報，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].軟件學(xué)報，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]高新波.模糊聚類分析及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2004.

[9]宋魚慶.醫(yī)學(xué)圖像數(shù)據(jù)挖掘若干技術(shù)研究[D].南京：東南大學(xué)，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]劉兵，夏士雄.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報，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]陳健美，路虎，宋余慶，等.一種隸屬關(guān)系不確定的可能性模糊聚類方法[J].計算機(jī)研究與發(fā)展，2008，45（9）：1486-1492.

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

[16]祁宏宇，吳小俊，王士同，等.一種協(xié)同的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—），男，教授，博士生導(dǎo)師，主要研究方向：模式識別，人工智能，圖像處理。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