改進型特征權(quán)重自調(diào)節(jié)K-均值聚類算法

支曉斌， 許朝暉

(1. 西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121;2. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

改進型特征權(quán)重自調(diào)節(jié)K-均值聚類算法

支曉斌1， 許朝暉2

(1. 西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121;2. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

針對特征權(quán)重自調(diào)節(jié)K-均值聚類(FWSA-KM)算法對噪聲敏感的問題，提出一種改進型特征權(quán)重自調(diào)節(jié)K-均值聚類(IFWSA-KM)算法。用一種非歐氏距離代替FWSA-KM算法中的歐氏距離，以增加聚類算法的抗噪聲性能。通過用人工數(shù)據(jù)和真實數(shù)據(jù)的對比性實驗，可驗證IFWSA-KM算法的有效性。

聚類算法；特征權(quán)重；魯棒性；非歐氏距離

聚類分析是指用數(shù)學(xué)的方法研究和處理給定對象的分類問題，它是多元統(tǒng)計分析的方法之一，也是在無監(jiān)督模式識別中的一個重要分支[1]。在眾多的聚類算法中，由MacQeen提出K-均值聚類(K-means, KM)算法具有其簡單、快速的優(yōu)點，因此被廣泛應(yīng)用于科學(xué)研究和工業(yè)應(yīng)用中，成為一種流行的聚類算法。盡管KM算法得到了廣泛的應(yīng)用，但KM算法卻存在很多缺點，如過分依賴于初始中心點的選取，容易受到數(shù)據(jù)中噪聲的影響，不能自動選取特征等。為了提高聚類算法的抗噪聲性能，很多學(xué)者都提出了改進的聚類算法。基于魯棒性統(tǒng)計理論，文[2]通過修改KM和FKM的度量，提出了改進型K-均值聚類(AlternativeK-means, AKM)算法和改進型模糊K-均值聚類(Alternative FuzzyK-means, AFKM)算法，AKM與AFKM算法在一定程度上都提高了原算法的抗噪聲性。

傳統(tǒng)KM聚類算法對數(shù)據(jù)的各個特征平等對待，不能自動選擇相關(guān)特征。為了使得KM能夠自動選擇數(shù)據(jù)的特征，眾多學(xué)者提出了基于特征加權(quán)的KM聚類算法。文[3]首先提出了特征加權(quán)K-均值聚類算法。文[4-5]提出了新的特征加權(quán)K-均值聚類算法，在該算法中，特征權(quán)重的優(yōu)化被集成到KM迭代算法中，模糊K-均值聚類算法中隸屬函數(shù)的求解方法被巧妙地用來計算特征權(quán)重，并且新算法沒有犧牲原KM算法的高效性。

文[6]提出一種特征權(quán)重計算的自調(diào)節(jié)機制，并將其嵌入到KM聚類算法中，提出特征權(quán)重自調(diào)節(jié)K-均值聚類(K-means with feature weight self-adjustment mechanism，F(xiàn)WSA-KM)算法,該算法不但使用的參數(shù)較少而且還能不犧牲原KM聚類算法的效率，但有一個問題，使用歐氏距離，當(dāng)數(shù)據(jù)結(jié)構(gòu)復(fù)雜或者帶有噪聲時，F(xiàn)WSA-KM算法的聚類效果并不理想。

鑒于上述問題，同時受到AKM算法的啟發(fā)，為了進一步提升FWSA-KM算法的性能，本文提出一種改進型特征權(quán)重自調(diào)節(jié)K-均值聚類(K-means with an improved feature weight self-adjustment mechanism，IFWSA-KM)算法。由于非歐氏距離的使用，IFWSA-KM算法在迭代計算過程中能夠自適應(yīng)地給數(shù)據(jù)生成一個權(quán)函數(shù)，這使得對聚類中心的估計更加穩(wěn)健，從而提高算法的聚類精度。

1 FWSA-KM算法

設(shè)數(shù)據(jù)集X由n個數(shù)據(jù)點構(gòu)成，即

X={x1,x2,…,xn}。

經(jīng)典KM聚類算法的目標(biāo)函數(shù)為

(1)

其中U=(uij)n×c是隸屬度矩陣。如果第i個數(shù)據(jù)點xi屬于第j個類，則uij=1，否則uij=0，并且

而V=[v1,v2,…,vc]是c個聚類中心構(gòu)成的矩陣。KM聚類算法通過交替迭代優(yōu)化隸屬度矩陣U和聚類中心矩陣V求解。

為了使得KM聚類算法能夠自動對數(shù)據(jù)進行特征選擇，眾多學(xué)者提出了基于特征加權(quán)的KM聚類算法[3-8],其中FWSA-KM聚類算法的目標(biāo)函數(shù)為

minJFWSA-KM(U,V,W)=

(2)

滿足

(3)

(4)

為了求解特征權(quán)重矩陣，文[6]重新定義了另一個目標(biāo)函數(shù)

(5)

滿足

FWSA-KM算法在計算特征權(quán)重時，考慮了類間分離度信息。

若設(shè)

則式(5)可以重寫為

(6)

其中ak是聚類在第k維特征上總的類內(nèi)緊致性度量，bk是聚類在第k維特征上總的類間分離性度量。文獻[6]采用一種特征權(quán)重自調(diào)節(jié)方法來求解上述的優(yōu)化問題。

設(shè)FWSA-KM聚類算法中第t步迭代的特征權(quán)重為集合

(7)

其中

(8)

為第t步迭代的特征權(quán)重調(diào)節(jié)差量。

與其他已有的特征加權(quán)KM聚類算法相比，F(xiàn)WSA-KM算法的優(yōu)點是：(1) 特征權(quán)重的計算考慮了分離性度量；(2) 算法中的參數(shù)較少；(3) 不犧牲原KM聚類算法的效率。

2 IFWSA-KM算法

JIFWSA-KM(U，V,W)=

(9)

滿足

通過迭代求解三個最小化問題,即可最小化式(9)。

問題1 固定

問題2 固定

問題3 固定

針對問題1，如果

(10)

則uij=1,否則uij=0。

問題2的解

(11)

這是關(guān)于vjk的一個非線性方程，可以用不動點迭代法進行求解。

為了求解問題3，令

(12)

(13)

其中

則ak度量了聚類在第k維特征上總的類內(nèi)緊致性，bk度量了聚類在第k維特征上總的類間分離性度量。

為了求解特征權(quán)重矩陣，定義新的目標(biāo)函數(shù)

(14)

滿足

(15)

其中特征權(quán)重調(diào)節(jié)差量

(16)

對式(15)進行規(guī)范化處理，得到特征權(quán)重

(k=1,2,…,m)。

(17)

綜上所述，可以給出詳細的IFWSA-KM聚類算法步驟。

步驟1 初始化聚類中心矩陣

V(0)={V1，V2，…，Vc},

初始的特征權(quán)重矩陣W滿足

步驟2 計算隸屬度矩陣U。

步驟3 計算新的聚類中心矩陣V。

步驟4 由式(17)計算特征權(quán)重矩陣W。

步驟5 如果

則停止；否則，轉(zhuǎn)到步驟2。

3 實驗結(jié)果及其分析

將IFWSA-KM算法與KM算法、AKM算法和FWSA-KM算法，分別對8個真實數(shù)據(jù)進行對比性實驗，以驗證其有效性。

3.1 實驗設(shè)置

從UCI數(shù)據(jù)庫中選取低維的數(shù)據(jù)集Iris，Wine，Letter_abc，User，Satimage，Breastcancer和Dermatology，另外選擇1個高維數(shù)據(jù)集Leukemia進行聚類實驗[8-9]，相關(guān)數(shù)據(jù)特性如表1所示。

表1 數(shù)據(jù)描述

在實驗中，用準(zhǔn)確度和運算時間來衡量聚類的性能。準(zhǔn)確度定義為

(18)

其中nj是數(shù)據(jù)正確分到第j類的數(shù)目。

實驗中，4種算法各運行20次，選取20次運算的最優(yōu)值和平均值作為最終的聚類結(jié)果。最大迭代次數(shù)設(shè)為100，停止閾值設(shè)為10-5。

3.2 算法的聚類精度測試

表2給出了4種聚類算法分別對8個數(shù)據(jù)集進行20次運算的最優(yōu)聚類結(jié)果。

表2 各算法對8組數(shù)據(jù)集聚類的最優(yōu)精度

從表2可以看出，IFWSA-KM算法在7個數(shù)據(jù)集上得到的最優(yōu)聚類精度，明顯優(yōu)于其他3種聚類算法。由于在聚類運算中，最優(yōu)結(jié)果只是所有結(jié)果中最好的情況，表3給出了4種聚類算法分別對8個數(shù)據(jù)集20次運算的平均聚類結(jié)果。

表3 各算法對8組數(shù)據(jù)集聚類的平均精度

從表3可以看出，IFWSA-KM算法在6個數(shù)據(jù)集的平均聚類精度都優(yōu)于其他3種聚類算法。

綜上所述，IFWSA-KM算法的總體聚類精度優(yōu)于KM、AKM和FWSA-KM聚類算法。

3.3 測試算法的抗噪聲能力

3.3.1 均勻分布噪聲對算法的影響

為了測試IFWSA-KM聚類算法的抗噪聲能力，在Wine數(shù)據(jù)集中使用Matlab軟件中的Rand函數(shù)，生成30個均勻噪聲樣本，并將30個噪聲樣本置于Wine數(shù)據(jù)集的尾部，形成了一個新的人工數(shù)據(jù)集Wine1，該數(shù)據(jù)集有208個樣本，13個樣本特征。用4種聚類算法分別對Wine1數(shù)據(jù)集進行聚類，最終的聚類結(jié)果如表4和表5所示。

表4 各算法對Wine1數(shù)據(jù)集聚類的最優(yōu)精度

表5 各算法對Wine1數(shù)據(jù)集聚類的平均精度

由表4和5可以看出，在Wine數(shù)據(jù)集加入了均勻噪聲，4種聚類算法的聚類精度都有所下降，但是IFWSA-KM聚類算法與KM、AKM、FWSA-KM聚類算法相比，在最優(yōu)精度方面優(yōu)于KM和AKM算法，與FWSA-KM算法精度相當(dāng)，在平均精度方面優(yōu)于其他3個算法。因此，IFWSA-KM聚類算法的抗均勻噪聲性能較好。

3.3.2 離群點噪聲對算法的影響

為了進一步測試IFWSA-KM聚類算法對噪聲的魯棒性，在Wine數(shù)據(jù)集上增加一個離群點噪聲(用Matlab中的函數(shù)1000*ones(1,13))，生成一個新的人工數(shù)據(jù)集，記為Wine2，該數(shù)據(jù)集有179個樣本，13個樣本特征。用4種算法對wine2數(shù)據(jù)集進行聚類。聚類的結(jié)果如表6和7所示。

表6 各算法對Wine2數(shù)據(jù)集聚類的最優(yōu)精度

表7 各算法對Wine2數(shù)據(jù)集聚類的平均精度

由表6和7可以看出，在Wine數(shù)據(jù)集加入離群點噪聲后，IFWSA-KM算法的最優(yōu)精度和平均精度仍然優(yōu)于KM、AKM、FWSA-KM算法。因此，IFWSA-KM聚類算法的抗離群點噪聲性能較好。綜上所述，IFWSA-KM聚類算法明顯具有抗噪聲性強，魯棒性好的優(yōu)點。

3.4 測試算法的特征選擇能力

Iris和Dermatology數(shù)據(jù)集都是真實的數(shù)據(jù)集，經(jīng)常被用來作為聚類算法的測試數(shù)據(jù)集，現(xiàn)用這兩個數(shù)據(jù)集測試IFWSA-KM算法的特征選擇能力。用IFWSA-KM算法對Iris和Dermatology數(shù)據(jù)集進行聚類，得到兩個數(shù)據(jù)集的特征權(quán)重，將得到的特征權(quán)重分別進行排序；根據(jù)排序的大小，將特征權(quán)重明顯較小的舍去，用剩下特征權(quán)重所對應(yīng)的數(shù)據(jù)，組成新的數(shù)據(jù)集[10]；用4種聚類算法分別對特征選擇前后的數(shù)據(jù)集進行聚類，以測試IFWSA-KM聚類算法對數(shù)據(jù)集進行特征選擇的有效性。

表8和9分別給出Iris和Dermatology數(shù)據(jù)集分別經(jīng)過IFWSA-KM算法聚類后得到的特征權(quán)重排序。

表8 Iris數(shù)據(jù)集的特征權(quán)重排序

表9 Dermatology數(shù)據(jù)集的特征權(quán)重排序

由表8可知，Iris數(shù)據(jù)集的第1、第2兩個特征的權(quán)重明顯比其它特征權(quán)重小，故在特征選擇時將它們舍棄，得到新數(shù)據(jù)集Iris1。由表9可知，Dermatology數(shù)據(jù)集的第1、第13和第32三個特征的權(quán)重明顯比其它特征權(quán)重小，故在特征選擇時也將它們舍棄，得到新的數(shù)據(jù)集Dermatology1。

用4種聚類算法分別對Iris、Iris1、Dermatology和Dermatology1數(shù)據(jù)集進行聚類。聚類的結(jié)果如表10和11所示。

表10 各算法對Iris和Iris1數(shù)據(jù)集聚類的精度

表11 各算法對Dermatology和Dermatology1數(shù)據(jù)集聚類的精度

由表10和11可以看出，4種聚類算法對經(jīng)過特征選擇后新數(shù)據(jù)集的聚類精度，都優(yōu)于對原數(shù)據(jù)集的聚類精度，其中IFWSA-KM算法的聚類精度不但優(yōu)于KM、AKM、FWSA-KM算法的聚類精度，而且還優(yōu)于特征選擇前IFWSA-KM算法的聚類精度。從而表明IFWSA-KM算法具有良好的特征選擇能力。

4 總結(jié)

利用一種非歐氏距離代替FWSA-KM算法中的歐氏距離，提出一種改進型特征權(quán)重自調(diào)節(jié)K-均值聚類算法。新算法是原FWSA-KM算法的一種改進型算法，該聚類算法不僅具有良好的特征選擇能力，同時具有一定的對復(fù)雜結(jié)構(gòu)數(shù)據(jù)和噪聲數(shù)據(jù)的魯棒性，是一種可供選擇使用的聚類算法。聚類算法收斂與否對于聚類算法是至關(guān)重要的，如何證明IFWSA-KM的收斂性將是下一步的工作。

[1] 高新波.模糊聚類分析及其應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014:1-10;50-90.

[2] Wu Kuolung, Yang Miinshen. AlternativeC-means clustering algorithms[J]. Pattern recognition, 2002, 35(10): 2267-2278.

[3] DeSarbo W S, Carroll J D, Clark L A, et al. Synthesized clustering: A method for amalgamating alternative clustering bases with differential weighting of variables[J]. Psychometrika, 1984, 49(1): 57-78.

[4] Huang Zhexue, Micheal K Ng, Rong Hongqiang, et al. Automated variable weighting inK-means type clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 657-668.

[5] Jing Liping, Micheal K Ng, Huang Zhexue. An entropy weightingK-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(8): 1026-1041.

[6] Tsai C Y, Chiu C C. Developing a feature weight self-adjustment mechanism for aK-means clustering algorithm[J].Computational statistics and Data analysis, 2008, 52(10): 4658-4672.

[7] Guo Gongde, Chen Si, Chen Lifei. Soft subspace clustering with an improved feature weight self-adjustment mechanism[J]. International Journal of Machine Learning and Cybernetics, 2012, 3(1): 39-49.

[8] Zhi Xiaobin, Fan Jiulun, Zhao Feng. Robust Local Feature Weighting HardC-Means Clustering Algorithm[J]. Neurocomputing, 2014, 134: 20-29.

[9] 支曉斌, 田溪. 判別模糊C-均值聚類算法[J]. 西安郵電大學(xué)學(xué)報, 2013, 18(5): 26-30.

[10] 皋軍,王士同.具有特征排序功能的魯棒性模糊聚類方法[J].自動化學(xué)報,2009,35(2):146-153.

[責(zé)任編輯:王輝]

K-means clustering algorithm with an improved feature weight self-adjustment mechanism

ZHI Xiaobin1, XU Zhaohui2

( 1.School of Science, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

K-means with a feature weight self-adjustment mechanism (FWSA-KM) clustering algorithm is sensitive to noise. ThereforeK-means with an improved feature weight self-adjustment mechanism (IFWSA-KM) clustering algorithm is proposed in this paper. IFWSA-KM clustering algorithm can have some anti-noise performance by using a non-Euclidean distance. The effectiveness of IFWSA-KM algorithm is demonstrated by comparative experiments on synthetic and real data.

clustering algorithm, feature weighting, robust, non-Euclidean distance

10.13682/j.issn.2095-6533.2014.06.006

2014-05-14

陜西省自然科學(xué)基金資助項目(2014JM8307)

支曉斌(1976-)，男，博士，副教授，研究方向為模式識別。E-mail：xbzhi@163.com 許朝暉(1988-)，男，研究生，研究方向為現(xiàn)代信號處理與應(yīng)用。E-mail：1113110702@qq.com

TP391.4

A

2095-6533(2014)06-0026-06