基于歐式加權法的模糊C均值聚類算法

馬欣野，劉亞靜，劉 童

（華北理工大學礦業工程學院，河北 唐山 063200）

0 引言

在大數據時代背景下，無監督學習聚類算法的地位尤為突出[1]，可以說已成為當前數據挖掘的主要研究手段。但是該算法存在著一定的缺陷，比如眾多客觀事物中并不能直觀清楚地了解它們之間存在的線性或非線性關系，使得傳統聚類算法不能有效描述客觀事物間的特征關系。模糊聚類分析方法作為一種無監督學習聚類算法，無需專家指導和預先獲取數據樣本，就可借助模糊數學思想，根據一定的準則對客觀事物進行區分和分類。由于模糊聚類分析可以有效描述客觀事物樣本數據類間的模糊關系，已被廣泛應用于經濟學[2]、信息科學[3-5]、工程技術科學[6-8]等許多領域。模糊聚類分析中最常用的樣本間距離度量方法為歐式距離方法，該方法是一種二范數形式，可用來表征樣本類屬性間的模糊距離程度。然而，相關性會由于類間屬性值相差較大或者線性變換而產生形變，這樣就導致樣本對象間所計算出來的相似度不準確。

標準差在統計學和金融學中用來描述樣本數據的不確定程度（風險），信息熵在信息論中被用來描述樣本數據的不確定程度，在一定程度上標準差和信息熵是成正比的，而標準差和模糊熵權則成反比。即數據波動程度越大，樣本數據的無序性及離散程度也就越大，標準差和熵值也就越大，而該樣本數據對系統的影響（權重）越?。环粗瑪祿▌映潭仍叫?，樣本數據就越有序，離散程度越小，標準差和熵值也就越小，該樣本數據對系統的影響（權重）也就越大。本研究提出的基于加權歐式距離的FCM算法，就是將標準差、熵權法和FCM相結合的一種算法。

1 加權的FCM模型確立

1.1 距離的選取

模糊C均值聚類算法是將數據集的相似性樣本歸為若干個類的方法，一般情況下，常用距離作為分類統計量來計算各個數據對象之間的相異度（距離）。目前，歐氏距離、馬氏距離、絕對距離等為通常選取的距離測度方法[9]，模糊C均值聚類算法通常情況下采用歐氏距離作為距離度量方法，其定義如下：

式中，Xi，Xj分別為兩個樣本向量。

采用歐氏距離度量數據對象之間相異度的聚類分析常對樣本各個指標對象一視同仁，統一處理，計算出來的對象間距離是硬性的，還不能準確表示對象之間的所屬關系。將樣本數據比作一個生態系統，生態系統內不同子系統間既是獨立的單個系統，同時也相互聯系，組成一個大的系統。即各個小系統之間的類屬關系不單單取決于它們之間的硬性距離，還取決于這個小系統本身的生態特性，也就是說樣本對象對整體樣本數據的影響程度（權重）是不同的。因此，依據樣本對象自身特有的分布特征賦予不同的權重，以滿足樣本數據系統整體的特征多樣性。加權的歐氏距離表示如下：

其中，wk(k=1,2,…,L)表示每個變量的權重。其權重系數wk的取值是否合理，是否符合實際，直接關系到是否可以反映各個指標對象的數據分布特征，間接則是影響最終聚類結果的好壞。因此，在對數據指標對象賦權的過程中，既要符合數據在現實世界的實際意義，又要遵從樣本數據指標對象本身的分布特征。針對這一問題，提出了通過將模糊熵權法和標準差相結合對歐式距離進行加權的模糊C均值聚類方法。

1.2 權重的確定

通過上面對歐式距離的加權，使用wk作為表征不同變量在全局中所占據的不同權重，其定義如下：

由上式可知，wk值有效表征了數據樣本的分布特征，wj為樣本指標的熵權重，代表了不同指標之間的權重占比，考慮的是樣本數據的整體信息；sj為樣本指標的標準差，考慮的是各指標數據內部的緊湊程度。而且當熵權重越大時，熵值則越小，樣本指標就越有序，標準差sj就越小，說明此樣本數據對系統的影響（權重）越大，而此時加權值wj正好最大；反之，當熵權重越小時，則熵值越大，樣本指標就越無序，標準差sj就越大，說明此樣本數據對系統的影響（權重）越小，而此時加權值wj正好最小。以下為熵權重的定義過程。

1）定義一個系統的整體樣本數據，假設Xij為一個樣本矩陣，其所代表的是第i個樣本的第j個指標的數值（i=1,2,…,n;j=1,2,…,m）。

2）指標的歸一化處理：異質指標同質化。樣本指標之間一般存在不同的量綱，這致使構建的評價指標間不能達成統一的尺度[10]，無法獲取準確的聚類結果。因此，對選取的指標需要提前進行標準化處理，進而可以消除變量之間的量綱關系，從而使數據之間產生可比性關系[11-12]。此外，由于每個指標的作用效果分為正向負向，應對指標采用特定的標準化方式[10]。其具體方法如下。

正向指標：

負向指標：

式中，Xij為標準化后數據；X'ij為原始數據；minXj為第j個指標中的最小值；maxXj為第j個指標中的最大值；n為分類組的個數，m為指標數。

3）計算第j項指標下第i個樣本對象占該指標的比重：

式中，i=1,2,…,n;j=1,2,…,m。

4）計算第j項指標的熵值：

其中，k=1/ln(n)>0，滿足ej≥0。

5）計算信息熵冗余度：

6）計算各項指標的權值：

2 模糊C均值聚類方法

假設數據集用向量Xi=(xi1,xi2,…,xiL)（i=1,2,…,n）表示，其中n為樣本個數，L為每個樣本的指標個數，xiL為第i個樣本的第L個指標數值。FCM算法就是基于目標函數的大小不斷優化樣本數據集的隸屬度和聚類中心，直到最終獲取均勻的幾個模糊子集[13]。其迭代過程終止條件分為兩種情況，一種是迭代次數達到預先設定的數值，另一種是目標函數達到最小閾值，通常情況下最小閾值的誤差限設置為exp-5。目標函數是由隸屬度、樣本到聚類中心的偏差結合構成[14]。其中隸屬度矩陣U的取值范圍在0到1之間。另外，加上歸一化規定，一個數據集的隸屬度的總和等于1，即：

樣本數據到各個聚類中心的距離用dij來表示，m表示加權指數，用vi表示聚類中心，則dij=‖vi-xj‖計算結果為聚類中心與數據點間的加權歐式距離。那么FCM的價值函數的一般化形式為：

構造如下新的目標函數，即可求得使式（11）達到最小值的必要條件：

上式中，λj（j=1,2,…,n）為拉格朗日乘子，對參量求導可得使得式（11）達到最小的兩個必要條件，如下：

由上述推導可知FCM算法迭代過程，即不斷優化目標函數以確定聚類中心vi和隸屬矩陣U的過程，當目標函數的值小于前后兩次的誤差限閾值或者大于迭代次數時停止。

3 數據來源與研究結果

3.1 數據集

本試驗采用Iris數據集作為測試數據集。Iris數據集是國際公認比較無監督聚類方法效果好壞的典型數據集[15]，該數據集廣泛應用于數據挖掘和分類領域。Iris數據集以鳶尾花的萼片長度和寬度、花瓣長度和寬度四種特征作為數據的分類屬性[16]，數據集分為了3類，分別是山鳶尾（Setosa）、雜色鳶尾（Versicolour）、維吉尼亞鳶尾（Virginica），每類分為50個數據樣本，數據集因此共由150個數據組成。

3.2 實驗步驟

1）初始化參數C、模糊加權指數m，最大迭代次數以及終止誤差限條件；

2）初始化隸屬矩陣U，并進行迭代更新；

3）用式（13）更新聚類中心（i=1,…,c），c是數量集分為聚類中心個數，也就是數據集種類的個數；

4）更新目標函數，當目標函數的值小于前后兩次的誤差限閾值或者大于迭代次數時，算法停止。

3.3 實驗分析

在MATLAB中分別用FCM聚類算法和加權FCM聚類算法對Iris數據集聚類分析，結果如表1、圖1所示。

表1 Iris數據聚類結果Table 1 Iris data clustering results

根據圖1結果，其試驗分析如下。

由圖1可見，Iris數據集分為了三類，其中Setosa這一類可由加權和未加權算法全部識別出來。并且可以明顯看出，Setosa這一類與另外兩類在空間內并無重疊，線性可分，而另外兩類局部重疊。

圖1 Iris數據聚類結果Fig.1 Iris data clustering results

根據表1結果，其試驗分析如下。

由表1可見，Iris數據集同樣分為了三類，其中加權和未加權FCM算法都可將Setosa這一類全部識別，并且可以明確地確定獲取另外兩類樣本加權和未加權FCM算法下的個體重疊數量。結果表明，加權算法比未加權算法可以更為有效地識別Iris數據集重疊部分，具有較強的魯棒性，并將識別率從89.33%提高到95.33%。

4 結論

通過以上研究結果，可以得到如下結論。

1）數據本身所具有的特征屬性在空間內所呈現的幾何關系有所不同，因而不同屬性對系統數據的貢獻值不同，所以在進行評價分類時需要確定空間權重系數。

2）通過將加權FCM和未加權FCM進行比較：將模糊熵權法和標準差相結合，獲取的權重能夠更為客觀地反映數據之間的真實分布情況，使得獲取途徑更加智能。

3）實驗表明，未加權后的FCM算法更為有效地提高了分類結果精度。