改進的模糊C-均值聚類有效性指標

嚴加展，陳 華，李 陽

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

2.山東科技大學 計算機科學與工程學院，山東 青島266590

1 引言

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

根據現有的有效性指標的不足之處，提出了一種改進的模糊聚類有效性指標。該有效性指標不僅從簇的幾何結構角度考慮簇內緊湊度和簇間分離度，還考慮數據樣本簇之間的樣本結合問題。

2 相關工作

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

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

假設數據集X 中有n 個p 維數據樣本點，則X={ x1, x2,… ,xn} ∈RP。FCM 算法將數據樣本集X 劃分為c 類，并假設有c 個聚類中心V={v1,v2, …,vc}。FCM算法可以表示為以下數學規劃問題：

最小化：

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

FCM的過程可以描述如下：

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

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

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

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

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

2.2 經典的有效性指標

（1）Xie-Beni有效性指標VXB

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

其中，uij是模糊隸屬度，c是聚類數；當該指數取得最小值時，可以獲得相對最佳的簇數c。但該有效性指數存在局限性，當c接近n時，幾乎每個數據樣本都是一個簇中心，即

所以

根據上述公式，當簇數c 無限接近于樣本數n 時，VXB不可能確定簇數c的最優值。即有效性指標失去了魯棒性。其中，隨著簇數的增加，此有效性指數的作用逐漸減小，穩定性逐漸降低。

（2）Bensaid有效性指標VBD

Bensaid 提出的有效性指標是在Xie-Beni 有效性指標的基礎之上進行的改進，具體指標如公式（6）所示：

（3）VFM有效性指標

VFM有效性指標具體定義如公式（7）所示：

VFM指標把劃分熵與模糊劃分因子加入新的有效性指標內，從而重新定義了緊湊度以及分離度。然而VFM將兩個距離最小的簇中心的計算值當作分離度，這種方式對含有離群點的數據樣本簇的評價不理想。

（4）VUV有效性指標

VUV有效性指標具體定義如公式（9）所示：

此有效性指標將指數函數作為計算數據樣本與簇中心的相似度距離，在許多情況下這種距離計算方法可以消除離群點對聚類的影響。然而，該有效性指標僅僅涉及了數據樣本簇的緊湊度以及分離度，并沒有涉及樣本簇的結合度對聚類產生的影響，因此對于有重合的數據樣本簇評價結果并不是很準確。

3 改進指標的提出

大多數研究人員提出的模糊聚類有效性指標，例如VXB、VUV、VFM和VBD，所有的重點都集中在兩個方面：緊湊度和分離度，但忽略簇之間的結合現象，從而導致了錯誤的聚類結果。

3.1 傳統度量的局限性

當簇之間存在部分結合時，僅通過中心點之間的幾何距離不能準確分析簇間是否分離。如圖1 所示，圖中兩個不同的模糊劃分圖1（a）和圖1（b），VP和Vq分別代表p 和q 兩個模糊簇的中心，其簇中心的間距相等。從傳統的分離指數角度來看圖1（b）比圖1（a）更分散。然而，傳統的分離度僅限于兩個劃分的幾何結構上，忽略了簇的形狀分布，沒有考慮簇之間的結合情況。

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

3.2 改進的有效性指標

針對上述問題，提出一種改進的模糊聚類有效性指標VCSC。該指標主要包括兩個部分：結合度量（Combi‐nation）和SC（分離度Separation 和緊湊度Compactness）度量。結合度量是由每個樣本的聚類之間的結合程度來計算的，簇之間的結合度量越低，當前模糊簇與其他模糊簇之間的間隔就越大。SC 度量的目的是衡量簇內緊湊度和簇間分離度，SC 度量值越大，簇內緊湊度和簇間分離度越大，聚類結果越好。因此，獲得較低的結合度量和較高的SC度量是該評價指標的研究重點。

改進的有效性指標具體定義如下：

定義1 結合度量

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

定義2 SC 度量

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

（1）Sep簇間分離度

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

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

（2）Comp緊湊度

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

（3）Pen-i懲罰項

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

定義3 有效性指數VCSC

根據式（11）、（13），改進的模糊聚類有效性指標，如公式（16）所示：

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

當簇數c 無限接近數據集樣本的數目n 時，改進指標可以有效地抑制指標索引值趨于0的趨勢。

證明當c →n，

當c 趨近n 時，對于結合度Comb(c,U)=0，表示各個簇之間沒有結合。

當c →n時，分子中，如公式（15）所示，其極限值為：

當c →n時，分母中，如公式14所示，其極限值為：

所以，當c →n

上述過程表明，隨著簇數的增加，分母中簇之間的分離度及分子中的懲罰項減小，但并不等于零，顯然所改進的有效性指標具有可行性。

所提出的聚類有效性指數VCSC的詳細過程如下：

步驟1 初始化FCM算法的相關參數和有效性指標：

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

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

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

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

步驟7 根據公式16計算VCSC。

步驟8 找到有效性指標的最小值，并選擇相應的c作為最佳簇數。

4 實驗結果與分析

為了驗證所改進指標的有效性和準確性，將VCSC與VXB、VBD、VUV、VFM等有效性指標進行對比，并分析在模糊因子m 變化時，各指標在評價聚類結果方面的魯棒性。

4.1 VCSC指標有效性驗證

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

為了更加直觀地說明改進指標的有效性，選取具有代表性的數據集DataSet2_6、DataSet2_3、DataSet2_5、Iris、Seeds、wine 進行實驗，如圖2～7 分別顯示在5 個有效性指標的索引值。

表1 實驗中的人工數據集和真實數據集

表2 不同數據集上的各指標的聚類數

圖2 Dataset2_6聚類個數與索引結果分布圖

圖3 Dataset2_3聚類個數與索引結果分布圖

圖4 數據集Dataset2_5聚類個數與索引結果分布圖

圖5 Iris聚類個數與索引結果分布圖

圖6 Seeds聚類個數與索引結果分布圖

圖7 Wine聚類個數與索引結果分布圖

由表2 和圖2～7 中可以看出：雖然VXB、VBD、VUV、VFM等常用指標都能對均勻分布的數據集進行準確聚類，而VUV指標能夠對含噪聲的數據集也能達到較好的聚類效果，但是上述各指標在具有噪聲的、存在簇間結合的和公開數據集上聚類效果較差。實驗結果表明，改進的有效性指標VCSC不僅能夠對均勻分布的數據集準確聚類，而且對含有噪聲的數據集、存在簇間結合的數據集和真實數據集都具有良好的效果。

4.2 m值對指標評價準確性的驗證

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

由表3～5 可知，VXB、VBD、VUV、VFM隨著m 的變化，聚類結果也發生變化。僅VCSC指標不隨m 的變化而變化，并且能夠找到這些數據集中聚類的最佳數目，具有較高的準確性。實驗表明，本文提出的有效性指標對模糊加權指數m 具有較高的魯棒性和準確性。

表3 DataSet2_5中隨著m 變化時不同指標的簇數

表4 DataSet2_3中隨著m 變化時不同指標的簇數

表5 Iris中隨m 變化時不同有效度指標的簇數

5 結論

本文首先介紹了模糊聚類有效性指標的幾種類型，并對這些指標進行了分析。針對其不足之處，提出了一種改進的模糊聚類有效性指標。在充分考慮了簇內緊湊度和簇間分離度的同時也考慮了大多數有效性指標沒有涉及的簇間結合程度。該指標不但解決了當簇間存在一定程度結合時無法取得最優聚類數目的問題，而且弱化了簇數趨于無窮時指標值接近于0 值對有效性的影響。最后通過實驗驗證了改進的有效性指標具有較好的準確性和魯棒性。