基於密度峰值優化的Canopy-Kmeans並行演算法
摘要：隨著數據規模的爆炸式增長，利用K-means等聚類演算法挖掘大數據的潛在價值，已成為一個當前較為重要的研究方向。將Canopy演算法與K-means演算法結合，可解決 個中心點的選取問題。而針對Canopy-Kmeans演算法中初始中心點選取隨機、演算法受雜訊點影響等問題，提出了一種利用密度峰值改進的M-Canopy-Kmeans演算法，並採用Spark框架實現演算法的並行化。實驗結果表明，改進後的演算法避免了Canopy中心點選取的盲目性，且有效排除了樣本中的雜訊點，準確性、抗噪性都有明顯提高，且在Spark並行框架中具有良好的加速比和擴展性。
正文內容：
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集合）：給定數據集合，對於，若滿足，則稱Pc 是以cj 為中心點、以T1 為半徑的Canopy集合。
定義2（Canopy中心點）：給定數據集合，對於，若滿足，則稱Qm 為非Canopy候選中心點集合。其中，T1 、T2 為距離閾值，是預設的參數值，可以通過交叉檢驗得出。
1.2 局部密度
針對K-means對孤立點敏感的問題，提出一種假設。對於一個數據集，若類簇中的一個點由一些相對其局部密度較低的點圍繞，那麼這個點為此類簇的密度峰值點[7]。定義為：設待聚類的數據集，相應的指標集為，dij= dist(xi,xj) 為數據xi 和xj 之間的距離，當數據點為離散值時，局部密度為：
式中：j 與i 不相等且都屬於Is ，函數為：
其中dc＞0 表示截斷距離，根據所有點與點之間的歐氏距離小於dc 值佔總樣本數的k 來確定[8]，一般在2%～5%；dij 為歐式距離。
1.3 最大最小化準則
在集合 中隨機選取一個點作為種子點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）對於數據集，通過上文中局部密度的定義，在集合S 中算出每個對象的局部密度，將局部密度低的點剔除後，把剩餘的點放入集合W 中，並標註每個點的局部密度。
（2）將集合W 中局部密度最高的密度峰值點記作初始點A，在集合W 中選取距離A最遠的對象記作第二個初始點B；利用最大最小準則在集合W 中計算第三個點C，C的取值滿足DistC=Max(moin(da,db)) ，並求出剩餘M 個點，M 滿足
，且（聚類個數[12]）。
（3）計算Depth(i) ，將M 個點中的前i 個對象賦值給集合U ，得到Canopy中心點集合 ,同時令T1=min dist(i) ；
（4）輸入Canopy的中心點數據集，將集合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大大提升。基於以上優點，本文採用Spark框架進行演算法的並行化計算，流程如圖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：利用密度峰值計算局部密度集合
演算法1：利用密度峰值計算局部密度集合
input：節點數據集
output：節點局部密度集合，密度峰值點A
令集合W 為空//設置初始局部密度集合
計算集合L 中兩兩對象的距離dij ；
利用dij 求取dc ，其中k 取2%；
求出每個點的局部密度；
if
將對應的點加入到集合W 中；
end if
將值最大的點定義為密度峰值點A。
演算法2：Canopy本地中心點生成
Input：局部密度集合W ，密度峰值點A，當前節點數據集規模N
output：Canopy中心點集合
將A點賦值給p1 ；
While//設置迭代次數；
if 集合P 中對象數為1
計算數據集W 中距離p1 最遠的點B；
else
計算數據集W 中數據點與集合P 中所有數據點的距離，選最小值中最大者，結果放於集合P ；
end if
end while
演算法3：Canopy全局中心點生成
input：子節點的Canopy中心點集合
output：中心點集合UU與 T1
求取子節點匯總後集合的數據總量 N
While
求取數據集中數據之間最小距離的最大者，將其保存到集合
end while
將中對象數賦值給k ；
while j＜k
計算集合中的最大值並輸出T1 ，並令集合U 的值為集合的前I 個對象
end while
演算法4：K-Means迭代
input：中心點集合
output：K-means中心點集合
令；
判斷 是否改變
若改變，則將數據對象分配給同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篇。
4.1 結果分析
首先用傳統K-means演算法、文獻[6]中的Canopy-Kmeans演算法（下簡稱CK-means演算法）以及本文利用密度峰值思想改進後的演算法（下簡稱M-CKmeans演算法），對前4個UCI數據集進行多次計算後求平均準確率，以對比演算法的準確率，結果如圖4所示。然後，再用以上幾個演算法對搜狗數據集的數據進行運算，結果如圖5所示。
從圖4、圖5可以看出，本文提出的M-CKmeans演算法相比於CK-means演算法和傳統K-means演算法，在準確率上均有一定提高，驗證了基於密度峰值思想改進的Canopy-Kmeans演算法的有效性。
加速比是常用來衡量程序執行並行化的重要指標[14]，本文用其來衡量演算法在Spark平台下的性能。針對同一演算法，用單機運行時間除以並行運行時間，就可以得到並行演算法的加速比。本文將搜狗的開源數據集用CK-means與M-CKmeans演算法多次運行後取平均時間，計算兩種演算法的加速比，結果如圖6所示；再利用Iris數據集構造成60維度，不同大小的數據集（500 MB，1 GB，2 GB）對改進後的演算法進行加速比對比，結果如圖7所示。
從圖6可以看出，本文的M-CKmeans演算法在同一數據集下，相同節點的執行效率高於CK-means演算法。這主要是因為演算法優化了CK-means演算法的初始中心點的選取，減少了後續演算法需要迭代的次數。在保持相同的數據規模下，隨著數據節點數目的增加，雖然每個節點所需處理的數據量減小，但因為節點的增加還會導致節點間的通信開銷增大，所以加速比的增長速度放緩。從圖7可以看出，隨著數據集的增加，並行後的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.
[3] 邱榮太.基於Canopy的K-means多核演算法[J].微計算機信息,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.
[6] 毛典輝.基於MapReduce的Canopy-Kmeans改進演算法[J].計算機工程與應用,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.
[9] 程堃.基於雲平台的聚類演算法並行化研究[D].南京:南京郵電大學,2015.
[10]劉遠超,王曉龍,劉秉權.一種改進的k-means文檔聚類初值選擇演算法[J].高技術通訊,2006,16(01):11-15.
[11]Hearst M A.TextTiling:Segmenting Text into Multi-paragraph Subtopic Passages[M].MIT Press,1997.
[12]岑詠華,王曉蓉,吉雍慧.一種基於改進K-means的文檔聚類演算法的實現研究[J].現代圖書情報技術,2008,24(12):73-79.
[13]丁文超,冷冰,許傑等.大數據環境下的安全審計系統框架[J].通信技術,2016,49(07):909-914.
[14]陳愛平.基於Hadoop的聚類演算法並行化分析及應用研究[D].成都:電子科技大學,2012.
作者：李 琪，張 欣，張平康，張 航
單位：貴州大學 大數據與信息工程學院，貴州 貴陽 550025
作者簡介：李 琪，男，碩士，主要研究方向為雲計算與大數據；
張 欣，男，博士，副教授，主要研究方向為下一代無線通信及應用等；
張平康，男，碩士，主要研究方向為圖像處理；
張 航，男，碩士，主要研究方向為雲計算與大數據。
本文刊登在《通信技術》2018年第2期（轉載請註明出處，否則禁止轉載）
TAG:通信技術編輯部 |