改進CK-means+算法及并行實現

邵金鑫，行艷妮，南方哲，趙 鑫，馬廷淮，錢育蓉+

(1.新疆大學 軟件學院 新疆維吾爾自治區信號檢測與處理重點實驗室，新疆 烏魯木齊 830046； 2.南京信息工程大學 國際教育學院，江蘇 南京 210044)

0 引 言

K-means算法因其原理簡單、易實現、運行高效等優點成為大規模數據的常用算法[1-3]，但人為設定K-means算法初始聚類中心點和聚類數目，使聚類結果不穩定，以至精度低、收斂慢。針對K-means算法的改進工作大都關注于優化聚類簇數和中心點以及高效處理大規模數據這兩個方面[4-12]。文獻[13-17]使用預劃分數據集和全局優化思想來優化初始值選取過程。文獻[18]使用Kd樹劃分數據集，提供選取初始中心點的依據。但是Kd樹較慢的建樹速度隨著數據量增大會進入瓶頸期。文獻[19]將最大最小距離算法與禁忌搜索算法相結合，優化初始中心點。文獻[20-26]將預聚類結果作為K-means算法的輸入，但算法復雜度增加。以上方法分別存在處理大規模數據困難、復雜度高、通用性能差等問題。因此，本文提出改進的CK-means+算法，通過優化Canopy算法和均值計算法，解決K值不確定性和選取初始中心點的問題，并結合Spark平臺在UCI數據集上，從3個方面對比其它算法的性能。

本文的主要貢獻是：

(1)解決了Canopy算法中閾值T1和T2難以確定的問題，自適應得到閾值T2；

(2)采用改進Canopy算法得到聚類數目，均值計算法得到初始中心點，對K-means算法進行改進；

(3)設計并實現Spark下K-means算法的并行策略，使其更有效地適用于大規模數據的聚類處理。

1 相關技術

1.1 Spark平臺

Spark[27-29]是由UC Berkeley的AMPLab提出的一種由Scala語言實現的大數據計算框架，既兼容Hadoop中MapReduce的可擴展性和容錯性等優點，同時引入內存計算的概念。為加快Spark處理數據的運算速度，將數據存儲在HDFS中，Spark和HDFS結合使用，并采用Spark的YARN模式管理資源調度。Spark的YARN模式如圖1所示，它通過ResourceManager來申請資源，該資源管理器啟動NodeManager來管理從屬節點。在YARN模式下，Spark基于HDFS來存儲操作數據，這不僅具有高效、快速處理大數據的優勢，而且還充分發揮了HDFS數據存儲的優勢。

圖1 Spark的YARN模式資源管理調度

1.2 K-means算法概述

K-means算法是數據挖掘領域的重要算法之一，它的特點是不受監督，原理是根據數據集特征的相似度對數據進行分類。K-means聚類算法的定義為：假設需要聚類的數據集X中有n個數據點，將其分為k類，用向量X=x1,x2,x3…xn表示待分類數據集，用向量C1,C2,C3…Ck表示k個數據集合，k∈{1,2,3,…K}， 以數據集X為例，有n個點，m個屬性，以矩陣形式表示：

(1)劃分待分類數據集

(1)

Xn=[x1n,x2n,x3n,…,xmn]T(n∈{1,2,3,…,N},m∈{1,2,3,…,M})

(2)

(2)選取初始中心點

(3)

Ck=[c1k,c2k,c3k,…,cmk]T(k∈{1,2,3,…,K},m∈{1,2,3,…,M})

(4)

(3)計算歐氏距離和選擇最小距離

(5)

Xi={Min(EUD(Xn,Ck))} (i∈{1,2,3,…,N},n∈{1,2,3,…,N})

(6)

(4)成本損失函數最小化

(7)

1.3 Canopy算法原理

Canopy算法是由Mccallum等提出的無監督預聚類算法，用于高維度的大數據預聚類分析。它可以僅僅進行距離計算，就把初始數據集進行劃分為多個可重疊的子集，從而可以消除數據集中的噪聲點或離群值，因此，經過Canopy算法預處理后，K-means算法迭代次數降低，聚類耗時減少。原理是將Canopy算法對數據集做初步聚類結果的中心點作為K-means算法的初始質心。使用Canopy算法對數據集分類要預先設定兩個距離閾值T1、T2，選擇初始中心點，再計算數據點與初始中心點之間的距離，根據距離閾值將樣本劃分為相應的聚類。Canopy算法具體如算法1和圖2所示。

Algorithm1： Canopy clustering algorithm

Input： Data setsX

Output： The cluster numberKand initial cluster centers of datasets

(1) initialize the ArrayList and setT1,T2

(2) select initial data pointsxrandomly

(3) FOR(each dataxi∈X){

(4) IF(data setsX!=null)

(5) {computed;

(6) IF(d

(7) Canopy setsci←dataxi;

(8) };

(9) ELSE IF(d

(10) remove dataxifromX;

(11) }

(12) }

(13) ELSE {

(14) break;

(15) }

(16) }

(17) END FOR

(18) PRINTF(valueK, Initial Center);

圖2 Canopy算法流程

2 CK-means+算法原理

CK-means+算法的改進思路為：采用精度不高的Canopy聚類和均值計算法對源數據集進行處理，將輸出的結果提供給K-means作為初始值選定的參考，從而消除初始中心點和聚類數目K選擇的不確定性。

因此在本節中將首先闡述優化Canopy算法的思想，接著介紹使用Canopy和均值計算法優化 K-means算法的初始階段。

2.1 Canopy算法的優化

Canopy算法的距離閾值T1和T2具有很大的隨機性，一般都根據經驗給定，這對最終結果的準確性和效率有很大影響。如果將閾值設置得太大，則可能會將不同類數據分到同一個Canopy中，反之閾值過小，則有可能會將同一類數據分到好幾個Canopy中。因此本文提出一種改進Canopy算法。考慮到Canopy算法閾值的不確定性，以及閾值T2對Canopy算法最終輸出K值的影響，本文算法主要考慮閾值T2的設定，針對源數據集，計算所有點之間的距離之和，自適應得出閾值T2。

改進Canopy算法步驟為：

步驟1 創建一個空的Canopy集合ArrayList，將數據集X轉化為 類型；

步驟2 計算數據集中數據點間的歐式距離之和，對所得到的距離進行數學運算，得到閾值T2，作為Canopy算法的輸入；

步驟3 依次讀取數據集X中的數據點，將第一個數據點作為第一個Canopy的中心點，計算數據集X中數據點與中心點之間的歐式距離，并度量相似度；

步驟4 若計算出的距離小于閾值T2，將該數據點從數據集中X剔除，劃分到上述中心點的Canopy集合中；反之，依次讀取下一數據點；

步驟5 迭代進行步驟3、步驟4，直到數據集X為空，輸出聚類數目K。

2.2 CK-means+的改進

在K-means算法中，合理選擇初始中心點和聚類數目K可以避免算法陷入局部最優并且能夠有效減少算法迭代次數，本文采用Canopy算法和均值計算法解決該問題。

首先執行改進Canopy輸出聚類數目K；再者對源數據集進行平均值計算，依據其均值對數據集排序，同時考慮Canopy算法輸出的聚類數目K，將源數據集劃分為K個子集，計算每個子集的平均值，取最接近平均值的數據點作為K-means算法的初始中心點輸出；最后將K和初始中心點作為K-means算法的輸入執行K-means算法，CK-means+算法流程如圖3所示。

CK-means+算法如算法2所示，執行步驟如下：

步驟1 從第(1)行到第(20)行，完成Canopy算法閾值T2以及聚類數目K的確定，通過對Canopy算法進行優化，讀取數據集X進行預聚類過程得到聚類數目K，作為K-means算法的一個輸入；

步驟2 執行第(22)至(32)行的任務，計算數據并進行排序，并獲得初始中心點作為K-means算法的另一個輸入；

步驟3 完成第(33)行至第(48)行CK-means+算法的計算，輸入初始中心點和聚類數K，根據歐幾里得距離測量相似度，依次計算數據點與中心點的距離，將數據點分到最小距離的聚類中，計算群集中每個子集之間的平均距離，并計算新的群集中心點；

步驟4 將更新后聚類中心的SSE值與初始中心點進行對比，如果收斂，則結束，將聚類結果輸出；否則迭代執行步驟3。

圖3 CK-means+算法流程

Algorithm2： Improved K-means algorithm

Input： Data setsX

Output： Clustering results of data sets

(1) initialize the ArrayList

(2) compute the valueT2

(3) FOR(each dataxi，xj∈X){

(4)sum←computedij(data pointxitoxj)

(5) }

(6)T2←sqrt(sum/2)

(7) //

(8) Canopy input(Data setsX,T2)

(9) select initial data pointsxrandomly

(10) FOR(each dataxi∈X){

(11) IF(X!= null){

(12) computed;

(13) IF(d

(14) Canopy setsci←dataxi

(15) removexifromX

(16) }

(17) }

(18) }

(19) END FOR

(20) PRINTF(valueK)

(21) //

(22) compute the average value of each data point

(23) FOR(each dataxi∈X){

(24) computedi(avg)

(25)di(avg)=(w1*x1+w2*x2+…wm*xm)/m

(26) }

(27) sortXbased ondi(avg)

(28) Divide the data intoKsubsets

(29) Calculate the mean value of each subset

(30) Take the nearest possible data point of the mean as the initial center point for each data subsets

(31) print(initial Centers)

(32) //

(33) K-means input(ValueK, initial Centers)

(34) FOR(each dataxi∈X){

(35) IF(data setsX!=null){

(36) For(each dataxi∈X){

(37) calculate the Euclidean distancedik(dataxito initial centersk)

(38) IF(MinDis(k)==dik){

(39) centerk←xi

(40) }

(41) }

(42) }

(43) }

(44) END FOR

(45) compute New Centerci=

(46) Mean(sample(xi&& (xi∈ci)))

(47) }

(48) PRINTF(Clusterci);

2.3 CK-means+的算法復雜度

在K-means算法中，算法時間復雜度可以表示為O(K*N*T)， 其中K是聚類數，N是聚類數據集的數據量，T是迭代次數。本文提出的CK-means+算法的時間復雜度取決于以下因素：聚類數K、數據集的數據量N、迭代次數T以及并行數p，并且Spark并行算法將數據集分割為p個數據塊，每個數據塊的數據量大小為N/p，每個并行數據塊單元的任務是將所有數據點分配到相應類，并計算出新的中心，時間復雜度可以表示為O(K*N/p*T)， 因此 CK-means+算法的時間復雜度主要取決于數據集的數量，并且因為CK-means+算法的輸入參數最佳，算法迭代次數比K-means算法迭代次數要少。因此CK-means+算法具有良好的時間性能。

3 實驗實現

3.1 CK-means+算法在Spark下的并行實現

結合Spark并行編程模式，設計Spark框架下CK-means+算法的并行實現。CK-means+算法實現如圖4所示，主要分為3個階段：分割數據集、聚類并行化和聚類結果合并[30,31]。

圖4 基于Spark的CK-means+算法

在算法運行之前，上傳數據集到HDFS，HDFS把數據集分割為數據子集，Spark集群則會根據RDD的血統生成DAG圖，通過DAGScheduler調度器，根據加載的數據子集，在Executor里創建任務，再將計算資源分配給各個節點，具體步驟如下，并行CK-means+算法如算法3所示：

步驟1 采取HDFS的數據分區方法將數據集X分成p部分，將X/p的數據塊分配給每個節點；主節點將Ca-nopy算法預聚類輸出的初始中心點和聚類數目都傳輸給各個節點。

步驟2 在每個工作節點中，Canopy算法對分割后的數據集進行預處理，并輸出初始中心點和簇數作為CK-means+算法的輸入。K-means算法迭代計算各個數據子集與初始中心點的歐氏距離，計算每個聚類點到中心點的距離的和SSE，并標記每個點的類別。

步驟3 將聚類結果與并行結果進行集成。并行化后獲得的聚類中心點需要聚合。聚合有兩種類型：最小化ASSE(平均SSE)和分層聚合。為了確保聚類結果的準確性，本文使用最小化ASSE方法來聚合上一步中計算出的結果。也就是說，SSE和群集中心將進行迭代，直到SSE收斂為止。

在Spark上算法實現如下：

Algorithm3： Parallel CK-means+algorithm in Spark

Input： DatasetsX， Filepath， partition

Output： Clustering results of data sets

(1) val sc←new SparkConf(conf)

(2) val input←sc.textFile(Filepath，partition)

(3) val dataArray←data.map{ // Processing the data set

(4) val label←line.split(",").take(1)

(5) val pair←line.split(",").drop(1).map {_.toDouble}

(6) (lable,pair)

(7) }

(8) Canopy(DatasetsX)

(9) PRINT(valueK,initialCenters)

(10)K-means(DatasetsX， valueK,initialCenters)

(11) PRINT(Clusterci)

3.2 環境配置

實驗環境采用1個主節點和4個從節點的模式構建兩個計算集群：Hadoop集群和Spark集群。表1顯示每個節點的角色。配置最高的計算機是Master和NameNode節點，普通節點為Worker和Datanode節點，各個節點配置信息見表2。

表1 集群節點配置角色

表2 實驗環境配置

3.3 實驗數據集

本文所用實驗數據是UCI機器學習標準數據庫，選擇下列3個數據集進行實驗：soybean-small、iris、wine見表3，每個數據集都有不同的樣本數量，同時每個樣本有不同數量的屬性，進而去測試改進算法的有效性。

表3 UCI數據

CK-means+算法的聚類效果由以下幾個參數衡量：完成聚類所需的時間、誤差平方和(the sum of squared errors of the clustering results，SSE)、聚類結果準確性，以及衡量聚類結果有效性的幾個參數：Rand指數和調整Rand指數(ARI)。

4 實驗分析

4.1 性能對比

本文采用4種不同的聚類算法K-means算法、CK-means算法、K-means++算法和CK-means+算法)處理UCI數據集并比較聚類效果。以下數值為算法進行多次實驗后所取得的平均值，根據表4的數據分析和比較，可以得到以下結論：

(1)K-means算法和K-means++算法執行花費時間較長，是因為傳統方法是隨機選擇初始中心點，導致算法達到收斂狀態也就是穩定時迭代次數更多，因此算法聚類過程花費的時間更長。K-means ++算法的時間復雜度高，因此其執行時間也更長。使用Canopy算法預處理的K-means算法聚類時間明顯優于K-means算法，是由于該算法預先通過Canopy算法對數據集進行處理，再完成數據集的聚類，算法到達穩定狀態時的迭代次數會減少，因此它比K-means算法表現更優；

(2)分析聚類算法的誤差平方和，可以看出CK-means+算法聚類效果最佳。K-means算法隨機選擇初始中心點，具有最大的SSE，并且聚類效率較差；

(3)從聚類結果的準確性來看，CK-means+算法的準確性比K-means算法高23.8%，比CK-means高8.87%，比K-means++算法高4.53%。因此可以看出CK-means+算法的性能優于其它3種算法；

(4)圖5和圖6顯示4種算法聚類結果的參數(Rand指數和調整Rand指數)比較。通過計算樣本的預測值和實際值的相似度來獲得Rand指數。調整后的Rand指數類似于Rand指數，值越接近于1，聚類結果越好。從圖中可以看出，CK-means+算法的參數相較于K-means算法、CK-means算法和K-means++算法表現最優，可以看出CK-means+算法在各個方面都具有良好的聚類效果。

表4 聚類算法性能對比

圖5 Rand指數對比

圖6 調整Rand指數對比

4.2 加速比分析

在并行計算領域，加速比用于表示并行計算與相應的順序執行相比的運行速度，來衡量并行程序的性能和效果，加速比定義為式(8)

Er=Ts/Tr

(8)

其中，Ts表示算法順序執行時所需的時間，Tr表示算法在計算節點為r個的Spark集群中運行所需的時間。

當數據作為RDD加載時，它可以進入單個計算節點的內存進行聚類過程，因此，算法可以單獨在單個計算節點上運行，即使在順序執行時，算法也可以運行,但是當數據被分割并且分配給多個計算節點時，隨著計算節點的增加，各個節點間的開銷也會增加，因此引入更多數據節點來進行測試。

為了并行驗證CK-means+算法的性能，在實驗中選擇Spark MLlib中的K-means算法作為參考，以比較這兩種算法的加速比。

實驗中，Spark集群設置1～5個并行節點，2*105、3*106、5*107的數據量。HDFS作為文件系統，主節點運行Master、DataNode和Slave，從節點只運行Slave和DataNode。圖7和圖8描述兩種算法在不同數據量下節點數與加速比的關系。可見，算法的加速比都近似線性。

圖7 MLlib K-means算法在Spark下的加速比

圖8 CK-means+算法在Spark下的加速比

在數據量較小時，MLlib K-means算法加速比增長緩慢，而CK-means+算法在節點數超過3時，加速比甚至有所下降。然而當數據量達增加到5*107時，節點數從2個增加到5個時，MLlib K-means算法的加速比從1.56提高到3.76，CK-means+算法的加速比從1.8提高到4.0。加速比明顯增加。由此可見CK-means+算法在處理大規模數據時的優勢。

4.3 并行度對比

為了測試不同并行度下CK-means+算法的聚類時間，實驗在UCI數據集上測試CK-means+算法在并行度為1至5時的耗時。

如圖9所示，隨著并行度增加，聚類算法的時間消耗總體呈現出先減少后增加的趨勢。當并行度為2或3時，該算法花費時間最短，而當并行度為4或5時，該算法的時間消耗增加。計算時間減少的原因如下：隨著并行度增加，算法時間消耗由于并行處理數據而減少；通過并行迭代計算數據集與中心點間的距離，縮短算法的消耗時間。計算時間增加的原因如下：隨著并行度的增加，過多的并行度導致多個結果進行最終合并，從而增加了算法的運行時間。

圖9 CK-means+算法在不同并行度下的耗時

5 結束語

為了解決K-means算法中初始中心點和聚類數K值的不確定性的問題，本文提出基于Canopy預聚類算法和均值計算法的CK-means+算法。在UCI數據集上相較于K-means++算法、CK-means算法和K-means算法，CK-means+算法的聚類準確率分別平均提高7.03%、8.87%和24.1%，效率更高。并在Spark內存計算框架下，對CK-means+算法進行并行化編程，驗證其對處理大規模數據的適用性。該方法結合優化Canopy算法和均值計算法兩種方法，分別解決聚類數K和初始中心點的問題，提升了聚類算法的準確性和效率。

未來的工作將會集中在兩個層面，第一個層面是考慮聚類算法數據輸出的結果，準確高效整合聚類結果，提高聚類算法的準確率和效率；第二個層面是由于大數據格式的多樣化，對數據處理的準確性和實時性有更高的要求，因此下一步考慮對數據進行降維，實現更高效的數據聚類。