基于密度峰值優化的Canopy-Kmeans并行算法*

李 琪，張 欣，張平康，張 航

0 引 言

聚類分析作為統計學的一個分支，已經被廣泛研究和使用了多年。它是數據挖掘中非常重要的一部分，是從數據中發現有用信息的一種有效手段。聚類基于“相似同類，相異不同”的思想，將數據對象分組為若干類或簇，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別很大[1]。通過聚類，人們可以了解數據的分布情況，也可能會發現數據內事先未知的群組。

K-means算法是聚類分析中的經典算法，自20世紀60年代提出，已成為目前應用最廣泛的聚類方法之一。K-means算法具有理論思想可靠、算法數學思想簡單且易于實現、收斂速度快等優點，但算法本身存在缺陷，需要預先確定聚類數目K的值，且隨機選取的K個初始中心點可能會使聚類結果產生局部最優解，算法效果受噪聲點影響大。針對K-means算法存在的缺點，學者們從不同角度提出了改進方法。文獻[2]提出一種優化初始中心點的算法，采用密度敏感的相似性度量來計算對象密度。文獻[3]提出運用Canopy[4]算法和K-means算法結合，解決初始中心點選擇問題，但Canopy算法初始參數的確定也需依靠人工選取，因此效果并不穩定。文獻[5]提出了用最大距離法選取初始簇中心的K。文獻[6]提出一種基于最大最小化準則的Canopy-Kmeans算法。

在學者們對傳統K-means算法進行改進的同時，互聯網不斷發展，數據規模呈現爆炸式增長，傳統的串行聚類算法已經無法滿足當前處理海量數據的需求。而基于Spark與Hadoop等的開源分布式云計算平臺的出現，為解決這一問題提供了很好的方案。Spark是一款基于內存的分布式計算框架，計算中通過將上一個任務的處理結果緩存在內存中，大大節省了反復讀寫HDFS花費的時間。

為了進一步提高K-means聚類的準確率和聚類速度，基于以上算法的優缺點，結合Spark計算框架，本文提出一種基于密度峰值的Canopy-Kmeans并行算法。利用密度峰值[7]的思想和最大最小準則，結合Canopy-Kmeans算法，降低了選取初始聚類中心時離群點對算法的干擾和陷入局部最優的概率，提高了聚類的準確性，并利用Spark框架將算法并行化，減少了聚類所花費的時間。

1 相關概念

1.1 Canopy-Kmeans算法

Canopy-Kmeans算法是一種改進的K-means算法，其算法思想分為兩個階段。第一階段利用Canopy算法對數據集合進行預處理，快速將距離較近的數據分到一個子集中，這個子集稱作Canopy。通過計算將得到多個Canopy，數據集中的所有對象均會落在Canopy的覆蓋內，且Canopy之間可以重疊。第二階段利用得到的Canopy中心點作為K-means算法的初始聚類中心點和K值，在Canopy內使用K-means算法直至算法收斂。如果兩個數據對象不屬于同一個Canopy，那么它們就不屬于同一個簇。所以，在迭代過程中，對象只需計算與其在同一個Canopy下的K-means中心點的距離。

定義1（Canopy集合）：給定數據集合S={si|i=1,2,…,n}，對于?xi∈S，若滿cj||≤T1,cj∈ S,i≠ j}，則稱Pc是以 cj為中心點、以T1為半徑的Canopy集合。

定義2（Canopy中心點）：給定數據集合S={si|i=1,2,…,n}，對于Sxi∈?，若Qm||≤ T2,T2＜T1,Qm∈ S,i≠m}， 則 稱 Qm為 非Canopy候選中心點集合。其中，T1、T2為距離閾值，是預設的參數值，可以通過交叉檢驗得出。

1.2 局部密度

針對K-means對孤立點敏感的問題，提出一種假設。對于一個數據集，若類簇中的一個點由一些相對其局部密度較低的點圍繞，那么這個點為此類簇的密度峰值點[7]。定義為：設待聚類的數據集 S={x1,x2,…,xn}，相應的指標集為 Is={1,2,…,n}，dij=dist(xi,xj)為數據點xi和xj之間的距離，當數據點為離散值時，局部密度ρi為：

式中：j與i不相等且都屬于Is，函數χ(x)為：

其中dc＞0表示截斷距離，根據所有點與點之間的歐氏距離小于dc值占總樣本數的k來確定[8]，一般在2%～5%；dij為歐式距離。

1.3 最大最小化準則

在集合S中隨機選取一個點作為種子點A，然后計算A點與集合S中所有剩余點的距離；距離最大的點選為種子點B，計算A點和B點與集合S中所有剩余點的距離，得出距離兩個種子點最近的距離da與db；選取da、db中最大值的點作為下一個種子點C，可表示為：

按照式（3）一直迭代至無法滿足條件，即可選取出全部的種子點。

2 基于密度峰值的算法改進

隨機選取的Canopy-Kmeans算法，通過初期Canopy算法對數據集的快速預聚類，解決了K-means算法的K個中心點選取問題，同時優化了算法復雜度。但是，由于距離閾值T1、T2的選取需要通過多次運行算法求出最優距離，耗費了大量時間。文獻[9]對此問題進行了優化，避免了人為選取距離閾值T1、T2及Canopy初始中心點的隨機選取，但并未解決選取的初始中心點可能為噪聲點，從而影響算法的聚類效果。本文引入密度峰值的概念，在選取Canopy中心點前先計算數據集中密度相對較大的點，剔除低密度區域的噪聲點，得到一個高密度點集合W，同時利用“最大最小化原則”使Canopy初始中心點的距離盡可能大，使算法不易陷入局部最優。

“最大最小化準則”選取的Canopy中心點呈現以下規律：當Canopy中心點個數迫近或等于集合的聚類真實值時會產生較大波動，而少于或超過聚類真實值時相對平穩[10]。同時，參考Hearst M A文本自動分段算法中的邊界思想，定義[11]為：

當值Depth(i)最大時，Canopy取得最優初始中心點個數，并令Canopy的T1=min dist(i)。因為已經計算出Canopy中心點，所以不再需要計算T2。綜上所述，算法的實現流程圖如圖1所示。

圖1 基于密度峰值優化的Canopy-Kmeans流程

具體實現步驟如下：

（1）對于數據集S={x1,x2,…,xn}，通過上文中局部密度的定義，在集合S中算出每個對象的局部密度，將局部密度低的點剔除后，把剩余的點放入集合W中，并標注每個點的局部密度。

（2）將集合W中局部密度最高的密度峰值點記作初始點A，在集合W中選取距離A最遠的對象記作第二個初始點B；利用最大最小準則在集合W中計算第三個點C，C的取值滿足DistC=Max(min(da,db))，并求出剩余M個點，M滿足 DistM=Max(min(da,db,…,dm))，且M＜（聚類個數K＜[12]）。

（3）計算Depth(i)，將M個點中的前i個對象賦值給集合U，得到Canopy中心點集合U=(u1,u2,…,ui),同時令T1=min dist(i)；

（4）輸入Canopy的中心點數據集U=(u1,u2,…,ui)，將集合S中的所有點與Canopy中心點進行距離比較；小于T1的，標注該對象屬于對應的Canopy，最后生成i個可相互重疊的Canopy；

（5）在Canopy中應用K-means算法進行迭代，其中初始中心點為i個Canopy中心點；迭代過程中，對象只需計算與其在同一個Canopy下的K-means中心點的距離，直至算法收斂。

3 基于Spark的改進算法并行化

Spark[13]是一個開源的基于內存的集群運算框架，在2009年由美國加州大學伯克利分校AMP實驗室開發。由于Hadoop的MapReduce在運算過程中會將中間結果寫入硬盤，而頻繁的讀寫硬盤會大大增加運算時間。Spark使用內存運算技術，將中間結果寫入內存，所以基于Spark的算法運算速度相比于Hadoop MapReduce大大提升?；谝陨蟽烖c，本文采用Spark框架進行算法的并行化計算，流程如圖2所示。

圖2 算法并行流程

并行化過程中會使用Map進行局部密度點集合的求取、Canopy中心點的求取和K-means聚類。然后，使用Redcue或reduceByKey實現全局聚類，再對配置好的Spark參數后初始化環境，讀取存放在HDFS上的數據集生成彈性數據集RDD并將數據向量化。對RDD使用map操作，求取兩兩對象間的距離，得出局部密度集合和密度峰值點。使用最大最小化準則，在局部密度集合中點求取M個初始值點。匯總各節點中的初值點到主節點，計算深度值Depth(i)得到T1，并將Canopy中心點集合賦值為K-means的Cluster中心點。對RDD執行map操作，在子節點中將距離小于T1的點劃入同一Canopy。在各節點上運行K-means迭代，只需計算與中心點屬于同一Canopy的點距離。綜上所述，算法主要可分為以下三部分。

算法1：利用密度峰值計算局部密度集合

input：節點數據集L=(l1,l2,…,ln)

output：節點局部密度集合 W=(w1,w2,…,wm)，密度峰值點A

令集合W為空//設置初始局部密度集合

計算集合L中兩兩對象的距離dij；

利用dij求取dc，其中k取2%；

求出每個點的局部密度ρi；

if ρi＞ 1

將對應的點加入到集合W中；

end if

將ρ值最大的點定義為密度峰值點A。

算法2：Canopy本地中心點生成

Input：局部密度集合W，密度峰值點A，當前節點數據集規模N

output：Canopy中心點集合P=( p1,p2,…,pn)

將A點賦值給p1；

if 集合P中對象數為1

計算數據集W中距離p1最遠的點B；

else

計算數據集W中數據點與集合P中所有數據點的距離，選最小值中最大者，結果放于集合P；

end if

end while

算法3：Canopy全局中心點生成

input：子節點的Canopy中心點集合P=( p1,p2,…,pn)

output：中心點集合U與T1

求取子節點匯總后集合的數據總量N

求取數據集中數據之間最小距離的最大者，將其保存到集合P'

end while

將P'中對象數賦值給k；

while j＜k

計算集合P'中的最大值并輸出T1，并令集合U的值為集合P'的前i個對象

end while

算法4：K-Means迭代

input：中心點集合U=(u1,u2,…,ui)

output：K-means中心點集合U '

令U '=U；

判斷U '是否改變

若U '改變，則將數據對象分配給同Canopy與它距離最小的K-means中心點；

將屬于同一中心點的對象匯總，計算新的初始中心點；

輸出新的聚類中心點。

4 實驗結果與分析

4.1 實驗環境與數據

本文實驗是在Hadoop2.7.2的YARN基礎上部署的Spark框架，Spark版本為2.02。實驗由5臺PC機組成，機器內存4 GB，CPU為Intel Core i5處理器，主頻2.5 GHz，硬盤大小160 GB，操作系統版本為CentOS7。

實驗一共選用五個數據集，其中4個來自UCI機器學習庫，分別為Iris、Wine、Waveform和Pima Indians Diabetes，各數據集屬性如表1所示；另一個來自搜狗實驗室的開源分類數據庫，在其中選取文化、財經和體育三個類別的文檔，各選10 000篇。

表1 UCI數據集屬性

4.2 結果分析

首先用傳統K-means算法、文獻[6]中的Canopy-Kmeans算法（下簡稱CK-means算法）以及本文利用密度峰值思想改進后的算法（下簡稱M-CKmeans算法），對前4個UCI數據集進行多次計算后求平均準確率，以對比算法的準確率，結果如圖3所示。然后，再用以上幾個算法對搜狗數據集的數據進行運算，結果如圖4所示。

圖3 UCI數據集聚類準確率

圖4 文本聚類

從圖3、圖4可以看出，本文提出的M-CKmeans算法相比于CK-means算法和傳統K-means算法，在準確率上均有一定提高，驗證了基于密度峰值思想改進的Canopy-Kmeans算法的有效性。

加速比是常用來衡量程序執行并行化的重要指標[14]，本文用其來衡量算法在Spark平臺下的性能。針對同一算法，用單機運行時間除以并行運行時間，就可以得到并行算法的加速比。本文將搜狗的開源數據集用CK-means與M-CKmeans算法多次運行后取平均時間，計算兩種算法的加速比，結果如圖5所示；再利用Iris數據集構造成60維度，不同大小的數據集（500 MB，1 GB，2 GB）對改進后的算法進行加速比對比，結果如圖6所示。

圖5 相同數據集不同算法加速比

圖6 不同數據大小M-CKmeans加速比

從圖5可以看出，本文的M-CKmeans算法在同一數據集下，相同節點的執行效率高于CK-means算法。這主要是因為算法優化了CK-means算法的初始中心點的選取，減少了后續算法需要迭代的次數。在保持相同的數據規模下，隨著數據節點數目的增加，雖然每個節點所需處理的數據量減小，但因為節點的增加還會導致節點間的通信開銷增大，所以加速比的增長速度放緩。從圖6可以看出，隨著數據集的增加，并行后的M-CKmeans算法具有良好的加速比。綜上結果證明，本文算法在Spark環境下具有較好的加速比，且并行化性能更高。

5 結 語

文中主要利用密度峰值的思想，先求出各點的局部密度，然后結合最大最小準則，優化Canopy初始中心點的選擇，同時利用Spark框架改進算法并行化。實驗結果表明：改進后算法在抗噪性、準確度上有明顯提高，且基于Spark的改進算法能夠很好地應付大量數據，具有可觀的加速比。

[1] Jain A K,Murty.Data Clustering:A Review[J].Acm Computing Surveys,1999,31(03):264-323.

[2] 汪中,劉貴全,陳恩紅.一種優化初始中心點的K-means算法[J].模式識別與人工智能,2009,22(02):299-304.WANG Zhong,LIU Gui-quan,CHEN En-hong.A K-means Algorithm Based on Optimized Initial Center Points[J].Pattern Recognition and Artificial Intelligence,2009,22(02):299-304.

[3] 邱榮太.基于Canopy的K-means多核算法[J].微計算機信息,2012(09):486-487.QIU Rong-tai.Canopy for K-Means on Multi-core[J].Microcomputer Information,2012(09):486-487.

[4] Rong C.Using Mahout for Clustering Wikipedia's Latest Articles:A Comparison between K-means and Fuzzy C-means in the Cloud[C].IEEE Third International Conference on Cloud Computing Technology and Science,IEEE Computer Society,2011:565-569.

[5] 翟東海,魚江,高飛等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應用研究,2014,31(03):713-715.ZHAI Dong-hai,YU Jiang,GAO Fei,et al.K-means Text Clustering Algorithm Based on Initial Cluster Centers Selection According to Maximum Distance[J].Application Research of Computers,2014,31(03):713-715.

[6] 毛典輝.基于MapReduce的Canopy-Kmeans改進算法[J].計算機工程與應用,2012,48(27):22-26.MAO Dian-hui.Improved Canopy-Kmeans Algorithm Based on MapReduce[J].Computer Engineering &Applications,2012,48(27):22-26.

[7] Rodriguez A,Laio A.Machine learning Clustering by Fast Search and Find of Density Peaks[J].Science,2014,344(6191):1492.

[8] 張嘉琪,張紅云.拐點估計的改進譜聚類算法[J].小型微型計算機系統,2017,38(05):1049-1053.ZHANG Jia-qi,ZHANG Hong-yun.Improved Spectral Clustering Based on Inflexion Point Estimate[J].Journal of Chinese Computer Systems,2017,38(05):1049-1053.

[9] 程堃.基于云平臺的聚類算法并行化研究[D].南京:南京郵電大學,2015.KUN Cheng.Parallelized Clustering Algorithm Based on the Cloud Platform[D].Nanjing:Nanjing University of Posts and Telecommunications,2015.

[10] 劉遠超,王曉龍,劉秉權.一種改進的k-means文檔聚類初值選擇算法[J].高技術通訊,2006,16(01):11-15.LIU Yuan-chao,WANG Xiao-long,LIU Bing-quan.An Adapted Algorithm of Choosing Initial Values for k-means Document Clustering[J].Chinese High Technology Letters,2006,16(01):11-15.

[11] Hearst M A.TextTiling:Segmenting Text into Multiparagraph Subtopic Passages[M].MIT Press,1997.

[12] 岑詠華,王曉蓉,吉雍慧.一種基于改進K-means的文檔聚類算法的實現研究[J].現代圖書情報技術,2008,24(12):73-79.CEN Yong-Hua,WANG Xiao-rong,JI Yong-hui.Algorithm and Experiment Research of Textual Document Clustering Based on Improved K-means[J].New Technology of Library and Information Service,2008,24(12):73-79.

[13] 丁文超,冷冰,許杰等.大數據環境下的安全審計系統框架[J].通信技術,2016,49(07):909-914.DING Wen-chao,LENG Bing,XU Jie,et al.Security Audit System Framework in Big Data Environment[J].Communications Technology,2016,49(07):909-914.

[14] 陳愛平.基于Hadoop的聚類算法并行化分析及應用研究[D].成都:電子科技大學,2012.CHEN Ai-ping.Parallelized Clustering Algorithm Analysis and Application Based on Hadoop Platform[D].Chengdu:University Of Electronic Science and Technology of China,2012.