基于影響空間的初始中心點優(yōu)化K-means聚類算法

趙文沖，蔡江輝，張繼福

(太原科技大學 計算機科學與技術學院，太原 030024)

?

基于影響空間的初始中心點優(yōu)化K-means聚類算法

趙文沖，蔡江輝，張繼福

(太原科技大學 計算機科學與技術學院，太原 030024)

針對K-means聚類算法依賴初始點、聚類結果受初始點的選取影響較大的缺陷，給出了一種穩(wěn)定的基于影響空間的初始點優(yōu)化K-means聚類算法。該算法借助了影響空間數(shù)據(jù)結構和定義的加權距離吸引因子，將特殊中心點合并為K個微簇，并對微簇中的數(shù)據(jù)點加權平均得到K個初始中心點，然后執(zhí)行K-means算法；最后，理論分析和實驗結果表明，該初始點優(yōu)化K-means聚類算法能夠有效降低噪聲數(shù)據(jù)對聚類結果的影響，在聚類結果、聚類過程效率方面有較大優(yōu)勢。

K-means算法；影響空間；加權距離吸引因子；初始點優(yōu)化

聚類作為數(shù)據(jù)挖掘的重要技術之一，是在沒有任何先驗知識的前提下，將給定數(shù)據(jù)集中的數(shù)據(jù)對象劃分到一個一個簇中，使得簇內(nèi)部對象間的距離盡可能小、信息盡可能相似，而不同簇間的對象間的距離盡可能大、信息盡可能不相似的過程[1]。

目前，國內(nèi)外學者已經(jīng)提出了眾多聚類算法，大致可以分為以下幾大類[1]：劃分方法、層次方法、基于密度方法、基于網(wǎng)格方法以及基于模型方法。K-means[2]是一種簡單的、無監(jiān)督的劃分聚類算法，由于具有簡單易實現(xiàn)、通用性強、計算復雜度較低、對數(shù)據(jù)輸入順序不敏感等優(yōu)勢[3]，成為最受關注的最經(jīng)典算法之一。與此同時，K-means算法存在許多缺陷[4]，其中最主要缺陷之一是K-means作為一種迭代算法，易收斂于局部最優(yōu)解，對初始聚類中心和噪聲數(shù)據(jù)特別敏感。

針對K-means算法的初始中心點選取問題，本文給出了一種基于影響空間的初始中心點優(yōu)化K-means聚類算法。算法能夠獲得穩(wěn)定的更加符合分布的初始中心點，充分降低噪聲數(shù)據(jù)的影響，有效的提高了聚類質(zhì)量。

1 相關工作

作為一種無監(jiān)督學習方法，K-means可以為其它數(shù)據(jù)挖掘算法提供初始化、預處理等操作，因此初始中心點的選取不僅是K-means的單獨問題，而應當是依托K-means的所有算法的共同問題，初始中心點的優(yōu)化選取成為一項更加重要的任務。自K-means被提出，大量的初始中心點優(yōu)化選取方法被提出，歸納起來，大致分為隨機抽樣方法、距離優(yōu)化方法以及密度估計方法等三類[5]。

1.1 隨機抽樣方法

R-SEL算法[6]是最早的初始點選擇算法之一，也是最典型利用隨機抽樣思想的算法之一。數(shù)據(jù)集中的每個對象成為中心點的幾率等大，對于均勻分布且無噪聲的情況下能夠快速聚類。MacQueen等人[2]提出將數(shù)據(jù)集按任意順序進行輸入，挑選前K個輸入對象為初始聚類中心的思想，改進了對輸入順序的不敏感性。但噪聲數(shù)據(jù)對兩種算法的聚類結果產(chǎn)生較大影響。

Zhu等人[7]提出了一種基于隨機抽樣的通過迭代計算比較當前距離與所設定的距離閾值的大小進行中心點增刪的啟發(fā)式求取初始聚類中心點的方法。算法一定程度上很好的提高聚類精度、減少聚類過程中迭代次數(shù)，而且減少了對噪聲和輸入順序敏感性。

1.2 距離優(yōu)化方法

李金宗等[8]介紹了一種最大最小距離的初始中心點優(yōu)化算法，通過比較當前所選取的中心點與其它所有數(shù)據(jù)對象的最小距離的最大者獲得下一個中心點，算法迭代進行，直到獲得K個中心點為止。算法簡便易實現(xiàn)，但時間消耗大成為制約該算法的一大缺陷。針對高計算量，武霞等[9]提出了一種基于最大值原則的改進算法，不僅降低了計算量，而且提供了一種并行思想策略。

Sathiya G等人[10]提出了基于原點的距離優(yōu)化算法。首先計算排序各數(shù)據(jù)對象到原點的距離，并將這些距離等分成K等份，取中間點所對應的數(shù)據(jù)對象作為聚類中心點。此算法將原點作為一個參考點進行初始聚類中心點的選取，能夠準確高效地處理分布均勻的數(shù)據(jù)集，但對于某些分布不均勻數(shù)據(jù)集，效果則不明顯，甚至可能產(chǎn)生更高的時間消耗。

1.3 密度估計方法

Yang等人[11]提出一種密度估計方法選擇初始聚類中心算法。算法思想是利用鄰域不斷尋找剩余數(shù)據(jù)集中局部密度最大的數(shù)據(jù)點作為初始中心點，并將已得到的初始中心點以及初始中心點的k鄰域以及ε鄰域中的數(shù)據(jù)點從數(shù)據(jù)集中去除。算法對數(shù)據(jù)輸入順序不敏感，對分布均勻數(shù)據(jù)集聚類效果明顯，但由于先驗條件的缺失，算法在處理分布不均勻，存在多個密度層次的數(shù)據(jù)集時，效果并不明顯，很容易出現(xiàn)初始點集中在最稠密的小區(qū)域內(nèi)，造成聚類質(zhì)量的下降，迭代次數(shù)的增加等問題。

Bianchi F M等人[12]提出兩種新的利用PDF進行初始點選取的算法。算法首先得到數(shù)據(jù)對象的相異度矩陣，通過設定合適的PDF對數(shù)據(jù)對象的局部密度進行估計，最后得到局部密度最大的數(shù)據(jù)對象作為初始點。同時，在大型數(shù)據(jù)集的處理上，算法設定的兩種抽樣方法進行數(shù)據(jù)抽樣，降低了求取相異度矩陣的時間消耗。

2 初始點優(yōu)化方法

2.1 相關定義

假設給定數(shù)據(jù)集為D，|D|表示數(shù)據(jù)集D中數(shù)據(jù)對象的數(shù)目，設數(shù)據(jù)對象p，q∈D.在該優(yōu)化算法中，首先選取一個與距離無關的參數(shù)k，參照文獻[13]-[15],進行以下相關定義.

定義1k鄰域距離.p的k鄰域距離kdist(p)，定義為dist(p,q)，其中q∈D，是距離p的第k個最近數(shù)據(jù)對象。

定義2k鄰域點集.p的k鄰域點集NNk(p)，定義為D中與對象p的距離不大于kdist(p)的所有數(shù)據(jù)對象組成的集合。

定義3 反k鄰域點集.p的反k鄰域點集RNNk(p)，定義為NNk中存在對象p的所有數(shù)據(jù)對象組成的集合，即RNNk(p)={q|q∈D,p∈NNk(q)}.

通過將對象的k鄰域點集和反k鄰域點集進行結合，我們就可以得到對象的影響空間。

定義4 影響空間.對象p的影響空間ISk(p)，定義為對象p的NNk(p)和RNNk(p)的交集，即:

ISk(p)={s|s∈NNk(p)∩RNNk(p),s∈D}

由定義1-4，可以得到對于任意數(shù)據(jù)對象r∈D，有|NNk(r)|≥k，|RNNk(r)| ≥0，|ISk(r)| ≥0.考察全局噪聲數(shù)據(jù)和局部噪聲數(shù)據(jù)，由于噪聲數(shù)據(jù)基本處于分布比較稀疏，密度較小的區(qū)域，因此噪聲數(shù)據(jù)一般孤立于非噪聲數(shù)據(jù)的RNNk和ISk外，噪聲數(shù)據(jù)的ISk擁有較小的數(shù)據(jù)對象個數(shù)。因此，利用影響空間對數(shù)據(jù)集進行區(qū)域劃分，可以很好地降低噪聲數(shù)據(jù)對全局、局部聚類的影響，提高聚類質(zhì)量。

數(shù)據(jù)集D中的各個數(shù)據(jù)對象依照影響空間大小進行重新降序排列之后，得到了新的數(shù)列為V.順序訪問數(shù)據(jù)點的影響空間中的數(shù)據(jù)i，對訪問過的數(shù)據(jù)i進行標記Visited(i)=1，在對V順序訪問過程中針對訪問過的數(shù)據(jù)不再進行訪問其影響空間。這樣得到數(shù)據(jù)集D的特殊中心點集。

定義5 特殊中心點.所謂的特殊中心點集SC，定義為對V進行訪問過程中，未被標記的數(shù)據(jù)點組成的集合，即：

SC={o|o∈V∩Visited(o)!=1}

定義6k共享鄰域點集.數(shù)據(jù)對象p,q∈D，則p,q的k共享鄰域點集SNNk(p,q)為對象p的NNk(p)與對象q的NNk(q)中共享的點集。即

SNNk(p,q)={r|r∈NNk(p) ∩NNk(q)}

定義7 加權距離吸引因子.數(shù)據(jù)對象p,q∈D，則該兩數(shù)據(jù)點的加權距離吸引因子為

da(p,q)=

其中d=dist(p,q)；|SNNk(p,q)|為p，q的共享鄰域內(nèi)元素的數(shù)量；同樣的，|ISk(p)|與|ISk(q)|分別是p和q的影響空間中的數(shù)量。

這里采用加權距離吸引因子作為數(shù)據(jù)對象間合并的因子，不僅考慮數(shù)據(jù)對象間的度量距離，同時具有如下優(yōu)勢：

(1)充分考慮了兩個數(shù)據(jù)對象在數(shù)據(jù)集中的分布。

加權距離吸引因子兩對象的共享鄰域內(nèi)元素的數(shù)量、每個對象的影響空間中元素的數(shù)量以及兩對象間的距離平方三個方面構成。如圖1所示，此為一個二維的數(shù)據(jù)集，假設圖中的各標注的點的坐標為p=(2,4.9),q=(4.5,3.6),o=(3.0,4.0),r=(2.2,4.7),并設定k=4.對各標注點求NNk區(qū)域，即在圖中各個圓所表示區(qū)域。通過計算得到，dist(p,o)=1.3454，dist(q,o)=1.5524，NNk(p)=6，NNk(q)=4，NNk(o)=4，研究發(fā)現(xiàn)，雖然p和o的NNk區(qū)域內(nèi)都有點r，但r的NNk區(qū)域內(nèi)只有p沒有o，也就是r∈RNNk(p)但r?RNNk(o).通過定義4及定義6，得出SNNk(p,o)=0，同樣，得到SNNk(q,o)=2.則最終得到da(p,o)=0，da(q,o)>0，所以對象o與對象q更容易在同一個簇中。而事實也正好是這樣，p和r所在的簇比較稠密，密度較大，而q和o所在的簇中元素分布比較稀疏，密度較小。

(2)合理考慮了局部噪聲點對全局聚類的影響。

圖1中，對象o相對于p和r所在的較稠密區(qū)域A來說明顯地是一個局部噪聲點。通過定義3、定義4以及定義7，很容易得到A對o的加權距離吸引因子為0，從而聚類過程中排除o對A的影響。

(3)由于ISk已經(jīng)是按降序進行排序的，則該加權距離吸引因子符合影響空間較小的對象向影響空間較大的對象進行聚合。

圖1 簡單二維數(shù)據(jù)集分布

定義8 特殊中心點簇與初始中心點簇.根據(jù)加權距離吸引因子對特殊中心點進行合并，得到M個特殊中心點簇；再次對特殊中心點簇進行層次合并，最終得到K個初始中心點簇OCi，i=1,2,…,K.

定義9 加權初始中心點.對特殊中心點簇中的元素進行對應影響空間個數(shù)加權后，再平均簇內(nèi)元素數(shù)據(jù)，得到加權初始中心點OWCi，i=1,2,…,K.計算公式為

2.2 算法描述

算法具體描述如下：

輸入：數(shù)據(jù)集D，用戶設定參數(shù)k，聚簇的個數(shù)K.

輸出: K個初始中心點以及最終的K個聚簇.

/*Step1:求數(shù)據(jù)集D中的各數(shù)據(jù)對象的NNk*/

1)foreachobjectxi∈D(1≤i≤|D|)do

2)retrievingtheNNk(xi);

3)end

/*Step2:相應地，求D中各數(shù)據(jù)對象的RNNk，ISk*/

4)foreachobjectxi∈D

5)retrievingtheRNNk(xi)andISk(xi);

6)descendingallthe|ISk(xi)→V;

7)end

/*Step3:對V中數(shù)據(jù)進行訪問，得到特殊中心點集PC*/

8)forallobjectsvi∈V

9)Visited(vi) = 0;

10)end

11)foreachobjectxvi∈D

12)ifVisited( xvi)==0

13)putingxviintoPC;

14)forallobjectspi∈ISk( xvi)

15)Visited(pi) =1;

16)end

17)end

18)end

/*Step4:求特殊中心點集PC中的數(shù)據(jù)間的加權距離吸引因子，并進行層次結合，得到K個初始中心簇*/

19)foreachobjectqi∈PC(1≤i≤|PC|)

//Step4.1:計算加權距離吸引因子，并排序

20)foreachobjectqj∈PC，(1≤j≤|PC|,i≠j)

21)returnningthe|SNNk(qi,qj)|;

22)calculatingtheda(qi, qj);

23)sorttingtheda(qi, qj);

24)end

//Step4.2:層次合并特殊中心點直到達到最終K個初始中心簇

25)while|PC|>K

26)accordingtotheda(qi, qj),hierarchicalclusteringuntil|PC|==K;

27)retrievingKclusters: C1, C2, …, CK;

28)end

29)end

/*Step5:對初始中心點簇中元素對象進行加權平均后得到最終的加權初始中心點*/

30)foreachobjectoi,j∈Ci,1≤i≤K,1≤j≤|Ci|

31)calculatingOWCiaccordingtothedefine8;

32)retrievingK OWC;

33)end

/*Step6:執(zhí)行K-means算法

34)runningtheK-meansalgorithm.

3 實 驗

本節(jié)通過實驗對算法進行性能測試。實驗平臺配置為Intelcorei5 4570CPU，2G內(nèi)存，64位操作系統(tǒng)的DellPC機，實驗環(huán)境為eclipse，算法程序采用Java編寫。實驗所使用的數(shù)據(jù)全部來自于UCI數(shù)據(jù)集，表1為具體使用的實驗測試數(shù)據(jù)集。同時，對原始K-means算法、文獻[7]、文獻[10]、文獻[11]中算法以及文獻[12]中的DBCRIMES2算法進行了分析比較。

表1 實驗測試數(shù)據(jù)集的特征

3.1 聚類效果精度

文獻[16]提供了一種評價聚類結果好壞的標準。度量標準為

其中，n為數(shù)據(jù)集數(shù)據(jù)對象個數(shù)，k為聚類的簇數(shù)，αi為聚類的簇i與已知數(shù)據(jù)集類別對應后，簇i中被正確歸為相應類別的樣本個數(shù)。Micro-precision的值越大，表示算法在該數(shù)據(jù)集上聚類效果越好。

表2為六種算法在各數(shù)據(jù)集上的聚類精度對比，其中，由于K-means算法、文獻11算法以及DBCRIMES2算法都要隨機抽取樣本數(shù)據(jù)，實驗中我們各取10次實驗結果的平均值作為算法的聚類精度。

從表2可以看到，本文提出的優(yōu)化初始中心點K-means算法充分考慮了噪聲數(shù)據(jù)在數(shù)據(jù)集中的分布，選取的初始中心點均分布在局部分布密度最大的位置，聚類精度要明顯優(yōu)于其他5種算法。

3.2 聚類迭代次數(shù)比較

一般說來，初始中心點選取的越接近理想的中心點，聚類收斂速度越快，聚類過程效率越高。圖2-圖7分別為6個UCI數(shù)據(jù)集在上述6種算法下的聚類迭代次數(shù)比較。

表2 各算法在不同數(shù)據(jù)集上的聚類精度對比

圖2 各算法在Iris上的迭代次數(shù)對比

圖3 各算法在Seeds上的迭代次數(shù)對比

圖4 各算法在Wine上的迭代次數(shù)對比

圖5 各算法在Abalone上的迭代次數(shù)對比

圖7 各算法在Ionosphere上的迭代次數(shù)對比

比較可以得到，本文算法的聚類迭代次數(shù)比其它大多數(shù)算法迭代次數(shù)要小，表明本文算法選取的初始中心點更加接近于最終理想的中心點，在聚類過程效率方面具有較大優(yōu)勢。

4 結 論

針對K-means聚類算法對初始中心點依賴度高以及對噪聲數(shù)據(jù)比較敏感的問題，提出一種穩(wěn)定的初始點優(yōu)化K-means聚類算法。采用影響空間以及共享鄰域數(shù)據(jù)結構，尋找更加適合分布的初始中心點。理論分析和實驗結果表明了，本文提出的初始點優(yōu)化算法能夠很好的削弱噪聲數(shù)據(jù)對全局及局部的影響，獲得更加符合分布的穩(wěn)定的初始中心點，在聚類精度和聚類迭代效率方面都有相應的提高。

[1] 孫吉貴,劉杰,趙連宇. 聚類算法研究[J].軟件學報,2008, 19(1): 48-61.

[2] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]// Proceedings of the fifth Berkeley symposium on mathematical statistics and probability,1967, 1(14): 281-297.

[3] CELEBI M E, KINGRAVI H A, VELA P A. A comparative study of efficient initialization methods for theK-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1): 200-210.

[4] PENA J M, LOZANO J A, LARRANAGA P. An empirical comparison of four initialization methods for the-Means algorithm[J]. Pattern recognition letters, 1999, 20(10): 1027-1040.

[5] HE J, LAN M, TAN C L, et al. Initialization of cluster refinement algorithms: A review and comparative study[C]// Neural Networks, 2004. Proceedings. 2004 IEEE International Joint Conference on. IEEE, 2004, 1.

[6] FORGY E W. Cluster analysis of multivariate data: efficiency versus interpretability of classifications[J]. Biometrics, 1965, 21: 768-769.

[7] ZHU M, WANG W, HUANG J. Improved initial cluster center selection inK-means clustering[J]. Engineering Computations, 2014, 31(8): 1661-1667.

[8] 李金宗. 模式識別導論[M]. 北京:高等教育出版社, 1994.

[9] 武霞, 董增壽, 孟曉燕. 基于大數(shù)據(jù)平臺 hadoop 的聚類算法 K 均值優(yōu)化研究[J]. 太原科技大學學報, 2015, 36(2): 92-96.

[10] SATHIYA G, KAVITHA P. An Efficient EnhancedK-means Approach with Improved Initial Cluster Centers[J]. Middle-East Journal of Scientific Research, 2014, 20(1): 100-107.

[11] YANG S Z, LUO S W. A novel algorithm for initializing clustering centers[C]// Machine Learning and Cybernetics, 2005. Proceedings of 2005 International Conference on. IEEE, 2005(9): 5579-5583.

[12] BIANCHI F M, LIVI L, RIZZI A. Two density-basedK-means initialization algorithms for non-metric data clustering[J]. Pattern Analysis and Applications, 2014: 1-19.

[13] BREUNING M M, KRIEGEL H P, Ng R T, et al. LOF: identifying density-based local outliers[C]. ACM Sigmod Record. ACM, 2000, 29(2): 93-104.

[14] JIN W, TUNG A K H, HAN J, et al. Ranking outliers using symmetric neighborhood relationship[J]. Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 2006: 577-593.

[15] JARVIS R A, PATRICK E A. Clustering using a similarity measure based on shared near neighbors[J]. Computers, IEEE Transactions on, 1973, 100(11): 1025-1034.

[16] MODHA D S, SPANGLER W S. Feature weighting inK-means clustering[J]. Machine learning, 2003, 52(3): 217-237.

An OptimizationK-means Clustering Algorithm of Initial Center Objects Based on Influence Space

ZHAO Wen-chong, CAI Jiang-hui, ZHANG Ji-fu

(School ofComputer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China)

In view of the shortcomings thatK-means clustering algorithm depends on the initial data objects and the clustering results are greatly influenced by the selection of initial data objects, this paper proposes a stable optimization algorithm about initial data objects chosen inK-means algorithm based on influence space. Firstly, algorithm obtains several special center points to K tiny clusters with the help of influence space data structure and a weighed distance attraction factor is defined. And K initial data objects are obtained by weighed and meaning in K tiny clusters. Then, theK-means algorithm is run on given data set. Theoretical analysis and experimental results show that the new algorithm can lower the effect of noise data objects for the clustering results effectively; meanwhile, there is a great advantage on the clustering results and the processing iteration times.

：K-means clustering algorithm, influence space, weighed distance attraction factor, initial data objects optimization

2016-01-05

國家自然科學基金(41372349)，山西省社會發(fā)展攻關項目(20140313023-2)；山西省高校優(yōu)秀青年學術帶頭人項目。

趙文沖(1989-)，男，碩士研究生，研究方向為數(shù)據(jù)挖掘與知識工程；通信作者：蔡江輝教授，E-mail:supercooling@qq.com

1673-2057(2016)05-0347-07

TP391

A

10.3969/j.issn.1673-2057.2016.04.003