一種快速的廣義噪聲聚類算法

武斌，武小紅，賈紅雯

1.安徽農(nóng)業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院，合肥 230036

2.滁州職業(yè)技術(shù)學(xué)院 信息工程系，安徽 滁州 239000

3.江蘇大學(xué) 電氣信息工程學(xué)院，江蘇 鎮(zhèn)江 212013

4.江蘇大學(xué) 食品與生物工程學(xué)院，江蘇 鎮(zhèn)江 212013

一種快速的廣義噪聲聚類算法

武斌1，2，武小紅3，4，賈紅雯2

1.安徽農(nóng)業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院，合肥 230036

2.滁州職業(yè)技術(shù)學(xué)院 信息工程系，安徽 滁州 239000

3.江蘇大學(xué) 電氣信息工程學(xué)院，江蘇 鎮(zhèn)江 212013

4.江蘇大學(xué) 食品與生物工程學(xué)院，江蘇 鎮(zhèn)江 212013

1 引言

模糊聚類是模式識(shí)別領(lǐng)域中一個(gè)重要的分支，屬于無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法。其中最著名的模糊聚類算法是由Dunn提出[1]并由Bezdek加以擴(kuò)展而形成的模糊C-均值聚類（FCM）。FCM算法及其派生算法在模式識(shí)別，圖像處理和視頻檢索等領(lǐng)域取得很好的效果[2-4]。但是建立在可能性約束條件基礎(chǔ)上的FCM對(duì)噪聲非常敏感[5]，為了克服這個(gè)缺點(diǎn)，Krishnapuram和Keller放棄了FCM算法的可能性約束條件，提出了可能C-均值聚類（PCM）算法[5]。PCM算法能夠聚類包含噪聲的數(shù)據(jù)，它賦予噪聲數(shù)據(jù)很小的隸屬度值，因而噪聲對(duì)聚類的影響可以忽略。但是PCM算法對(duì)初始聚類中心很敏感，常常會(huì)導(dǎo)致一致性聚類結(jié)果[6]。

Davé提出噪聲聚類（NC）算法以處理噪聲數(shù)據(jù)[7]。NC算法將噪聲看做一個(gè)獨(dú)立的類，定義噪聲距離為常數(shù)δ。受PCM的啟發(fā)，Davé認(rèn)為噪聲距離不是常數(shù)將提高算法的性能，因而定義噪聲距離在不同的類中距離值不同，將噪聲聚類算法擴(kuò)展為廣義噪聲聚類（GNC）算法[8-9]。GNC算法實(shí)際上綜合了FCM算法和PCM算法兩者的優(yōu)點(diǎn)，避免了FCM算法對(duì)噪聲數(shù)據(jù)敏感和PCM算法易導(dǎo)致一致性聚類結(jié)果的缺點(diǎn)。但是，GNC算法在計(jì)算噪聲距離時(shí)需要事先運(yùn)行FCM算法以計(jì)算參數(shù)ηi，也就是說GNC算法非常依賴參數(shù)ηi。如果GNC算法算法不依賴參數(shù)ηi則不必事先運(yùn)行FCM算法，這樣必然節(jié)省了聚類時(shí)間。受可能聚類算法（PCA）[10]和可能性模糊C-均值聚類新算法[11]啟發(fā)，本文提出一種快速的廣義噪聲聚類（FGNC）算法。FGNC算法不依賴參數(shù)ηi，比GNC聚類時(shí)間少，具有較高的聚類準(zhǔn)確率。

2 噪聲聚類和廣義噪聲聚類

噪聲聚類（NC）算法定義噪聲距離為常數(shù)δ。噪聲被看做一個(gè)獨(dú)立的類，對(duì)于某個(gè)數(shù)據(jù)點(diǎn)xj在噪聲類中的隸屬度定義為[7]：

式（1）中，c是聚類的類別數(shù)，uij是數(shù)據(jù)xj隸屬于類i的隸屬度值。NC采用的可能性約束條件如下：

約束條件（2）比FCM的可能性約束條件要寬松。

與FCM算法相比，NC算法的優(yōu)點(diǎn)在于其魯棒性和適合處理噪聲數(shù)據(jù)。NC算法賦予噪聲數(shù)據(jù)很小的隸屬度值從而使噪聲數(shù)據(jù)和真實(shí)數(shù)據(jù)區(qū)別開來(lái)。但是如何確定噪聲距離常數(shù)δ是一個(gè)難點(diǎn)，通常要根據(jù)經(jīng)驗(yàn)取值。

NC算法的噪聲距離δ2和可能C-均值聚類（PCM）的參數(shù)ηi比較相似。PCM算法中實(shí)際上有c個(gè)噪聲類而NC算法就一個(gè)噪聲類，即NC算法是魯棒的FCM算法，而PCM算法像c個(gè)NC算法的集合[8]。在分析NC算法和PCM算法基礎(chǔ)上，Davé進(jìn)一步將NC算法推廣為廣義噪聲聚類（GNC），GNC最小化以下目標(biāo)函數(shù)[8-9]：

式（3）中，Dik=‖xk-νi‖，表示數(shù)據(jù)點(diǎn)xk到類中心矢量νi的歐式距離。定義為：

式（4）中，參數(shù)ηi來(lái)自PCM的計(jì)算公式與FCM的隸屬度計(jì)算公式相同，它們分別為[9]：

式（5）中，uik，F(xiàn)CM是運(yùn)行FCM后得到的隸屬度值，β通常取值為1。

最小化式（3）得到GNC的隸屬度：

3 非參數(shù)化的廣義噪聲聚類

FGNC算法的類中心矢量νi和公式（8）一樣。

理論分析：樣本的協(xié)方差σ2衡量了數(shù)據(jù)的分離程度，聯(lián)合式（10）和（11）可以將目標(biāo)函數(shù)（3）變換為：

求解最小化式（13）得到的隸屬度和式（12）相同式。式（13）的第1項(xiàng)為：

tr(SfW)衡量數(shù)據(jù)的類內(nèi)緊湊程度，tr(ST)衡量數(shù)據(jù)的分離程度[10]。因而FGNC算法能同時(shí)重視數(shù)據(jù)的類內(nèi)緊湊程度和分離程度，很好地解決了GNC依賴參數(shù)問題，同時(shí)具有良好的聚類效果。

FGNC算法可以表述如下。

初始化部分：

步驟1固定c和m的值，1＜c＜n，1＜m；設(shè)置終止值ε；

步驟2設(shè)置初始循環(huán)數(shù)r=1和最大循環(huán)數(shù)為rmax；

步驟3選定初始類中心V(0)；

步驟4根據(jù)公式（11）計(jì)算σ2的值。

循環(huán)計(jì)算部分：

步驟1根據(jù)公式（6）和（10）計(jì)算；

步驟2用公式（12）計(jì)算隸屬度U(r)；

步驟3用公式（8）計(jì)算類中心矩陣V(r)；

步驟4循環(huán)數(shù)r加1，直到滿足條件‖V(r)-V(r-1)‖＜ε或(r＞rmax)。

4 實(shí)驗(yàn)

為了測(cè)試FGNC算法的有效性、聚類準(zhǔn)確性和聚類時(shí)間，分別用FCM、GNC和FGNC算法對(duì)一些數(shù)據(jù)集進(jìn)行測(cè)試。實(shí)驗(yàn)條件：ε=0.000 01，最大循環(huán)數(shù)為rmax=100，m=2.0。計(jì)算機(jī)配置：奔騰1.7 GHz，內(nèi)存256 MB，利用Matlab 7.0進(jìn)行仿真計(jì)算。對(duì)三種算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較，說明了FGNC算法的優(yōu)越性能。

4.1 對(duì)噪聲數(shù)據(jù)的處理能力

[12]進(jìn)行實(shí)驗(yàn)。X12是有12個(gè)數(shù)據(jù)點(diǎn)的二維數(shù)據(jù)集，它的坐標(biāo)的分布圖見文獻(xiàn)[12]。X12中的10個(gè)數(shù)據(jù)點(diǎn)（除了點(diǎn)x6和x12）組成兩個(gè)菱形分布在y軸兩邊，x6和x12到兩類中心距離相等是噪聲點(diǎn)。初始化類中心[12]：

分別對(duì)X12運(yùn)行FCM、GNC和FGNC算法后，得到的隸屬度值如表1所示。數(shù)據(jù)點(diǎn)x6和x12在運(yùn)行FCM算法后每個(gè)類的隸屬度均為0.50，因此FCM無(wú)法將噪聲和其余的10個(gè)數(shù)據(jù)點(diǎn)區(qū)別開來(lái)，也就是說FCM算法對(duì)噪聲敏感[12]。因?yàn)閤12比x6遠(yuǎn)離類中心點(diǎn)，所以原則上要求x12的隸屬度要比x6的隸屬度小，而運(yùn)行GNC算法后數(shù)據(jù)點(diǎn)x6和x12在每個(gè)類的隸屬度分別為0.21和0.03，因此GNC算法能很好地把噪聲數(shù)據(jù)從其他數(shù)據(jù)中區(qū)別開來(lái)。運(yùn)行FGNC算法后，數(shù)據(jù)點(diǎn)x6和x12在每個(gè)類的隸屬度分別為0.09和0.01，因此FGNC算法也能很好地處理噪聲數(shù)據(jù)。實(shí)驗(yàn)表明GNC和FGNC算法均能有效地處理含噪聲的數(shù)據(jù)，不同之處在于GNC需要運(yùn)行FCM后來(lái)計(jì)算參數(shù)ηi，而FGNC則不需要。

表1 FCM、GNC和FGNC算法對(duì)數(shù)據(jù)集X12進(jìn)行實(shí)驗(yàn)所得到的隸屬度

4.2 聚類中心分析

聚類算法除了產(chǎn)生隸屬度外還會(huì)得到聚類的類中心，如果所得到的聚類中心距離真實(shí)聚類中心最近，則表示該算法得到的聚類中心最好。X12的真實(shí)聚類中心[12]：

表2是FCM、GNC和FGNC三種算法對(duì)噪聲數(shù)據(jù)集X12進(jìn)行實(shí)驗(yàn)所得的聚類中心。

表2 FCM、GNC和FGNC算法對(duì)噪聲數(shù)據(jù)集X12進(jìn)行實(shí)驗(yàn)所得的聚類中心

用VFCM、VGNC和VFGNC分別表示表2中的類中心，利用下式計(jì)算類中心[12]：

式中*表示FCM/GNC/FGNC算法。計(jì)算結(jié)果為：EFCM= 0.587 2，EGNC=0.007 2，EFGNC=0，則EFCM＞EGNC＞EFGNC。很明顯E*越小表示該聚類中心越接近真實(shí)聚類中心，所以FGNC算法得到的類中心最好，GNC算法次之，F(xiàn)CM算法最差。

4.3 聚類準(zhǔn)確性和聚類時(shí)間

對(duì)IRIS[13-14]數(shù)據(jù)集運(yùn)行FCM、GNC和FGNC算法。初始化類中心[12]：

FCM、GNC和FGNC算法對(duì)IRIS數(shù)據(jù)集聚類的結(jié)果如表3所示，可見，F(xiàn)CM算法聚類準(zhǔn)確率最差，聚類花費(fèi)時(shí)間最少；GNC算法和FGNC算法聚類準(zhǔn)確率相同，但FGNC花費(fèi)時(shí)間比GNC要少，循環(huán)次數(shù)也比GNC少。

表3 FCM、GNC和FGNC算法對(duì)IRIS數(shù)據(jù)集聚類結(jié)果

接著對(duì)Wine數(shù)據(jù)集[15]做實(shí)驗(yàn)，Wine數(shù)據(jù)集有三類數(shù)據(jù)，三類數(shù)據(jù)點(diǎn)數(shù)分別是59、71和48，取屬性7和10作為聚類實(shí)驗(yàn)用數(shù)據(jù)集。初始化類中心：

實(shí)驗(yàn)結(jié)果如表4所示，可見，F(xiàn)GNC算法聚類準(zhǔn)確率最好，同時(shí)FGNC算法聚類花費(fèi)的時(shí)間也比GNC算法少。

表4 FCM、GNC和FGNC算法對(duì)Wine數(shù)據(jù)集聚類結(jié)果

最后，對(duì)數(shù)據(jù)集X500進(jìn)行聚類，X500含有兩個(gè)類別的正態(tài)分布N(u，Σ)，分別為：

類1和類2分別含有200個(gè)數(shù)據(jù)點(diǎn)。另外，由100個(gè)非正態(tài)分布在[1，8]×[-4，4]上的噪聲數(shù)據(jù)點(diǎn)構(gòu)成X500的一個(gè)噪聲類別。從表5可看出，F(xiàn)GNC算法聚類的循環(huán)次數(shù)和聚類時(shí)間均比GNC算法少。

表5 GNC和FGNC算法對(duì)X500數(shù)據(jù)集聚類結(jié)果

5 結(jié)論

本文在分析GNC算法的基礎(chǔ)上，針對(duì)GNC算法需要事先運(yùn)行FCM算法以計(jì)算其參數(shù)這個(gè)缺點(diǎn)，提出FGNC算法。通過對(duì)噪聲數(shù)據(jù)的處理，以及對(duì)聚類中心分析，聚類準(zhǔn)確率和聚類時(shí)間的實(shí)驗(yàn)分析，結(jié)果表明FGNC算法在保持GNC算法處理噪聲數(shù)據(jù)能力的同時(shí)，具有最優(yōu)的聚類中心，其聚類速度更快，聚類準(zhǔn)確率更高。

[1]Dunn J C.A fuzzy relative of the ISODATA process and its useindetectingcompact well-separatedclusters[J].Journal of Cybern，1974，3（3）：32-57.

[2]Tjhi W C，Chen L H.A heuristic-based fuzzy co-clustering algorithmforcategorizationofhigh-dimensionaldata[J]. Fuzzy Sets and Systems，2008，159（4）：371-389.

[3]Lin D T，Liao G J.Swarm intelligence based fuzzy c-means clustering for motion vector selection in video watermarking[J]. International Journal of Fuzzy Systems，2008，10（3）：185-194.

[4]Ghosh A，Mishra N S，Ghosh S.Fuzzy clustering algorithms for unsupervised change detection in remote sensing images[J]. Information Sciences，2011，181（4）：699-715.

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

[6]Barni M，Cappellini V，Mecocci A.Comments on“a possibilistic approach to clustering”[J].IEEE Trans on Fuzzy Systems，1996，4（3）：393-396.

[7]Davé R N.Characterization and detection of noise in clustering[J]. Pattern Recognition Letters，1991，12（11）：657-664.

[8]He Guangpu，Li Min，Wu Bin，et al.Generalized noise clustering based on non-Euclidean distance[J].Journal of Beijing Jiaotong University，2008，32（6）：98-101.

[9]Davé R N，Sen Sumit.Generalized noise clustering as a robust fuzzy C-mestimators model[C]//Proceedings of Conference of the North American Fuzzy Information Processing Society，1998：256-260.

[10]Yang M S，Wu K L.Unsupervised possibilistic clustering[J]. Pattern Recognition，2006，39（1）：5-21.

[11]武小紅，周建江.可能性模糊C-均值聚類新算法[J].電子學(xué)報(bào)，2008，36（10）：1996-2000.

[12]Pal N R，Pal K，Bezdek J C.A possibilistic fuzzy c-means clusteringalgorithm[J].IEEETransonFuzzySystems，2005，13（4）：517-530.

[13]Lee S W，Kim Y S，Park K H，et al.Iterative Bayesian fuzzy clustering toward flexible icon-based assistive software for the disabled[J].Information Sciences，2010，180（3）：325-340.

[14]Carl G L.Fuzzy connectivity clustering with radial basis kernel functions[J].Fuzzy Sets and Systems，2009，160（13）：1868-1885.

[15]Wang C H.Apply robust segmentation to the service industry using kernel induced fuzzy clustering techniques[J].Expert Systems with Applications，2010，37（12）：8395-8400.

WU Bin1，2,WU Xiaohong3，4,JIA Hongwen2

1.School of Information and Computer Science,Anhui Agricultural University,Hefei 230036,China
2.Department of Information Engineering,Chuzhou Vocational Technology College,Chuzhou,Anhui 239000,China
3.School of Electrical and Information Engineering,Jiangsu University,Zhenjiang,Jiangsu 212013,China
4.School of Food and Biological Engineering,Jiangsu University,Zhenjiang,Jiangsu 212013,China

A Fast Generalized Noise Clustering（FGNC）based on Generalized Noise Clustering（GNC）objective function and Possibilistic Clustering Algorithm（PCA）is proposed to deal with the shortcoming of GNC algorithm depend heavily on parameters, and FCM must be performed until termination to calculate the parameters for GNC algorithm.With a nonparametric method, FGNC calculates the parameters in GNC objective function.So FGNC algorithm does not depend on the parameters that GNC holds and clusters data faster than GNC algorithm.Experiment and simulation on two man-made data sets and two real data sets show FGNC can deal with noisy data well,cluster centers are closer to real ones,clustering accuracy is improved and clustering time is reduced.

Fuzzy C-Means（FCM）;Possibilistic C-Means（PCM）;Generalized Noise Clustering（GNC）

為解決廣義噪聲聚類（GNC）算法非常依賴參數(shù)和在運(yùn)行GNC算法前必須運(yùn)行FCM算法以便計(jì)算參數(shù)的缺點(diǎn)，在GNC的目標(biāo)函數(shù)和可能聚類算法（PCA）基礎(chǔ)上，提出一種快速的廣義噪聲聚類（FGNC）算法。FGNC算法通過一種非參數(shù)化方法計(jì)算GNC目標(biāo)函數(shù)中的參數(shù)，因而FGNC算法不依賴參數(shù)并且聚類速度快于GNC算法。對(duì)人工含噪聲數(shù)據(jù)集和兩個(gè)實(shí)際數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明FGNC算法能很好地處理含噪聲數(shù)據(jù)，具有聚類中心更接近真實(shí)聚類中心，聚類準(zhǔn)確性高，聚類時(shí)間少的優(yōu)良性能。

模糊C-均值聚類；可能C-均值聚類；廣義噪聲聚類

A

TP181

10.3778/j.issn.1002-8331.1112-0635

WU Bin,WU Xiaohong,JIA Hongwen.Fast generalized noise clustering algorithm.Computer Engineering and Applications,2013,49（13）：145-148.

安徽省高校省級(jí)優(yōu)秀青年人才基金（No.2012SQRL251）；安徽省高校省級(jí)科學(xué)研究項(xiàng)目（No.KJ2012Z302）。

武斌（1978—），男，講師，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別和嵌入式系統(tǒng)工程；武小紅（1971—），男，副教授，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別和圖像處理等；賈紅雯（1978—），女，講師，主要研究領(lǐng)域?yàn)橥ㄐ藕蛙浖夹g(shù)。E-mail：wubind2003@163.com

2012-01-09

2012-03-29

1002-8331（2013）13-0145-04

CNKI出版日期：2012-05-21http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1137.003.html