一種約束的改進(jìn)可能性C均值聚類方法研究

肖振球，曾文華

( 1.嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院，廣東 梅州 514015；2.廈門大學(xué)軟件學(xué)院，福建 廈門 361005)

?

一種約束的改進(jìn)可能性C均值聚類方法研究

肖振球1，曾文華2

( 1.嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院，廣東 梅州 514015；2.廈門大學(xué)軟件學(xué)院，福建 廈門 361005)

【目的】 針對(duì)改進(jìn)的可能性C均值聚類方法(IPCM)運(yùn)算效率低，難以處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，提出了一種約束的改進(jìn)可能性C均值聚類方法(CIPCM).【方法】 CIPCM方法采用多項(xiàng)式核將特征向量映射到一個(gè)隱性特征空間，便于處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；引入兩個(gè)成對(duì)約束集合，降低聚類迭代次數(shù)，提高運(yùn)算效率和抗干擾能力.實(shí)驗(yàn)采用國(guó)際公認(rèn)的UCI公共測(cè)試數(shù)據(jù)集，并用錯(cuò)分率指標(biāo)評(píng)測(cè)了目標(biāo)分類性能.【結(jié)果】 CIPCM方法的聚類錯(cuò)分率低，對(duì)噪聲的魯棒性強(qiáng).【結(jié)論】 CIPCM運(yùn)算效率比高于改進(jìn)可能性C均值聚類方法.

聚類；C均值；模糊C均值；可能性C均值；改進(jìn)的可能性C均值

聚類是一種無(wú)監(jiān)督的分類方法，依據(jù)各類目標(biāo)之間的相似性自動(dòng)進(jìn)行分類，廣泛應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別、圖像處理等領(lǐng)域[1].現(xiàn)有聚類方法主要分為四類：基于劃分的聚類方法、基于分層的聚類方法、基于密度的聚類方法和基于網(wǎng)格的聚類方法，目前應(yīng)用最為廣泛的是基于劃分的聚類方法[2].

劃分可以分為硬劃分和軟劃分兩類，硬劃分是將所有對(duì)象都嚴(yán)格地劃分到某一個(gè)類別中去，也即分類后的隸屬度只能0或1.C均值(C-means)[3]是目前應(yīng)用最為廣泛的基于硬劃分的聚類方法，其算法實(shí)現(xiàn)簡(jiǎn)單，運(yùn)算效率高，在圖像分割、目標(biāo)跟蹤等領(lǐng)域都已有成功應(yīng)用.然而，現(xiàn)實(shí)世界中許多對(duì)象是存在重疊的，難以嚴(yán)格地劃分到某一類別，于是出現(xiàn)了模糊聚類方法，這是一種軟劃分方法，劃分后的隸屬度在0～1之間，可以通過(guò)最近鄰原則轉(zhuǎn)換為硬劃分.模糊聚類的代表性方法是模糊C均值(fuzzy c-means，F(xiàn)CM)聚類方法[4]，模糊C均值聚類方法通過(guò)引入模糊權(quán)重指數(shù)，實(shí)現(xiàn)對(duì)象的模糊分類，幾何意義直觀且運(yùn)算效率高.但該方法對(duì)隸屬度的約束較為嚴(yán)格，導(dǎo)致算法對(duì)噪聲較為敏感.為了克服FCM算法對(duì)噪聲敏感的問(wèn)題，文獻(xiàn)[5]放寬了隸屬度約束條件，修正了目標(biāo)函數(shù)，提出了一種可能性C均值(possibilistic C-Means，PCM)聚類算法.IPCM方法通過(guò)放松隸屬度約束條件，可以降低噪聲對(duì)聚類的不利影響.但PCM算法對(duì)初始凝聚點(diǎn)比較敏感，而且聚類原型可能趨同.針對(duì)PCM算法的缺陷，文獻(xiàn)[6]改進(jìn)了PCM算法，改進(jìn)后的算法稱之為改進(jìn)可能性C均值(improved possibilistic C-Means，IPCM)算法.該方法將FCM和PCM方法相結(jié)合，是目前處理部分重疊和噪聲數(shù)據(jù)的有效聚類方法.但該方法處理球狀類型的簇時(shí)，運(yùn)算效率嚴(yán)重下降，而且不能處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu).文獻(xiàn)[7]則根據(jù)基因表達(dá)數(shù)據(jù)分析特征，提出評(píng)價(jià)方案和改進(jìn)策略，該算法提取基因特征點(diǎn)清晰，但也面臨自動(dòng)分析缺陷問(wèn)題.

針對(duì)IPCM方法運(yùn)算效率低和難以處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，本文提出一種約束IPCM方法，記為CIPCM(constrained improved possibilistic c-means)方法.本方法采用多項(xiàng)式核將特征向量映射到一個(gè)隱性特征空間，便于處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；通過(guò)引入必須相連和不可相連兩個(gè)成對(duì)約束集合，來(lái)提高運(yùn)算速度和降低噪聲干擾，最終提高聚類準(zhǔn)確率.

1 模糊聚類方法

模糊聚類是解決對(duì)象重疊問(wèn)題的有效方法之一，最具代表性的是FCM方法.給定一個(gè)數(shù)據(jù)集：X={x1,x2,…,xN},xi∈Rl,1≤i≤N.其中，N為數(shù)據(jù)集中特征向量總數(shù)，l為特征向量維數(shù).定義目標(biāo)函數(shù)為：

(1)

FCM算法通過(guò)最小化公式(1)，將數(shù)據(jù)集X劃分到C個(gè)模糊簇.在目標(biāo)函數(shù)最小化過(guò)程中，隸屬度和聚類中心的更新方式為

(2)

FCM方法通過(guò)引入模糊權(quán)重指數(shù)，實(shí)現(xiàn)對(duì)象的模糊分類，幾何意義直觀且運(yùn)算效率高.但該方法對(duì)隸屬度的約束較為嚴(yán)格，導(dǎo)致算法對(duì)噪聲較為敏感.

為降低噪聲影響，PCM方法放寬了隸屬度約束條件，修正后的目標(biāo)函數(shù)為：

(3)

通過(guò)放寬隸屬度約束條件，PCM方法可以降低噪聲對(duì)聚類的不利影響.然而，PCM算法對(duì)初始凝聚點(diǎn)比較敏感，而且聚類原型可能趨同.

IPCM方法將FCM和PCM方法相結(jié)合，得到新的目標(biāo)函數(shù)，為

(4)

IPCM可以有效處理數(shù)據(jù)重疊和噪聲干擾問(wèn)題.但在處理球狀類型的簇時(shí)，IPCM方法的運(yùn)算效率下降嚴(yán)重，而且難以處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu).

2 CIPCM方法

針對(duì)IPCM方法運(yùn)算效率低和難以處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，本文提出一種約束IPCM的方法，即CIPCM方法.CIPCM算法采用多項(xiàng)式核將特征向量映射到一個(gè)隱性特征空間，便于處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；引入必須相連和不可相連兩個(gè)成對(duì)約束集合，提高運(yùn)算效率和抗干擾能力.該方法的目標(biāo)函數(shù)可以表示為：

(5)

其中，S1是指必須相連約束集合，S2是指不可相連約束集合，約束結(jié)合的生成方法見(jiàn)表1.

(6)

公式(5)中，第一項(xiàng)為向量到聚類中心的球面距離的累加和，第二項(xiàng)用于增大典型度，避免噪聲干擾，第三項(xiàng)控制違反成對(duì)約束的花費(fèi)，用于提高運(yùn)算效率和抗干擾能力.

CIPCM方法的實(shí)現(xiàn)流程如圖1所示.對(duì)于輸入的數(shù)據(jù)集X={x1,x2,…,xN}、聚類數(shù)量C、核κ={κ1,κ2,…,κM}、每一次迭代的約束條件數(shù)量λ、總約束條件數(shù)量λtotal和噪聲閾值θ，經(jīng)過(guò)自適應(yīng)迭代過(guò)程，輸出模糊隸屬度矩陣U=[uci]，作為聚類結(jié)果.其中，成對(duì)約束集合的構(gòu)建思路是：

函數(shù)G(G,U(t),T(t),C,θ,λ)用于生成成對(duì)約束集合，偽代碼見(jiàn)表1.

圖1中，T、U、w和α的更新方式為：

表1 成對(duì)約束集合生成算法偽代碼

Tab.1Pseudocodefrompairwiseconstrainedset

輸入:X,U,T,C,θ,λ輸出:S1、S2過(guò)程:1.初始化:S(0)1=?、S(2)2=?;2.估計(jì)噪聲:Xtci={xi∈X:max(xi)≥θ,?c=1,2,…,C};3.forc=1:C4.Fc={xi∈Xtci≥θ:Uci≥Uc'i,?1≤c'≤C,c'≠c}5.endfor6.forc=1:C7.O(Fc,Fc')=∑xi∈FcUFc'min(uci,uc'i)2∑xi∈FcUFc'min(uci,uc'i)8.O(Fc)=1C-1∑Cc'=1,c'≠cO(Fc,Fc')9.endfor10.檢測(cè)重疊簇:Fm=argmaxFc,c=1,2,…,CO(Fc)11.forc=1:C且c≠m12.qc=λO(Fc,Fm)∑Cc'=1,c'≠cO(Fc,Fm)13.endfor14.forc=1:C且c≠m15.xm=argmaxxj∈Fmumj16.xc=argmaxxj∈Fcucj17.A=?18.fori=1:qc19.xa=argmaxxj∈Fm∪Fc,xj?Amin(umj,ucj)20.A=A∪xa21.查詢(xa,xm)的鏈接表lableam22.iflableam為必連23.S1=S1∪(xa,xm)24.else25.S2=S2∪(xa,xm)26.endif27.查詢(xa,xc)的鏈接表lableac28.iflableac為必連29.S1=S1∪(xa,xc)30.else31.S2=S2∪(xa,xc)32.endif

(7)

其中，

(8)

(9)

(10)

(11)

(12)

κk(xi,xj)=φk(xi)Tφk(xj)

(13)

其中，φk(x)為映射核，其與ψk(x)的關(guān)系為

(14)

每一個(gè)ψk(x)都可以將一個(gè)向量x轉(zhuǎn)換為一個(gè)L維的向量，這樣保證特征空間的所有映射具有相同的維數(shù).通過(guò)映射可以形成一個(gè)新的正交基，表示為：

(15)

基核采用簡(jiǎn)單的多項(xiàng)式核，表示為

κk(xi,xj)=(xiTxj+c)k

(16)

3 仿真試驗(yàn)與分析

3.1 試驗(yàn)數(shù)據(jù)庫(kù)和評(píng)價(jià)指標(biāo)

選用聚類方法評(píng)價(jià)常用的UCI公共數(shù)據(jù)集[8]中的4組典型數(shù)據(jù)庫(kù)來(lái)評(píng)測(cè)CIPCM方法的性能，實(shí)驗(yàn)數(shù)據(jù)集信息見(jiàn)表2.

圖1 CIPCM方法實(shí)現(xiàn)流程Fig.1 CIPCM method implementation process

表2 試驗(yàn)數(shù)據(jù)集信息Tab.2 Information of data set

另外，為了測(cè)試算法對(duì)噪聲的魯棒性，還對(duì)Iris數(shù)據(jù)集進(jìn)行加噪處理.文獻(xiàn)[9]中對(duì)Iris數(shù)據(jù)集中每一維特征數(shù)據(jù)上加入0.0～10.0的隨機(jī)數(shù)作為噪聲，以便測(cè)試算法的魯棒性.

評(píng)價(jià)指標(biāo)采用常用的錯(cuò)分率(MCR)指標(biāo)，表示為：

(17)

3.2 參數(shù)選取

本文方法相關(guān)參數(shù)的取值見(jiàn)表3.

聚類數(shù)量C與數(shù)據(jù)集中的類別數(shù)一致.

表3 相關(guān)參數(shù)取值Tab.3 The relative parameters

3.3 試驗(yàn)結(jié)果與分析

為評(píng)價(jià)CIPCM方法的性能，將CIPCM方法與FCM[4]、PCM[5]、IPCM[6]以及劉兵等[8]提出的樣本加權(quán)可能性模糊聚類(sample-weighted possibilistic fuzzy clustering，SWPFC)方法進(jìn)行對(duì)比測(cè)試.圖2-5給出了不同數(shù)據(jù)集下的錯(cuò)分率指標(biāo).

從圖2-5中可以明顯看出，CIPCM方法在4個(gè)測(cè)試數(shù)據(jù)集下的錯(cuò)分率指標(biāo)都是最低的，可見(jiàn)本方法優(yōu)于其他4種方法.

為評(píng)價(jià)CIPCM方法對(duì)噪聲的魯棒性，圖6對(duì)比了不同方法在加噪Iris數(shù)據(jù)集下的錯(cuò)分率指標(biāo).由圖6可見(jiàn)，加噪后CIPCM方法的錯(cuò)分率指標(biāo)基本不變，說(shuō)明CIPCM方法對(duì)噪聲的魯棒性較強(qiáng).

圖7給出了不同方法在各測(cè)試數(shù)據(jù)集下分類一個(gè)目標(biāo)的平均時(shí)間花費(fèi)對(duì)比，單位為毫秒(ms).其中，實(shí)驗(yàn)所用的計(jì)算機(jī)平臺(tái)為：AMD A6 3.6G CPU、8G RAM、Windows 7.由圖7可見(jiàn)，CIPCM方法的處理速度與SWPFC方法相當(dāng)，比IPCM方法快.盡管比FCM和PCM方法慢，但錯(cuò)分率指標(biāo)要遠(yuǎn)高于這兩種方法.綜合評(píng)價(jià)認(rèn)為CIPCM方法的性能較優(yōu).

圖2 Iris數(shù)據(jù)集下不同方法的錯(cuò)分率指標(biāo)Fig.2 Error rate of different methods under Iris data set

圖3 Heart數(shù)據(jù)集下不同方法的錯(cuò)分率指標(biāo)Fig.3 Error rate of different methods under Heart data set

圖4 Breast數(shù)據(jù)集下不同方法的錯(cuò)分率指標(biāo)Fig.4 Error rate of different methods underBreast data set

圖5 Ionosphere數(shù)據(jù)集下不同方法的錯(cuò)分率指標(biāo)Fig.5 Error rate of different methods under Ionosphere data set

圖6 加噪Iris數(shù)據(jù)集下不同方法的錯(cuò)分率指標(biāo)Fig.6 Error rate of different methods under the Iris data set

圖7 不同方法的時(shí)間花費(fèi)對(duì)比Fig.7 Time spent on different methods

4 討論與結(jié)論

針對(duì)FCM方法對(duì)噪聲比較敏感，PCM算法對(duì)初始凝聚點(diǎn)比較敏感且聚類原型可能趨同，IPCM方法運(yùn)算效率低和難以處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，提出了一種CIPCM方法.通過(guò)在國(guó)際通用的UCI公共測(cè)試數(shù)據(jù)集上進(jìn)行性能對(duì)比，證明本文方法的錯(cuò)分率指標(biāo)高于其他方法，且對(duì)噪聲的魯棒性更強(qiáng)；同時(shí)，新方法的運(yùn)算效率高于IPCM方法，但仍有待繼續(xù)提高.另外，相關(guān)參數(shù)的自適應(yīng)學(xué)習(xí)也是下一步研究的方向.

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

[2] 張敏,于劍.基于劃分的模糊聚類算法[J].軟件學(xué)報(bào),2004,15(6):858-868

[3] 張運(yùn)楚,梁自澤,李恩,等.基于C-均值聚類的視覺(jué)監(jiān)控背景圖像構(gòu)建算法[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(14):45-47

[4] Bezdek J C,Ehrlich R.FCM:The fuzzy c-means clustering algorithm[J].Computers & Geosciences,2014(84):191-203

[5] Krishnapuram R,Keller J M.The possibilistic C-means algorithm:insights and recommendations[J].IEEE Transactions on Fuzzy Systems,2009,4(3):385 - 393

[6] Zhang J S,Leung Y W.Improved possibilistic C-means clustering algorithms[J].Fuzzy Systems IEEE Transactions,2004,12(2):209 - 217

[7] 朱嬋,許龍飛.聚類算法在基因表達(dá)數(shù)據(jù)分析中的應(yīng)用[J].華僑大學(xué)學(xué)報(bào)：自然科學(xué)版,2005,26(1):7-10

[8] http://archive.ics.uci.edu/ml/[DB/OL]

[9] 劉兵,夏士雄,周勇,等.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報(bào),2012,40(2):371-375

[10] 胡靖,張廷偉,劉長(zhǎng)仲,等.基于模糊聚類法的亞洲小車蝗種群空間格局分析[J].甘肅農(nóng)業(yè)大學(xué)學(xué)報(bào),2012,47(3):62-66

(責(zé)任編輯 胡文忠)

A constrained improved possibilistic C-means clustering method

XIAO Zhen-qiu1，ZENG Wen-hua2

(1.Computer Academy,Jiaying University,Meizhou 514015,China；2.College of Software,Xiamen University,Xiamen 361005,China)

【Objective】 To solve the problem that improved possibilistic C-means method has low computational efficiency and is hard to deal with complex data structures.【Method】 A constrained improved possibilistic C-means method was proposed.The new method used polynomial kernel to map the feature vector to an implicit space,in order to easily deal with complex data structures and introduced two pairwise constrain set to reduce the number of iteration in the process of data clustering to improve the computational efficiency and anti-interference ability.【Result】 The experiment was implemented on a well-known public testing dataset called UCI,and used misclassification rate to evaluate the performance of object classification.The results showed that the new method had low misclassification rate and strong robustness to noise.【Conclusion】 The computational efficiency of the new method is higher than that of the improved possibilistic C-means clustering method.

clustering;C-means;fuzzy C-means;possibilistic C-means;improved possibilistic C-means

肖振球(1980-)，男， 講師，碩士，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù).E-mail:850246398@qq.com

國(guó)家自然科學(xué)基金面上項(xiàng)目(41172028 )； 國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61403164 ).

2016-03-28；

2016-09-21

TP 391

A

1003-4315(2016)06-0149-06