武斌，武小紅，賈紅雯

1.安徽農(nóng)業(yè)大學(xué) 信息與計算機學(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é) 信息與計算機學(xué)院，合肥 230036

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

tr(SfW)衡量數(shù)據(jù)的類內(nèi)緊湊程度，tr(ST)衡量數(shù)據(jù)的分離程度[10]。因而FGNC算法能同時重視數(shù)據(jù)的類內(nèi)緊湊程度和分離程度，很好地解決了GNC依賴參數(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）計算σ2的值。

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

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

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

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

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

4 實驗

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

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

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

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

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

4.2 聚類中心分析

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

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

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

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

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

4.3 聚類準確性和聚類時間

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

[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é)報，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ù)和在運行GNC算法前必須運行FCM算法以便計算參數(shù)的缺點，在GNC的目標函數(shù)和可能聚類算法（PCA）基礎(chǔ)上，提出一種快速的廣義噪聲聚類（FGNC）算法。FGNC算法通過一種非參數(shù)化方法計算GNC目標函數(shù)中的參數(shù)，因而FGNC算法不依賴參數(shù)并且聚類速度快于GNC算法。對人工含噪聲數(shù)據(jù)集和兩個實際數(shù)據(jù)集進行仿真實驗，實驗結(jié)果表明FGNC算法能很好地處理含噪聲數(shù)據(jù)，具有聚類中心更接近真實聚類中心，聚類準確性高，聚類時間少的優(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.

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

武斌（1978—），男，講師，主要研究領(lǐng)域為模式識別和嵌入式系統(tǒng)工程；武小紅（1971—），男，副教授，主要研究領(lǐng)域為模式識別和圖像處理等；賈紅雯（1978—），女，講師，主要研究領(lǐng)域為通信和軟件技術(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