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

譚欣，徐蔚鴻

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

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

譚欣，徐蔚鴻

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

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

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

1 引言

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

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

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

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

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

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

度不會(huì)受到其他聚類中心的牽制。

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

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

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

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

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

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

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

C-FCA算法基本分為兩個(gè)部分：

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

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

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

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

IRIS數(shù)據(jù)是包含3類鳶尾植物Setosa、versicolor、virginica的隨機(jī)樣本，每一類有50個(gè)表示IRIS的花瓣長(zhǎng)（Petal length）、花瓣寬（Petal width）、萼片長(zhǎng)（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è)樣本構(gòu)成。

下面用FCM、WFCM、UMPFCA、C-FCA這四種聚類算法對(duì)IRIS和Wine數(shù)據(jù)集進(jìn)行測(cè)試。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é)果對(duì)比1）

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

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

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

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

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

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

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

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

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

圖3 UMPFCA

圖4 C-FCA

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

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

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

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

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

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

5 結(jié)論

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

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，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é)報(bào)，2004，15（6）.

[5]田軍委，黃永宣，于亞琳.基于熵約束的快速FCM聚類多閾值圖像分割算法[J].模式識(shí)別與人工智能，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é)報(bào)，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ì)算機(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].模式識(shí)別與人工智能，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.

國家教育部重點(diǎn)科研項(xiàng)目（No.208098）；湖南省科技計(jì)劃項(xiàng)目（No.2012FJ3005）。

譚欣（1988—），女，碩士研究生，主要研究方向：人工智能與圖像處理；徐蔚鴻（1963—），男，教授，博士生導(dǎo)師，主要研究方向：模式識(shí)別，人工智能，圖像處理。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