關(guān)于馬氏距離模糊聚類的有效性指標(biāo)研究

祖志文， 李 秦

(蘭州交通大學(xué) 數(shù)理學(xué)院， 甘肅 蘭州 730070)

聚類有效性是指通過聚類算法得到數(shù)據(jù)集的聚類結(jié)構(gòu)后，對聚類結(jié)果做合理性和有效性的評價。對于模糊聚類而言，模糊聚類算法在對樣本集進(jìn)行聚類分析前需要事先給定聚類數(shù)目，合理聚類數(shù)目的確定需由有效性函數(shù)來完成，因此模糊聚類有效性問題可轉(zhuǎn)化為最佳聚類數(shù)的決策問題。

歷史上對模糊聚類有效性指標(biāo)已早有研究，如劃分系數(shù)、劃分熵，及改進(jìn)的基于可能性分布的聚類有效性函數(shù)FP(U;c)、FS有效性指標(biāo)[1]、Kwon指標(biāo)[2]、Kim指標(biāo)[3]、PBMF模糊有效性指標(biāo)[4]。近幾年，對于模糊聚類的有效性指標(biāo)的研究層出不窮，基于數(shù)據(jù)集的幾何結(jié)構(gòu)設(shè)計的模糊聚類有效性指標(biāo)表現(xiàn)較佳，如很多學(xué)者對緊致性和分離性度量公式分別加以改進(jìn)，從而利用兩者之比構(gòu)造出新的有效性指標(biāo)[5-6]；Sreeram Joopudi等人[7]提出了分級距離指標(biāo)GD-index；Chatti Subbalakshmi等人[8]將輪廓函數(shù)與模糊聚類結(jié)合，可以尋找動態(tài)數(shù)據(jù)集的最佳聚類數(shù)。

以上為基于歐氏距離的經(jīng)典模糊聚類FCM算法研究的模糊聚類有效性指標(biāo)，對基于馬氏距離的模糊聚類算法并不適用。本文首先通過列舉基于歐氏距離的模糊聚類有效性指標(biāo)分析不同類型有效性指標(biāo)的準(zhǔn)確性，然后給出基于馬氏距離的模糊聚類算法M-FCM，根據(jù)M-FCM與FCM算法的差異提出一種適用于M-FCM算法的有效性指標(biāo)，最后結(jié)合算法在真實數(shù)據(jù)集上進(jìn)行實驗，以驗證所提出的有效性指標(biāo)的準(zhǔn)確性。

1 兩種模糊聚類有效性指標(biāo)對比

1.1 基于數(shù)據(jù)集模糊劃分

FP(U;c)=F(U;c)-P(U;c),

Kim指標(biāo)是通過計算所有重疊度的均值來衡量聚類的有效性，重疊度是聚類對交疊部分相關(guān)度的權(quán)值之和。指標(biāo)如下所示：

1.2 基于數(shù)據(jù)集幾何結(jié)構(gòu)

FS有效性指標(biāo)定義如下：

針對Kim指標(biāo)的缺點(diǎn)提出的有效性指標(biāo)SC定義如下：

SC=ω×Sepn(c,U)+(1-ω)×Comn(c,U),

1.3 兩種有效性指標(biāo)對比分析

為比較基于數(shù)據(jù)集模糊劃分與幾何結(jié)構(gòu)的模糊聚類有效性指標(biāo)，選擇可適用于馬氏距離的模糊聚類算法有效性指標(biāo)的研究方向，使得算法能準(zhǔn)確識別最佳聚類數(shù)目，下面將常用的兩個基于數(shù)據(jù)集模糊劃分的模糊聚類有效性指標(biāo)FP(U;c)、Kim與兩個基于數(shù)據(jù)集幾何結(jié)構(gòu)的模糊聚類有效性指標(biāo)FS、SC分別用于經(jīng)典的模糊聚類算法FCM，在5個來自UCI數(shù)據(jù)庫的真實數(shù)據(jù)集Iris、Pima、Breast Cancer、Wine、WDBC上進(jìn)行實驗。Iris數(shù)據(jù)集由150個樣本組成，并且每個樣本有4個屬性，分為3個類別，第一類與其它兩類完全分離，而第二類與第三類之間有交叉。Pima數(shù)據(jù)集有768個樣本，由兩個相互交疊的類組成，每個樣本有8個屬性。Breast Cancer數(shù)據(jù)集由9維空間的683個樣本組成，分為兩個交疊的子類。Wine數(shù)據(jù)是由13維空間的178個樣本組成，共分為3個種類，3類之間完全分離。WDBC數(shù)據(jù)集由30維空間的569個樣本組成，分為兩類。不同類型有效性指標(biāo)對上述5個真實數(shù)據(jù)集所獲聚類數(shù)及相應(yīng)的有效性值如表1所示。

表1 有效性指標(biāo)對比

從表中可以看出，F(xiàn)P(U;c) 指標(biāo)處理多維數(shù)據(jù)的能力欠佳，對較高維的Pima、Wine和WDBC數(shù)據(jù)集失效；Kim指標(biāo)會隨著聚類數(shù)的增加而呈現(xiàn)單調(diào)遞增的趨勢，而且當(dāng)對包含交疊子集的數(shù)據(jù)集Iris、Pima進(jìn)行聚類時，該指標(biāo)不能夠準(zhǔn)確的識別聚類數(shù)。而有效性指標(biāo)FS、SC在這5個真實數(shù)據(jù)聚類實驗中,雖然收斂速度明顯不如兩個基于數(shù)據(jù)集模糊劃分的模糊聚類有效性指標(biāo)，但都可得到符合實際的最佳聚類數(shù)，說明基于數(shù)據(jù)集幾何結(jié)構(gòu)研究的模糊聚類有效性指標(biāo)性能較佳。

2 基于馬氏距離模糊聚類的有效性

2.1 基于馬氏距離的模糊聚類算法

經(jīng)典的FCM算法是只適合于球形數(shù)據(jù)，而用于非球形或橢球形結(jié)構(gòu)的許多算法，都在處理高維數(shù)據(jù)時效果很差，將經(jīng)典的FCM聚類中的歐氏距離用馬氏距離代替，可以消除量綱不同對聚類分析的影響，排除變量之間相關(guān)性的干擾，這種基于馬氏距離的模糊聚類算法也多用來處理復(fù)雜的多維數(shù)據(jù)[10]。

FCM算法的優(yōu)化目標(biāo)函數(shù)為

最小化J，對ci,uij,Σi求偏導(dǎo)，并令它們等于零，得

(1)

(2)

(3)

M-FCM算法描述如下：

初始化：給定聚類類別數(shù)c，2≤c≤n，n是數(shù)據(jù)個數(shù)，設(shè)定迭代閾值ε，初始化聚類中心矩陣C(0)，設(shè)置迭代計數(shù)器L=0。

步驟一：用(1)式計算或更新隸屬度矩陣U(L)。

步驟二：用(2)式更新聚類中心矩陣C(L+1)。

步驟三：如果‖C(L)-C(L+1)‖<ε，則算法停止并輸出隸屬度矩陣U和聚類中心C，否則令L=L+1，轉(zhuǎn)向步驟一。其中，‖·‖為某種合適的矩陣范數(shù)。

2.2 基于馬氏距離的模糊聚類有效性指標(biāo)

(1)用目標(biāo)函數(shù)的均值來衡量類內(nèi)緊致度：

(k=1,2,…,c;j=1,2,…,n)

其中，Σi(3)式計算。當(dāng)compact(U,C,Σi)越小時，類內(nèi)樣本越緊致，當(dāng)compact(U,C,Σi)取得最小值時，則類內(nèi)緊致程度最好，相似度最高。

(2)用類間聚類中心的總距離來定義類間分離度：

其中Dik為聚類中心的距離，當(dāng)separate(C)取得最大值時，類間分離程度最好。

(3)用各個類內(nèi)最大模糊隸屬度值的均值來衡量類間清晰度：

清晰度用來度量模糊聚類劃分結(jié)果是否分明，其值越小，則表明劃分越清晰。

基于上述的緊致度、分離度和清晰度，提出了一種基于馬氏距離的模糊聚類有效性指標(biāo)CSD：

其中權(quán)重因子α和1-α用來補(bǔ)償緊致度和分離度的度量差別，使得在不同數(shù)據(jù)空間中緊致度和分離度取值變化范圍較大的一方賦予較小的權(quán)重，聚類結(jié)果更清晰。一般情況下，緊致度權(quán)重α略大于分離度權(quán)重1-α，這里取α=0.6，1-α=0.4。由上述可知，CSD指標(biāo)的值越小，說明樣本集的類內(nèi)緊致程度越高、類間分離程度越大、類間清晰程度越明顯，即CSD指標(biāo)的最小值對應(yīng)的聚類數(shù)目c為最佳聚類數(shù)目。

3 實驗結(jié)果與分析

圖1 CSD有效性指標(biāo)平均值隨聚類數(shù)目c的變化圖

對于5種數(shù)據(jù)集Iris(n=150,c=3)、Breast Cancer(n=683,c=2)、Wine(n=178,c=3)、WDBC(n=569,c=2)、Pima(n=768,c=2)的聚類算法運(yùn)行結(jié)果如表2所示。

表2 聚類算法運(yùn)行結(jié)果

實驗結(jié)果分析：由圖1(a)—(e)可知，CSD有效性指標(biāo)對Iris數(shù)據(jù)集在聚類數(shù)c=3時達(dá)到極小值，對Breast Cancer數(shù)據(jù)集在聚類數(shù)c=2時達(dá)到極小值，對Wine數(shù)據(jù)集在聚類數(shù)c=3時達(dá)到極小值，對WDBC數(shù)據(jù)集在聚類數(shù)c=2時達(dá)到極小值，對Pima數(shù)據(jù)集在聚類數(shù)c=2時達(dá)到極小值，即新的有效性指標(biāo)對5個標(biāo)準(zhǔn)數(shù)據(jù)集都可以正確地確定數(shù)據(jù)集的最佳聚類數(shù)。由表2可知，基于馬氏距離的模糊聚類算法在CSD有效性指標(biāo)檢驗下可以有效聚類，并且算法的運(yùn)行時間和聚類精度都在合理范圍內(nèi)。通過實驗，可以說明本文提出的有效性指標(biāo)保證了基于馬氏距離的模糊聚類算法M-FCM在多維數(shù)據(jù)中聚類時可以準(zhǔn)確識別最佳聚類數(shù)目。

4 結(jié)束語

本文通過對比分析基于數(shù)據(jù)集模糊劃分與幾何結(jié)構(gòu)的模糊聚類有效性指標(biāo)，確定了類內(nèi)緊致度、類間分離度與類間清晰度結(jié)合的有效性研究方向，針對基于馬氏距離的模糊聚類算法提出新的度量標(biāo)準(zhǔn)，構(gòu)造出基于馬氏距離的模糊聚類有效性指標(biāo)CSD。最后結(jié)合算法在真實數(shù)據(jù)集上進(jìn)行實驗，驗證了該有效性指標(biāo)適用于基于馬氏距離的模糊聚類算法，保證了算法在多維數(shù)據(jù)上聚類的有效性。

[參考文獻(xiàn)]

[1] 李春生.模糊聚類的組合方法及其應(yīng)用研究[D].長沙：湖南大學(xué),2010.

[2] KWON S H.Cluster validity index for fuzzy clustering[J].Electronics Letters,1998,34(22):2176-2177.

[3] KIM D W,Lee K H,Lee D.On cluster validity index for estimation of the optimal number of fuzzy clusters[J].Pattern Recognition, 2004,37(10):2009-2025.

[4] PAKHIRA M K,BANDYOPADHYAY 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.

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

[6] 湯官寶.一種新的模糊聚類有效性指標(biāo)[J].計算機(jī)與現(xiàn)代化,2014(7):16-18.

[7] SREERAM J,SURAJ S R,NARASIMHAN S,et al.A New Cluster Validity Index for Fuzzy Clustering[J].IFAC Proceedings Volumes,2013,46(32):325-330.

[8] CHATTI S,RAMA K G,KRISHNA M R S,et al.A Method to Find Optimum Number of Clusters Based on Fuzzy Silhouette on Dynamic Data Set[J].Procedia Computer Science,2015,46:346-353.

[9] 張妨妨.模糊聚類技術(shù)的研究及應(yīng)用[D].無錫：江南大學(xué),2013.

[10] 蔡靜穎.模糊聚類算法及應(yīng)用[M].北京:冶金工業(yè)出版社,2015:20-100.