基于改進(jìn)馬氏距離的模糊C聚類研究

趙小強(qiáng)，李雄偉

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

基于改進(jìn)馬氏距離的模糊C聚類研究

趙小強(qiáng)，李雄偉

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

提出一種基于改進(jìn)馬氏距離的模糊C聚類算法，先通過對(duì)數(shù)據(jù)集進(jìn)行加權(quán)，然后對(duì)數(shù)據(jù)的馬氏距離進(jìn)行協(xié)方差處理。研究結(jié)果表明：該方法可以對(duì)高相關(guān)屬性的數(shù)據(jù)集進(jìn)行有效分類，能降低分錯(cuò)率，該方法具有可行性和有效性。

模糊C均值；高相關(guān)屬性；馬氏距離；協(xié)方差矩陣

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

1 模糊C均值聚類方法

2 基于改進(jìn)馬氏距離的模糊 C均值聚類

2.1 特征空間的馬氏距離

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

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

2.2 基于改進(jìn)馬氏距離的模糊聚類

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

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

M-FCM算法步驟如下：

步驟1 確定類數(shù)c，并且設(shè)定各個(gè)變量的權(quán)重ωi，i=1，…，p；

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

步驟5 對(duì)數(shù)據(jù)進(jìn)行加權(quán)馬氏化處理, 得到新的數(shù)據(jù)集；

步驟6 對(duì)新數(shù)據(jù)集進(jìn)行歐氏距離聚類分析；

步驟7 重復(fù)步驟3～6，直到聚類結(jié)果收斂為止。

3 實(shí)驗(yàn)驗(yàn)證

從UCI中選取4個(gè)數(shù)據(jù)集對(duì)算法進(jìn)行驗(yàn)證。首先將各數(shù)據(jù)集使用式(7)進(jìn)行加權(quán)馬氏距離化處理，然后用FCM算法。算法的測(cè)試平臺(tái)為WindowsXP，選擇CPU P4 2.66 GHz，內(nèi)存256 Mb的PC機(jī)為測(cè)試環(huán)境，程序的編寫用Matlab語(yǔ)句。

3.1 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

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

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

表1 數(shù)據(jù)集的特征描述Table 1 Characteristic description of data set

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

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

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

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

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

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

4 結(jié)論

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

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

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

[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] 李潔, 高新波, 焦李成. 基于特征加權(quán)的模糊聚類新算法[J].電子學(xué)報(bào), 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]. 北京交通大學(xué)學(xué)報(bào), 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

甘肅省高校基本科研業(yè)務(wù)費(fèi)項(xiàng)目省財(cái)政廳項(xiàng)目(1203ZTC061)；甘肅省制造業(yè)信息化工程技術(shù)研究中心開放基金資助項(xiàng)目(1112RJZA028)

趙小強(qiáng)(1969?)，男，陜西岐山人，博士，教授，從事生產(chǎn)調(diào)度、數(shù)據(jù)挖掘與故障診斷研究；E-mail：xqzhao2008@gmail.com