基于改進馬氏距離的模糊C聚類研究

趙小強，李雄偉

(蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州，730050)

基于改進馬氏距離的模糊C聚類研究

趙小強，李雄偉

(蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州，730050)

提出一種基于改進馬氏距離的模糊C聚類算法，先通過對數據集進行加權，然后對數據的馬氏距離進行協方差處理。研究結果表明：該方法可以對高相關屬性的數據集進行有效分類，能降低分錯率，該方法具有可行性和有效性。

模糊C均值；高相關屬性；馬氏距離；協方差矩陣

模糊聚類算法是基于模糊論的聚類算法研究，其算法迭代速度比一般的聚類算法快，近年來，廣泛應用于圖像處理、機器學習、模式識別和數據挖掘等方面，逐漸成為一個研究熱點。在諸多的聚類算法中，模糊C均值(FCM)算法的理論比較成熟，應用范圍相對廣泛，它是以硬聚類(HCM)為基礎經過進一步推導而得出的[1?2]。為了使FCM算法具有一般性，Bezdek[3]引進參數m，使 FCM的目標函數推廣到了無限族，討論了 FCM 的收斂問題，并證明了其最終收斂到一個極值，從而演變成一般情況下的 FCM 算法。近年來，FCM算法已經成為大家深入研究的重點領域，許多學者針對實際情況遇到的不同問題，提出了各種改進的聚類算法，如李潔等[4]針對樣本向量中各維特征對模式分類的不同影響，提出基于特征加權的模糊聚類新算法；Xing等[5]為了解決樣本分布不均的問題，提出了一種基于專家模型的自適應FCM；李翠霞等[6]提出的一種模糊聚類算法歸類的研究是針對噪聲數據敏感和魯棒性較差問題。但是傳統的 FCM 算法是主要解決空間中數據點與點之間的聚類問題，它只適用于凸型數據，而不適用于非凸型數據。Schikuta等[7]提出 Bang聚類系統在處理數據結構方面有所提高，但是當數據的維度增加時，其效果不理想。FCM聚類中的目標函數采用馬氏距離，因為馬氏距離可以調整數據點在空間中的分布，使相關性強的數據點集中在一起，可以比較好地解決歐式距離屬性相關的問題。然而分布點的集中又會帶來數據高斯分布的問題，使錯分率的概率大大增加。而且，在馬氏距離計算中如何解決奇異性問題是個難點。因此，本文作者通過改進協方差矩陣的估計來提高馬氏距離聚類分析效率，并將改進的馬氏距離的FCM算法應用于UCI數據集聚類中，實驗驗證了該方法的可行性和有效性。

1 模糊C均值聚類方法

2 基于改進馬氏距離的模糊 C均值聚類

2.1 特征空間的馬氏距離

式中，(1/m)m×1代表元素均為1/m的m維列矢量。樣本xi到樣本總體X的馬氏距離為：

若協方差矩陣Σi是奇異的，則馬氏距離無解。依據矩陣的相關理論，對于任意一個秩為r的實對稱半正定矩陣可按以下方式分解，Σi為實對稱半正定矩陣，設Σi的秩為r，則Σi可以分解為ΣTi=AGA，G為r×r的對角陣，它由Σi的非0特征值構成，G是非奇異的。A為r×m矩陣，由G中特征值所對應的特征向量構成，且ATA為r×r的單位陣。分解后，便可根據G的逆來求Σi的偽逆：

2.2 基于改進馬氏距離的模糊聚類

在所有的測度計量中，往往通過對屬性的描述來體現兩者之間的相似性，馬氏距離就是一種測量相似度的方法。一般情況下，將重要位置的屬性賦予相對比較高的權重，從而突出屬性相似度對聚類效果的影響。在樣本空間中，樣本i的每個特征p在類c上的馬氏距離公式為：

基于式(6)，本文提出一種改進馬氏距離模糊C均值聚類。計算馬氏距離，首先要根據已知的樣本數估計協方差矩陣。此時，協方差矩陣的估計值必然與樣本個體的類別有關系，而類別的判定又取決于聚類分析，那么這就會陷入一個不斷循環的困境。因此，對于馬氏距離中的協方差矩陣通常用全體數據的樣本協方差矩陣來代替。因為這種做法忽略了類別對取樣結果的影響，所以需要將變量的權重和樣本的類別對協方差矩陣估計的影響考慮進去，從而對協方差矩陣進行從新估計。

M-FCM算法步驟如下：

步驟1 確定類數c，并且設定各個變量的權重ωi，i=1，…，p；

步驟 2 進行初始化處理：給定聚類類別數c，2≤c≤n，n是數據數，設定迭代停止閾值ε，初始化聚類中心矩陣 A(0)，設置迭代計數器b=0，用式(3)計算或更新隸屬度矩陣U(b)，用式(2)更新聚類中心矩陣A(b+1)，如果||A(b)?A(b+1)||＜ε，則算法停止并輸出隸屬度矩陣U，和聚類中心A；

步驟5 對數據進行加權馬氏化處理, 得到新的數據集；

步驟6 對新數據集進行歐氏距離聚類分析；

步驟7 重復步驟3～6，直到聚類結果收斂為止。

3 實驗驗證

從UCI中選取4個數據集對算法進行驗證。首先將各數據集使用式(7)進行加權馬氏距離化處理，然后用FCM算法。算法的測試平臺為WindowsXP，選擇CPU P4 2.66 GHz，內存256 Mb的PC機為測試環境，程序的編寫用Matlab語句。

3.1 實驗數據與結果

在UCI數據庫中提取的4個數據集分別為：Iris(鳶尾植物數據庫)，Glass(玻璃識別數據庫)，Wine(葡萄酒數據庫)和Pima(皮馬印第安人糖尿病數據庫)。4個數據集基本特征見表1。表2所示為傳統FCM與新算法的聚類結果的比較，其中M-FCM算法為基于改進馬氏距離的FCM算法。

IRIS數據是鳶尾植物數據庫，最初是用來它測量地理變化的，后來應用在了統計學中。它主要分布在3種不同類別的鳶尾花，即山鳶尾、變色鳶尾和維吉尼亞鳶尾，每一類鳶尾花各占50個樣本。每一個樣本中都有花萼的長度，花萼的寬度，花瓣的長度和花瓣的寬度4個特征作為屬性。其中山鳶尾與其他2類之間能很好的分離，它是線性的。而變色鳶尾和維吉尼亞鳶尾之間存在交叉重疊的部分，是非線性的。

表1 數據集的特征描述Table 1 Characteristic description of data set

表2 不同算法聚類結果的比較Table 2 Comparison of different clustering results

Glass數據集是一種玻璃識別數據庫，主要是應用于犯罪現場。在案情偵破中，通過識別現場留下的玻璃碎片屬性來作為犯罪分子的犯罪證據。主要以折射率、鈉、鎂、鋁、硅、鉀、鈣、鋇、鐵等9個參數作為特征，6個類屬性，它們分別為70個浮點法處理大廈的窗戶、76個非浮點法處理大廈的窗戶、17個浮點法處理車窗、0個非浮點法處理車窗、13個集裝箱、9個餐具、29個前大燈共同構成214個樣本個體。

Wine數據集為生長在 Italy 同一區域不同葡萄園產出的3種葡萄酒，并把它們的化學分析結果的作為樣本，以酒精、灰、蘋果酸、灰的堿度、鎂、總酚類、黃酮、非黃酮酚類、原花色素、顏色強度、OD280/OD315 稀釋的葡萄酒、脯氨酸等13個參數作為數據的特征，一般可以分為3個類別，第1類有59個樣本點，第2類有71個樣本點，第3類有48個樣本點，一共有178個樣本,由上面的13個特征和178個樣本點一起構成了178 ×13 維矩陣。

Pima數據集是皮馬印第安人糖尿病數據庫，主要是指在年滿 21歲的女性皮馬印第安人的遺傳病例參數、包括懷孕次數、 2 h血漿葡萄糖濃度在口服葡萄糖耐量試驗、舒張壓、三頭肌皮褶厚度(mm)、 2 h血清胰島素、身體質量指數、糖尿病血統函數、年齡、變量(0或1)等8個屬性，其中類值1被解釋為“檢測呈陽性糖尿病其值為268，類值0被解釋為“檢測呈陰性糖尿病”，其值為500。

3.2 實驗結果分析

M-FCM算法的聚類效果比FCM算法的更優，對不同的數據類型，算法精確度的提高程度有很大的差異性。當數據集屬性相關性的程度增大時，該算法的精確度普遍提高。Glass數據集精確度提高非常明顯，Wine和Pima數據集的精確度幅度次之；而且M-FCM算法在迭代過程中均收斂。這說明M-FCM算法的適用不僅跟數據集的屬性相關度有關，而且其結果比FCM的更好。

4 結論

(1) 提出了一種數據加權馬氏距離的 FCM(即M-FCM)算法，將馬氏距離模糊C均值聚類算法分成2個步驟，首先是對數據加權重之后進行馬氏化處理，然后在采用歐氏距離的聚類過程，反復進行迭代直到結果收斂為止。

(2) 采用改進之后的馬氏距離對Iris，Glass，Wine和Pima數據集進行仿真，聚類效果有提高顯著。

(3) 雖然馬氏距離在進行分類時有較好的性質，但是在處理協方差矩陣的估計問題時，方法比較多，如何選擇一種最有效的方式是以后關注的問題。

[1] Duda R O, Hart P E. Pattern classification and scene analysis[M].New York: John Wiley &Sons, 1973: 230?235.

[2] Duma J C. Well-separated clusters and the optimal fuzzy partitious[J]. J Cybernet, 1974, 4(1): 95?104.

[3] Bezdek J C. Pattern recognition with fuzzy objective function algorithms[M]. New York: Plenum Press, 1981: 193?203.

[4] 李潔, 高新波, 焦李成. 基于特征加權的模糊聚類新算法[J].電子學報, 2006, 34(1): 89?92.

LI Jie, GAO Xinbo, JIAO Licheng. A new feature weighted fuzzy clustering algorithm[J]. Acta Electronica Sinica, 2006,34(1): 89?92.

[5] XING HongJie, HUA Baogang. An adaptive fuzzy C-mean clustering-based mixture of experts model for unlabeled data classification[J]. Nero Computing, 2008, 71: 1008?1021.

[6] 李翠霞, 于劍. 一種模糊聚類算法歸類的研究[J]. 北京交通大學學報, 2005, 29(2): 17?21.

LI Cuixia, YU Jian. Study on the classification of a kind of fuzzy clustering algorithm[J]. Journal of Beijing Jiao Tong University,2005, 29(2): 17?21.

[7] Schikuta E, Erhart M. The BANG-clustering system: Grid-bused data analysis[C]//Lecture Notes in Computer Science Band 1280.London: Springer, 1997: 513?524.

(編輯 趙俊)

A fuzzy C-means clustering algorithm based on improved Mahalanobis distance

ZHAO Xiaoqiang, LI Xiongwei

(College of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China)

A fuzzy C-means clustering algorithm based improved Mahalanobis distance was proposed. The datasets were weighted and then covariances of Mahalanobis distance were calculated. The results show that the method can effectively cluster for datesets of high correlation and reduce error probability. The method has effectiveness and feasibility.

fuzzy C-mean clustering; high correlation property; Mahalanobis distance; covariance matrix

TP273

A

1672?7207(2013)S2?0195?04

2013?03?01；

2013?05?02

甘肅省高?；究蒲袠I務費項目省財政廳項目(1203ZTC061)；甘肅省制造業信息化工程技術研究中心開放基金資助項目(1112RJZA028)

趙小強(1969?)，男，陜西岐山人，博士，教授，從事生產調度、數據挖掘與故障診斷研究；E-mail：xqzhao2008@gmail.com