支曉斌， 許朝暉

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

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

支曉斌1， 許朝暉2

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

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

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

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

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

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

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

1 FWSA-KM算法

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

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

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

(1)

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

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

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

minJFWSA-KM(U,V,W)=

(2)

滿足

(3)

(4)

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

(5)

滿足

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

若設(shè)

則式(5)可以重寫為

(6)

其中ak是聚類在第k維特征上總的類內(nèi)緊致性度量，bk是聚類在第k維特征上總的類間分離性度量。文獻(xiàn)[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)點(diǎn)是：(1) 特征權(quán)重的計(jì)算考慮了分離性度量；(2) 算法中的參數(shù)較少；(3) 不犧牲原KM聚類算法的效率。

2 IFWSA-KM算法

JIFWSA-KM(U，V,W)=

(9)

滿足

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

問題1 固定

問題2 固定

問題3 固定

針對(duì)問題1，如果

(10)

則uij=1,否則uij=0。

問題2的解

(11)

這是關(guān)于vjk的一個(gè)非線性方程，可以用不動(dòng)點(diǎn)迭代法進(jìn)行求解。

為了求解問題3，令

(12)

(13)

其中

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

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

(14)

滿足

(15)

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

(16)

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

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

(17)

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

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

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

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

步驟2 計(jì)算隸屬度矩陣U。

步驟3 計(jì)算新的聚類中心矩陣V。

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

步驟5 如果

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

3 實(shí)驗(yàn)結(jié)果及其分析

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

(18)

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

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

3.2 算法的聚類精度測(cè)試

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

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

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

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

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

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

3.3 測(cè)試算法的抗噪聲能力

3.3.1 均勻分布噪聲對(duì)算法的影響

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

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

表5 各算法對(duì)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個(gè)算法。因此，IFWSA-KM聚類算法的抗均勻噪聲性能較好。

3.3.2 離群點(diǎn)噪聲對(duì)算法的影響

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

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

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

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

3.4 測(cè)試算法的特征選擇能力

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

表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兩個(gè)特征的權(quán)重明顯比其它特征權(quán)重小，故在特征選擇時(shí)將它們舍棄，得到新數(shù)據(jù)集Iris1。由表9可知，Dermatology數(shù)據(jù)集的第1、第13和第32三個(gè)特征的權(quán)重明顯比其它特征權(quán)重小，故在特征選擇時(shí)也將它們舍棄，得到新的數(shù)據(jù)集Dermatology1。

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

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

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

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

4 總結(jié)

利用一種非歐氏距離代替FWSA-KM算法中的歐氏距離，提出一種改進(jìn)型特征權(quán)重自調(diào)節(jié)K-均值聚類算法。新算法是原FWSA-KM算法的一種改進(jìn)型算法，該聚類算法不僅具有良好的特征選擇能力，同時(shí)具有一定的對(duì)復(fù)雜結(jié)構(gòu)數(shù)據(jù)和噪聲數(shù)據(jù)的魯棒性，是一種可供選擇使用的聚類算法。聚類算法收斂與否對(duì)于聚類算法是至關(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é)報(bào), 2013, 18(5): 26-30.

[10] 皋軍,王士同.具有特征排序功能的魯棒性模糊聚類方法[J].自動(dòng)化學(xué)報(bào),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é)基金資助項(xiàng)目(2014JM8307)

支曉斌(1976-)，男，博士，副教授，研究方向?yàn)槟Ｊ阶R(shí)別。E-mail：xbzhi@163.com 許朝暉(1988-)，男，研究生，研究方向?yàn)楝F(xiàn)代信號(hào)處理與應(yīng)用。E-mail：1113110702@qq.com

TP391.4

A

2095-6533(2014)06-0026-06