湯官寶

(阿壩師范高等專科學?；A(chǔ)教育系，四川 汶川 623002)

0 引言

聚類分析屬于無監(jiān)督模式識別的一個重要分支，基于一定的劃分準則，它將待分類樣本集劃分為若干類，使得屬于同一類的樣本相似度盡量高，而不同類的樣本相異性盡量大[1-2]。模糊C-均值算法(FCM)由于其具有簡單、高效、數(shù)據(jù)適應性強等特點，是聚類分析中使用頻率較高、較為流行的算法。如何建立合適的聚類評價標準來驗證FCM算法最終的聚類結(jié)果的優(yōu)劣是聚類分析的核心問題之一。為此許多學者做了大量研究工作。Zadeh給出第一個聚類有效性指標:分離度指標[3]，但判決效果并不理想。Bezdek提出了劃分系數(shù)(PC)和劃分熵(PE)的概念[4-5]。Dave[6]提出了改進的劃分系數(shù)(MPC)。PC，PE，MPC這3項指標雖然具有直觀的幾何解釋和良好的數(shù)學性質(zhì)，但是它們的單調(diào)趨勢以及與數(shù)據(jù)集本身缺少直接聯(lián)系，限制了其應用?？紤]數(shù)據(jù)集自身的信息，基于不同的類內(nèi)緊致性和類間分離性函數(shù)，研究者又提出了一系列聚類有效性指標:Xie和Beni[7]提出了緊致分離指標VXB;Zahid和Limouri提出了VSC聚類有效性指標[8];Pakhira等提出VPBM聚類有效性指標和VPBMF聚類有效性指標[9-10];孔攀等提出了VN(c)聚類有效性指標[11]。數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的多樣化導致沒有通用的模糊聚類有效性函數(shù)，從而導致有效性函數(shù)不斷涌現(xiàn)[12-14]。充分考慮數(shù)據(jù)集的幾何結(jié)構(gòu)，本文基于內(nèi)間分離性與類內(nèi)緊致性的比值，提出一種新的模糊聚類有效性指標。該指標能夠有效地確定由模糊C-均值算法(FCM)所得模糊劃分的最優(yōu)劃分和最優(yōu)聚類數(shù)。

1 模糊C-均值聚類算法

假定數(shù)據(jù)樣本集合 X={x1，x2，…，xn}，模糊聚類是將X 劃分為 c類(2≤c＜n)的過程，V={v1，v2，…，vc}為聚類中心。在模糊劃分中，每個元素以一定隸屬度屬于某一類，uij表示第j個元素屬于第i類的隸屬度FCM的目標函數(shù)表示為:

其中:dik=‖xk－vi‖為樣本點xk與聚類中心vi間的距離;m≥1為模糊加權(quán)指數(shù)[15]，通常取 m=2。FCM的算法思想是迭代調(diào)整(U，V)，使式(1)達到最小值。U，V迭代調(diào)整的過程由下面2個式子確定:

FCM聚類算法實施步驟如下:

步驟1 初始化各個參數(shù)，設定算法終止閾值。

步驟2 利用式(3)計算劃分矩陣。

步驟3 利用式(2)更新聚類中心。

步驟4 如果達到終止條件，算法停止，得到劃分矩陣和聚類中心。否則，轉(zhuǎn)向步驟2。

2 新的有效性指標

充分考慮數(shù)據(jù)集的幾何結(jié)構(gòu)，用內(nèi)間分離性與類內(nèi)緊致性度量的比值作為聚類有效性標準是一種較好的方法。如何定義緊致性和分離性函數(shù)是本文關(guān)注的問題。本文定義的緊致性和分離性函數(shù)充分考慮數(shù)據(jù)集自身信息和它的幾何結(jié)構(gòu)，故能夠有效地確定由模糊C-均值算法(FCM)所得模糊劃分的最優(yōu)劃分和最優(yōu)聚類數(shù)，具有較好的性能。

2.1 類內(nèi)緊致性度量

定義類內(nèi)緊致性度量函數(shù)c(c)為:

2.2 類間分離度度量

定義類間分離度度量函數(shù)s(c)為:

2.3 新的有效性指標

根據(jù)類間分離性度量和類內(nèi)緊致性度量，本文定義新的聚類有效性指標:

一個好的聚類結(jié)果要求較大的分離性，同時要求較小的緊致性。VT定義為分離性度量與緊致性度量之比。所以VT值越大，對應的聚類劃分越好。通過求VT的值來確定最佳聚類數(shù)，其過程如下:

1)初始化參數(shù)[16]，設定c的搜索范圍為2到。

2)for c=2 to cmax

①執(zhí)行FCM算法;

②計算VT的值;

End。

3)找到最大的VT，對應的c即為最佳聚類數(shù)，對應的劃分為最優(yōu)劃分。

3 仿真實驗結(jié)果及分析

為了驗證新的聚類有效性指標的性能，在1個人造數(shù)據(jù)集Data Set(1)和4個真實數(shù)據(jù)集(Iris、Wine、WBCD、WDBC)上進行測試，并和其它幾類聚類有效性指標進行比較。FCM聚類算法最大迭代次數(shù)設定為100，最大類別數(shù)設為10，模糊指數(shù)m設為2。

3.1 數(shù)據(jù)集描述

人造數(shù)據(jù)集:Data Set(1)是二維平面上隨機生成的數(shù)據(jù)集，共4類，每類50個樣本。如圖1所示。

圖1 Data Set(1)數(shù)據(jù)集

真實數(shù)據(jù)集:采用UCI機器學習庫中4個數(shù)據(jù)集，分別為 Iris、Wine、WBCD、WDBC 數(shù)據(jù)集[17]。表 1是對4個數(shù)據(jù)集的簡單描述。

表1 數(shù)據(jù)集的簡單描述

3.2 仿真實驗結(jié)果

在上述5個數(shù)據(jù)集上運行FCM聚類算法，同時用本文提出的聚類有效性指標VT確定最佳聚類數(shù)。實驗結(jié)果顯示:VT指標確定5個數(shù)據(jù)集(Data Set(1)、Iris、Wine、WBCD、WDBC)的最佳聚類數(shù)分別為4、3、3、2、2，這與數(shù)據(jù)集的真實信息是相符的，從而說明聚類有效性指標VT具有良好的性能。

圖2～圖6為5個數(shù)據(jù)集上的有效性指標與聚類數(shù)之間的變化關(guān)系。

圖2 Data Set(1)有效性指標與聚類數(shù)關(guān)系圖

圖3 Iris有效性指標與聚類數(shù)關(guān)系圖

圖4 Wine有效性指標與聚類數(shù)關(guān)系圖

圖5 WBCD有效性指標與聚類數(shù)關(guān)系圖

圖6 WDBC有效性指標與聚類數(shù)關(guān)系圖

用多個聚類有效性指標確定4個真實數(shù)據(jù)集的最佳聚類數(shù)，結(jié)果如表2所示。從表2可以看出，只有VPBMF，VN，VT這3項指標確定的最佳聚類數(shù)與所有4個數(shù)據(jù)集的真實信息相符，說明VT聚類有效性指標是優(yōu)于多個現(xiàn)有聚類有效性指標的。

表2 多種有效性指標確定的最佳聚類數(shù)對比

4 結(jié)束語

當數(shù)據(jù)集的聚類數(shù)未知時，有效性指標可以用來確定最佳聚類數(shù)。本文提出的基于類內(nèi)緊致性和內(nèi)間分離性的聚類有效性指標，可以有效確定最佳聚類數(shù)和最優(yōu)劃分。實驗結(jié)果表明其具有良好的性能。

[1] 高新波，謝維信.模糊聚類理論發(fā)展及應用的研究進展[J].科學通報，1999，44(21):2241-2251.

[2] 高新波.模糊聚類分析及其應用[M].西安:西安電子科技大學出版社，2004.

[3] Zadeh L A.Similarity relations and fuzzy orderings[J].Information Science，1971，3(2):177-200.

[4] Bezdek J C.Cluster validity with fuzzy sets[J].Journal of Cybernetics，1974，3(3):58-73.

[5] Bezdek J C.Numerical taxonomy with fuzzy sets[J].Journal of Mathematical Biology，1974，1(1):57-71.

[6] Dave R N.Validating fuzzy partitions obtained through cshells clustering[J].Pattern Recognition Letters，1996，17(6):613-623.

[7] Xie X L，Beni G.A validity measure for fuzzy clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13(8):841-847.

[8] Zahid N，Limouri M，Essaid A.A new cluster-validity for fuzzy clustering[J].Pattern Recognition，1999，32(7):1089-1097.

[9] Pakhira M K，Bandyopadyay S，Maulik U.Validity index for crisp and fuzzy clusters[J].Pattern Recognition，2004，37(3):487-501.

[10] Pakhira M K，Bandyopadyay S，Maulik U.A study of some fuzzy cluster validity indices，genetic clustering and application to pixel classification[J].Fuzzy Sets and Systems，2005，155(2):191-214.

[11] 孔攀，鄧輝文，黃艷艷，等.一個新的模糊聚類有效性指標[J].計算機工程，2009，35(12):143-144.

[12] Rezaee B.A cluster validity index for fuzzy clustering[J].Fuzzy Sets and Systems，2010，161(23):3014-3025.

[13] Le Capitaine H，F(xiàn)relicot C.A cluster-validity index combining an overlap measure and a separation measure based on fuzzy-aggregation operators[J].IEEE Transactions on Fuzzy System，2011，19(3):580-588.

[14] Kwon S H.Cluster validity index for fuzzy clustering[J].Electronics Letters，1998，34(22):2176-2177.

[15] Pal N R，Bezdek J C.On cluster validity for the fuzzy cmeans model[J].IEEE Transactions on Fuzzy Systems，1995，3(3):370-379.

[16] 于劍，程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J].中國科學(E 輯)，2002，32(2):274-280.

[17] UCI.Fuzzy Clustering[EB/OL].http://www.ics.uci.edu/mlearn/MLRepository.html，2014-03-05.