改進型特征權重自調節K-均值聚類算法

支曉斌， 許朝暉

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

改進型特征權重自調節K-均值聚類算法

支曉斌1， 許朝暉2

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

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

聚類算法；特征權重；魯棒性；非歐氏距離

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

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

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

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

1 FWSA-KM算法

設數據集X由n個數據點構成，即

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

經典KM聚類算法的目標函數為

(1)

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

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

為了使得KM聚類算法能夠自動對數據進行特征選擇，眾多學者提出了基于特征加權的KM聚類算法[3-8],其中FWSA-KM聚類算法的目標函數為

minJFWSA-KM(U,V,W)=

(2)

滿足

(3)

(4)

為了求解特征權重矩陣，文[6]重新定義了另一個目標函數

(5)

滿足

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

若設

則式(5)可以重寫為

(6)

其中ak是聚類在第k維特征上總的類內緊致性度量，bk是聚類在第k維特征上總的類間分離性度量。文獻[6]采用一種特征權重自調節方法來求解上述的優化問題。

設FWSA-KM聚類算法中第t步迭代的特征權重為集合

(7)

其中

(8)

為第t步迭代的特征權重調節差量。

與其他已有的特征加權KM聚類算法相比，FWSA-KM算法的優點是：(1) 特征權重的計算考慮了分離性度量；(2) 算法中的參數較少；(3) 不犧牲原KM聚類算法的效率。

2 IFWSA-KM算法

JIFWSA-KM(U，V,W)=

(9)

滿足

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

問題1 固定

問題2 固定

問題3 固定

針對問題1，如果

(10)

則uij=1,否則uij=0。

問題2的解

(11)

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

為了求解問題3，令

(12)

(13)

其中

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

為了求解特征權重矩陣，定義新的目標函數

(14)

滿足

(15)

其中特征權重調節差量

(16)

對式(15)進行規范化處理，得到特征權重

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

(17)

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

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

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

初始的特征權重矩陣W滿足

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

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

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

步驟5 如果

則停止；否則，轉到步驟2。

3 實驗結果及其分析

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

3.1 實驗設置

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

表1 數據描述

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

(18)

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

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

3.2 算法的聚類精度測試

表2給出了4種聚類算法分別對8個數據集進行20次運算的最優聚類結果。

表2 各算法對8組數據集聚類的最優精度

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

表3 各算法對8組數據集聚類的平均精度

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

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

3.3 測試算法的抗噪聲能力

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

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

表4 各算法對Wine1數據集聚類的最優精度

表5 各算法對Wine1數據集聚類的平均精度

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

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

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

表6 各算法對Wine2數據集聚類的最優精度

表7 各算法對Wine2數據集聚類的平均精度

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

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

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

表8和9分別給出Iris和Dermatology數據集分別經過IFWSA-KM算法聚類后得到的特征權重排序。

表8 Iris數據集的特征權重排序

表9 Dermatology數據集的特征權重排序

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

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

表10 各算法對Iris和Iris1數據集聚類的精度

表11 各算法對Dermatology和Dermatology1數據集聚類的精度

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

4 總結

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

[1] 高新波.模糊聚類分析及其應用[M].西安:西安電子科技大學出版社,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]. 西安郵電大學學報, 2013, 18(5): 26-30.

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

[責任編輯:王輝]

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

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

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

TP391.4

A

2095-6533(2014)06-0026-06