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

武斌，武小紅，賈紅雯

1.安徽農業大學 信息與計算機學院，合肥 230036

2.滁州職業技術學院 信息工程系，安徽 滁州 239000

3.江蘇大學 電氣信息工程學院，江蘇 鎮江 212013

4.江蘇大學 食品與生物工程學院，江蘇 鎮江 212013

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

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

1.安徽農業大學 信息與計算機學院，合肥 230036

2.滁州職業技術學院 信息工程系，安徽 滁州 239000

3.江蘇大學 電氣信息工程學院，江蘇 鎮江 212013

4.江蘇大學 食品與生物工程學院，江蘇 鎮江 212013

1 引言

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

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

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

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

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

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

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

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

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

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

式（5）中，uik，FCM是運行FCM后得到的隸屬度值，β通常取值為1。

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

3 非參數化的廣義噪聲聚類

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

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

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

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

FGNC算法可以表述如下。

初始化部分：

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

步驟2設置初始循環數r=1和最大循環數為rmax；

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

步驟4根據公式（11）計算σ2的值。

循環計算部分：

步驟1根據公式（6）和（10）計算；

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

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

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

4 實驗

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

4.1 對噪聲數據的處理能力

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

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

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

4.2 聚類中心分析

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

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

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

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

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

4.3 聚類準確性和聚類時間

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

FCM、GNC和FGNC算法對IRIS數據集聚類的結果如表3所示，可見，FCM算法聚類準確率最差，聚類花費時間最少；GNC算法和FGNC算法聚類準確率相同，但FGNC花費時間比GNC要少，循環次數也比GNC少。

表3 FCM、GNC和FGNC算法對IRIS數據集聚類結果

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

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

表4 FCM、GNC和FGNC算法對Wine數據集聚類結果

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

類1和類2分別含有200個數據點。另外，由100個非正態分布在[1，8]×[-4，4]上的噪聲數據點構成X500的一個噪聲類別。從表5可看出，FGNC算法聚類的循環次數和聚類時間均比GNC算法少。

表5 GNC和FGNC算法對X500數據集聚類結果

5 結論

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

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

模糊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.

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

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