嚴(yán)加展，陳 華，李 陽(yáng)

1.新疆大學(xué) 電氣工程學(xué)院，烏魯木齊830047

2.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島266590

1 引言

聚類分析可以看作是一種無(wú)監(jiān)督學(xué)習(xí)[1-2]過(guò)程，其主要目的是將一組數(shù)據(jù)樣本劃分為多個(gè)簇[3]，并使簇內(nèi)數(shù)據(jù)樣本有較高的相似度，而不同簇中的數(shù)據(jù)樣本之間相似度較低[4]。模糊聚類作為一種不確定的聚類方法，引入模糊理論使聚類分析更符合數(shù)據(jù)分布的實(shí)際情況，其中模糊C-均值（Fuzzy C-Means，F(xiàn)CM）聚類[5]在模糊聚類中的應(yīng)用最為成熟和廣泛。模糊C-均值聚類利用聚類有效性指標(biāo)對(duì)聚類結(jié)果質(zhì)量進(jìn)行客觀的評(píng)價(jià)[6]。目前，針對(duì)模糊聚類有效性指標(biāo)的研究主要基于劃分熵[7]、劃分系數(shù)[8]以及數(shù)據(jù)幾何結(jié)構(gòu)[9]提出的聚類有效性指標(biāo)。例如：Xie-Beni 有效性指標(biāo)[10]VXB其考慮了數(shù)據(jù)的幾何結(jié)構(gòu)，利用數(shù)據(jù)幾何結(jié)構(gòu)的計(jì)算對(duì)有效性指標(biāo)進(jìn)行改進(jìn)；Bensaid有效性指標(biāo)[11]VBD利用簇中數(shù)據(jù)樣本平均值和對(duì)分離度計(jì)算進(jìn)行改進(jìn)，從而改進(jìn)有效性指標(biāo)；VUV[12]有效性指標(biāo)引入指數(shù)函數(shù)作為相似度距離計(jì)算等；VFM[13]有效性指標(biāo)引入劃分熵以及模糊因子進(jìn)行幾何結(jié)構(gòu)計(jì)算，對(duì)有效性指標(biāo)進(jìn)行改進(jìn)。國(guó)內(nèi)學(xué)者也做了大量研究，這些學(xué)者主要從數(shù)據(jù)樣本分布的幾何特征入手進(jìn)行有效性指標(biāo)的改進(jìn)，例如：祖志文等人[14]將馬氏距離引入有效性指數(shù)，對(duì)其進(jìn)行改進(jìn)排出不同量綱對(duì)聚類干擾；唐益明等人[15]將數(shù)據(jù)幾何結(jié)構(gòu)以及大小集群思想引入有效性指標(biāo)的改進(jìn)，使其適用于復(fù)雜的數(shù)據(jù)結(jié)果，但是對(duì)與簇間存在結(jié)合的簇，聚類效果不好；謝娟英[16]利用方差度量方法重新定義的分離度及緊湊度改進(jìn)有效性指標(biāo)。然而很多有效性指標(biāo)并不是很完善，在判斷自然分布數(shù)據(jù)集聚類的準(zhǔn)確性以及指標(biāo)的可適用范圍等方面存在問(wèn)題。

根據(jù)現(xiàn)有的有效性指標(biāo)的不足之處，提出了一種改進(jìn)的模糊聚類有效性指標(biāo)。該有效性指標(biāo)不僅從簇的幾何結(jié)構(gòu)角度考慮簇內(nèi)緊湊度和簇間分離度，還考慮數(shù)據(jù)樣本簇之間的樣本結(jié)合問(wèn)題。

2 相關(guān)工作

模糊聚類分析可以大致分為兩類：第一類是聚類數(shù)目不確定，利用不同的參數(shù)對(duì)數(shù)據(jù)集進(jìn)行動(dòng)態(tài)聚類，這種聚類方法是基于模糊矩陣的聚類分析方法，第二類是聚類數(shù)目能夠確定，主要目標(biāo)是對(duì)不同的數(shù)據(jù)集做出最佳的聚類結(jié)果，這種方法屬于基于目標(biāo)函數(shù)的聚類分析方法。其中，最廣泛使用和最有效的算法是Bezdek[6]提出的模糊C-均值（FCM）算法。

2.1 模糊C-均值（FCM）算法

假設(shè)數(shù)據(jù)集X 中有n 個(gè)p 維數(shù)據(jù)樣本點(diǎn)，則X={ x1, x2,… ,xn} ∈RP。FCM 算法將數(shù)據(jù)樣本集X 劃分為c 類，并假設(shè)有c 個(gè)聚類中心V={v1,v2, …,vc}。FCM算法可以表示為以下數(shù)學(xué)規(guī)劃問(wèn)題：

最小化：

其中，uij表示隸屬度xj屬于聚類中心vi的程度。U=(uij)c×n是由屬于每一個(gè)數(shù)據(jù)樣本的程度組成的模糊劃分矩陣。m 是權(quán)重指數(shù)，主要用于調(diào)整模糊劃分矩陣的模糊度；定義為樣本間的相似性度量。

FCM的過(guò)程可以描述如下：

步驟1 固定聚類數(shù)c，模糊因子m（通常從1.5 到2.5）；初始化模糊劃分矩陣并讓它滿足公式（2）。

步驟2 根據(jù)公式（3）更新集群中心V(γ+1)={v1,v2,… ,vc}。

步驟3 根據(jù)公式（4）更新模糊劃分矩陣U(γ+1)=(uij)c×n。

其中，i=1,2, ,c,j=1,2, ,n 。

步驟4 計(jì)算e=||U(γ+1)-U(γ)||。如果e ≤η（η是一個(gè)閾值，通常從0.001到0.01），算法停止；或者γ=γ+1，重復(fù)步驟2。

2.2 經(jīng)典的有效性指標(biāo)

（1）Xie-Beni有效性指標(biāo)VXB

Xie-Beni提出的有效性指數(shù)VXB考慮了數(shù)據(jù)樣本的幾何形狀。其定義如公式（5）所示：

其中，uij是模糊隸屬度，c是聚類數(shù)；當(dāng)該指數(shù)取得最小值時(shí)，可以獲得相對(duì)最佳的簇?cái)?shù)c。但該有效性指數(shù)存在局限性，當(dāng)c接近n時(shí)，幾乎每個(gè)數(shù)據(jù)樣本都是一個(gè)簇中心，即

所以

根據(jù)上述公式，當(dāng)簇?cái)?shù)c 無(wú)限接近于樣本數(shù)n 時(shí)，VXB不可能確定簇?cái)?shù)c的最優(yōu)值。即有效性指標(biāo)失去了魯棒性。其中，隨著簇?cái)?shù)的增加，此有效性指數(shù)的作用逐漸減小，穩(wěn)定性逐漸降低。

（2）Bensaid有效性指標(biāo)VBD

Bensaid 提出的有效性指標(biāo)是在Xie-Beni 有效性指標(biāo)的基礎(chǔ)之上進(jìn)行的改進(jìn)，具體指標(biāo)如公式（6）所示：

（3）VFM有效性指標(biāo)

VFM有效性指標(biāo)具體定義如公式（7）所示：

VFM指標(biāo)把劃分熵與模糊劃分因子加入新的有效性指標(biāo)內(nèi)，從而重新定義了緊湊度以及分離度。然而VFM將兩個(gè)距離最小的簇中心的計(jì)算值當(dāng)作分離度，這種方式對(duì)含有離群點(diǎn)的數(shù)據(jù)樣本簇的評(píng)價(jià)不理想。

（4）VUV有效性指標(biāo)

VUV有效性指標(biāo)具體定義如公式（9）所示：

此有效性指標(biāo)將指數(shù)函數(shù)作為計(jì)算數(shù)據(jù)樣本與簇中心的相似度距離，在許多情況下這種距離計(jì)算方法可以消除離群點(diǎn)對(duì)聚類的影響。然而，該有效性指標(biāo)僅僅涉及了數(shù)據(jù)樣本簇的緊湊度以及分離度，并沒(méi)有涉及樣本簇的結(jié)合度對(duì)聚類產(chǎn)生的影響，因此對(duì)于有重合的數(shù)據(jù)樣本簇評(píng)價(jià)結(jié)果并不是很準(zhǔn)確。

3 改進(jìn)指標(biāo)的提出

大多數(shù)研究人員提出的模糊聚類有效性指標(biāo)，例如VXB、VUV、VFM和VBD，所有的重點(diǎn)都集中在兩個(gè)方面：緊湊度和分離度，但忽略簇之間的結(jié)合現(xiàn)象，從而導(dǎo)致了錯(cuò)誤的聚類結(jié)果。

3.1 傳統(tǒng)度量的局限性

當(dāng)簇之間存在部分結(jié)合時(shí)，僅通過(guò)中心點(diǎn)之間的幾何距離不能準(zhǔn)確分析簇間是否分離。如圖1 所示，圖中兩個(gè)不同的模糊劃分圖1（a）和圖1（b），VP和Vq分別代表p 和q 兩個(gè)模糊簇的中心，其簇中心的間距相等。從傳統(tǒng)的分離指數(shù)角度來(lái)看圖1（b）比圖1（a）更分散。然而，傳統(tǒng)的分離度僅限于兩個(gè)劃分的幾何結(jié)構(gòu)上，忽略了簇的形狀分布，沒(méi)有考慮簇之間的結(jié)合情況。

圖1 包含相同分離距離的兩個(gè)不同模糊劃分

3.2 改進(jìn)的有效性指標(biāo)

針對(duì)上述問(wèn)題，提出一種改進(jìn)的模糊聚類有效性指標(biāo)VCSC。該指標(biāo)主要包括兩個(gè)部分：結(jié)合度量（Combi‐nation）和SC（分離度Separation 和緊湊度Compactness）度量。結(jié)合度量是由每個(gè)樣本的聚類之間的結(jié)合程度來(lái)計(jì)算的，簇之間的結(jié)合度量越低，當(dāng)前模糊簇與其他模糊簇之間的間隔就越大。SC 度量的目的是衡量簇內(nèi)緊湊度和簇間分離度，SC 度量值越大，簇內(nèi)緊湊度和簇間分離度越大，聚類結(jié)果越好。因此，獲得較低的結(jié)合度量和較高的SC度量是該評(píng)價(jià)指標(biāo)的研究重點(diǎn)。

改進(jìn)的有效性指標(biāo)具體定義如下：

定義1 結(jié)合度量

為了確定這種樣本點(diǎn)，對(duì)于所有的1 ≤p ≤c，1 ≤q ≤c，設(shè)置閾值γ（一般為γ 值為0.1）。如果滿足t(|ujp-ujq|)≤γ，則確定數(shù)據(jù)樣本處于簇p 和q 的結(jié)合區(qū)域中。簇之間的結(jié)合度定義如公式（11）：

定義2 SC 度量

SC 度量包含兩個(gè)部分：簇內(nèi)緊湊度和簇間分離度。定義如公式（13）：

（1）Sep簇間分離度

Sep表示簇中的分離程度，具體定義如公式（14）：

表示簇之間的分離度，分離度反應(yīng)的是簇之間分離程度，其值越大則表明簇間分離越明顯。

（2）Comp緊湊度

Comp表示簇中的緊湊程度，具體定義如公式（15）：

（3）Pen-i懲罰項(xiàng)

可以看出，索引SC(U,V;c)的值越大，聚類結(jié)果越好。

定義3 有效性指數(shù)VCSC

根據(jù)式（11）、（13），改進(jìn)的模糊聚類有效性指標(biāo)，如公式（16）所示：

有效性指數(shù)表明，Comb(c,U)值越小，簇之間的結(jié)合程度越小；SC(U,V;c)值越大，簇內(nèi)越緊湊，簇之間的分離度越大。顯然，較小的VCSC的值代表更好的聚類結(jié)果。因此，通過(guò)尋找最小值，可以找到聚類的最優(yōu)數(shù)目，從而得到理想的模糊聚類結(jié)果。

當(dāng)簇?cái)?shù)c 無(wú)限接近數(shù)據(jù)集樣本的數(shù)目n 時(shí)，改進(jìn)指標(biāo)可以有效地抑制指標(biāo)索引值趨于0的趨勢(shì)。

證明當(dāng)c →n，

當(dāng)c 趨近n 時(shí)，對(duì)于結(jié)合度Comb(c,U)=0，表示各個(gè)簇之間沒(méi)有結(jié)合。

當(dāng)c →n時(shí)，分子中，如公式（15）所示，其極限值為：

當(dāng)c →n時(shí)，分母中，如公式14所示，其極限值為：

所以，當(dāng)c →n

上述過(guò)程表明，隨著簇?cái)?shù)的增加，分母中簇之間的分離度及分子中的懲罰項(xiàng)減小，但并不等于零，顯然所改進(jìn)的有效性指標(biāo)具有可行性。

所提出的聚類有效性指數(shù)VCSC的詳細(xì)過(guò)程如下：

步驟1 初始化FCM算法的相關(guān)參數(shù)和有效性指標(biāo)：

步驟3 根據(jù)公式（3）、（4），更新簇中心vj和隸屬度矩陣Ui=[uij]。

步驟4 如果||U(γ+1)-U(γ)||≤ξ（ξ閾值，通常從0.000 1到0.01），切換到步驟5。否則切換到步驟3。

步驟5 根據(jù)隸屬矩陣U 和步驟4中的簇中心矩陣，計(jì)算Comb(c,U)和SC(U,V;c)。

步驟6 如果c ?cmax，c=c+1，重復(fù)步驟2；否則，切換到步驟7。

步驟7 根據(jù)公式16計(jì)算VCSC。

步驟8 找到有效性指標(biāo)的最小值，并選擇相應(yīng)的c作為最佳簇?cái)?shù)。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所改進(jìn)指標(biāo)的有效性和準(zhǔn)確性，將VCSC與VXB、VBD、VUV、VFM等有效性指標(biāo)進(jìn)行對(duì)比，并分析在模糊因子m 變化時(shí)，各指標(biāo)在評(píng)價(jià)聚類結(jié)果方面的魯棒性。

4.1 VCSC指標(biāo)有效性驗(yàn)證

實(shí)驗(yàn)數(shù)據(jù)集信息如表1 所示。前4 個(gè)是人工數(shù)據(jù)集，其中數(shù)據(jù)樣本集DataSet2_4 服從均勻分布且簇與簇之間劃分清晰；數(shù)據(jù)樣本集DataSet2_6 服從高斯分布且內(nèi)含噪聲數(shù)據(jù)點(diǎn)；數(shù)據(jù)樣本集DataSet2_3 服從高斯分布且3 個(gè)簇之間存在結(jié)合現(xiàn)象；數(shù)據(jù)樣本集DataSet2_5服從高斯分布且5 個(gè)簇之間存在結(jié)合現(xiàn)象；后4 者為UCI的真實(shí)數(shù)據(jù)集。這些數(shù)據(jù)集是常用的測(cè)試數(shù)據(jù)集，在屬性的數(shù)量和集群的數(shù)量上有一定的區(qū)別。FCM 中的參數(shù)設(shè)置：終止閾值ξ=0.001，模糊因子m=2.0，||*||2是歐氏距離的平方，閾值α 一般設(shè)置為0.6，γ 一般設(shè)置為0.1。各指標(biāo)在不同數(shù)據(jù)集上聚類結(jié)果如表2 所示。

為了更加直觀地說(shuō)明改進(jìn)指標(biāo)的有效性，選取具有代表性的數(shù)據(jù)集DataSet2_6、DataSet2_3、DataSet2_5、Iris、Seeds、wine 進(jìn)行實(shí)驗(yàn)，如圖2～7 分別顯示在5 個(gè)有效性指標(biāo)的索引值。

表1 實(shí)驗(yàn)中的人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集

表2 不同數(shù)據(jù)集上的各指標(biāo)的聚類數(shù)

圖2 Dataset2_6聚類個(gè)數(shù)與索引結(jié)果分布圖

圖3 Dataset2_3聚類個(gè)數(shù)與索引結(jié)果分布圖

圖4 數(shù)據(jù)集Dataset2_5聚類個(gè)數(shù)與索引結(jié)果分布圖

圖5 Iris聚類個(gè)數(shù)與索引結(jié)果分布圖

圖6 Seeds聚類個(gè)數(shù)與索引結(jié)果分布圖

圖7 Wine聚類個(gè)數(shù)與索引結(jié)果分布圖

由表2 和圖2～7 中可以看出：雖然VXB、VBD、VUV、VFM等常用指標(biāo)都能對(duì)均勻分布的數(shù)據(jù)集進(jìn)行準(zhǔn)確聚類，而VUV指標(biāo)能夠?qū)肼暤臄?shù)據(jù)集也能達(dá)到較好的聚類效果，但是上述各指標(biāo)在具有噪聲的、存在簇間結(jié)合的和公開(kāi)數(shù)據(jù)集上聚類效果較差。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的有效性指標(biāo)VCSC不僅能夠?qū)鶆蚍植嫉臄?shù)據(jù)集準(zhǔn)確聚類，而且對(duì)含有噪聲的數(shù)據(jù)集、存在簇間結(jié)合的數(shù)據(jù)集和真實(shí)數(shù)據(jù)集都具有良好的效果。

4.2 m值對(duì)指標(biāo)評(píng)價(jià)準(zhǔn)確性的驗(yàn)證

FCM 中Jmin的目標(biāo)函數(shù)依賴于模糊指標(biāo)m，若有效性指標(biāo)對(duì)m 不敏感，則認(rèn)為有效性指標(biāo)是穩(wěn)定的。本節(jié)測(cè)試5 個(gè)有效性指標(biāo)以檢驗(yàn)其是否依賴于模糊指數(shù)m。Pal 和Bezdek[17]的演示給出了模糊指數(shù)m ∈[1.5，2.5]的值范圍。存在簇間結(jié)合的數(shù)據(jù)集DataSet2_5 和DataS‐et2_3、Iris 中，驗(yàn)證有效性指標(biāo)在模糊指數(shù)m 變化時(shí)是否穩(wěn)定。表3～5 分別顯示了DataSet2_5 和DataSet2_3、Iris中數(shù)據(jù)樣本在各中指標(biāo)下的最佳聚類數(shù)。

由表3～5 可知，VXB、VBD、VUV、VFM隨著m 的變化，聚類結(jié)果也發(fā)生變化。僅VCSC指標(biāo)不隨m 的變化而變化，并且能夠找到這些數(shù)據(jù)集中聚類的最佳數(shù)目，具有較高的準(zhǔn)確性。實(shí)驗(yàn)表明，本文提出的有效性指標(biāo)對(duì)模糊加權(quán)指數(shù)m 具有較高的魯棒性和準(zhǔn)確性。

表3 DataSet2_5中隨著m 變化時(shí)不同指標(biāo)的簇?cái)?shù)

表4 DataSet2_3中隨著m 變化時(shí)不同指標(biāo)的簇?cái)?shù)

表5 Iris中隨m 變化時(shí)不同有效度指標(biāo)的簇?cái)?shù)

5 結(jié)論

本文首先介紹了模糊聚類有效性指標(biāo)的幾種類型，并對(duì)這些指標(biāo)進(jìn)行了分析。針對(duì)其不足之處，提出了一種改進(jìn)的模糊聚類有效性指標(biāo)。在充分考慮了簇內(nèi)緊湊度和簇間分離度的同時(shí)也考慮了大多數(shù)有效性指標(biāo)沒(méi)有涉及的簇間結(jié)合程度。該指標(biāo)不但解決了當(dāng)簇間存在一定程度結(jié)合時(shí)無(wú)法取得最優(yōu)聚類數(shù)目的問(wèn)題，而且弱化了簇?cái)?shù)趨于無(wú)窮時(shí)指標(biāo)值接近于0 值對(duì)有效性的影響。最后通過(guò)實(shí)驗(yàn)驗(yàn)證了改進(jìn)的有效性指標(biāo)具有較好的準(zhǔn)確性和魯棒性。