一種新的模糊聚類有效性指標(biāo)

湯官寶

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

0 引言

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

1 模糊C-均值聚類算法

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

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

FCM聚類算法實(shí)施步驟如下:

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

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

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

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

2 新的有效性指標(biāo)

充分考慮數(shù)據(jù)集的幾何結(jié)構(gòu)，用內(nèi)間分離性與類內(nèi)緊致性度量的比值作為聚類有效性標(biāo)準(zhǔn)是一種較好的方法。如何定義緊致性和分離性函數(shù)是本文關(guān)注的問(wè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 新的有效性指標(biāo)

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

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

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

2)for c=2 to cmax

①執(zhí)行FCM算法;

②計(jì)算VT的值;

End。

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

3 仿真實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

真實(shí)數(shù)據(jù)集:采用UCI機(jī)器學(xué)習(xí)庫(kù)中4個(gè)數(shù)據(jù)集，分別為 Iris、Wine、WBCD、WDBC 數(shù)據(jù)集[17]。表 1是對(duì)4個(gè)數(shù)據(jù)集的簡(jiǎn)單描述。

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

3.2 仿真實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[1] 高新波，謝維信.模糊聚類理論發(fā)展及應(yīng)用的研究進(jìn)展[J].科學(xué)通報(bào)，1999，44(21):2241-2251.

[2] 高新波.模糊聚類分析及其應(yīng)用[M].西安:西安電子科技大學(xué)出版社，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] 孔攀，鄧輝文，黃艷艷，等.一個(gè)新的模糊聚類有效性指標(biāo)[J].計(jì)算機(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].中國(guó)科學(xué)(E 輯)，2002，32(2):274-280.

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