宋董飛, 徐 華

(江南大學 物聯網工程學院,無錫 214122)

引言

隨著移動互聯網和物聯網技術的不斷發(fā)展,極大地豐富和便捷了人們的生活,但隨之也伴隨著巨量數據的產生. K-means作為典型的聚類算法,已很難適應大數據環(huán)境下的數據處理要求,其缺點主要表現為[1]：(1)隨機選擇初始中心點易使算法陷入局部最優(yōu);(2)迭代過程中需要進行大量冗余距離計算,增加算法復雜度; (3)面對海量數據集,傳統(tǒng)的串行K-means算法運行效率低.

針對傳統(tǒng)K-means算法的缺點,已有很多學者在K-means的基礎上提出了改進措施. 文獻[2,3]引入通過引入canopy算法,對K-means算法進行了優(yōu)化,利用canopy算法生成重疊子集,在生成的重疊子集中進行聚類,同時文獻[2]提出了基于“最大最小原則”的canopy中心點選擇方法,解決了canopy選擇的盲目性與隨意性,提高了算法的分類準確率,但在實際應用中非常耗時. 文獻[4]基于“距離最遠的樣本點不可能分到同一個簇中”這一事實,提出了最大距離法選取初始簇中心的K-means聚類算法,能夠選取質量較好的初始中心點,克服了傳統(tǒng)K-means算法聚類結果不穩(wěn)定和局部最優(yōu)等問題. 文獻[5,6]分別利用Mapreduce框架和Spark框架,實現了改進K-means算法的并行化,通過并行計算提高聚類速度,使其適用于海量數據聚類中.

基于以上研究,為了進一步減少數據聚類迭代過程中的冗余計算,加快聚類速度,提高聚類準確率,本文提出了SKDk-means (Spark based kd-tree K-means)并行聚類算法. 文獻[7]提出kd-tree數據結構,將其應用在K-means迭代過程中,加快聚類速度. 受文獻[7]啟發(fā),本文在初始點選取階段引入kd-tree數據結構,改善初始中心點預選取算法,并在迭代過程中利用kdtree解決了聚類過程中距離冗余計算的問題,同時將改進后的算法部署在Spark平臺上,通過并行計算提高數據處理的速度. 本文實驗分別以UCI標準數據集和人工產生的不同規(guī)模的數據集驗證算法具有較好的聚類質量和并行計算性能,更適合應用于海量數據的聚類分析中.

1 基于kd-tree改進的K-means聚類算法

1.1 kd-tree

kd-tree(k-dimensional tree)是由Bentley于1975年提出[8],k是空間數據對象的維度數,在多維的空間數據結構中,kd-tree常用來數據索引和數據查詢.

kd-tree的構建思想[9]是：選擇數據對象方差值最大的維度作為分割維度,為了保證左右子樹平衡,在分割維度上選取數據的中值. 根據選取的維度和中值將k維數據空間劃分為兩個部分,小于等于中值的點劃分到左子樹,大于中值的點劃分到右子樹. 我們可以繼續(xù)分別對這兩個子k維空間進行如上劃分,又會得到新的子空間,重復以上過程直到每個子空間都不能再劃分.

kd-tree上的最近鄰查找算法即在kd-tree中檢索與某一查詢點歐式距離最近的數據點[10]. kd-tree數最近鄰查找算法思想如下：從根節(jié)點遞歸地向下搜索,進行二叉搜索; 搜索到葉子結點,記為當前最近鄰nearest; 進行回溯搜索,如果超球面與父節(jié)點超平面相交,進入相反的空間搜索,更新nearest,否則繼續(xù)向上回溯,回溯到根節(jié)點,結束并返回最近鄰.

1.2 基于kd-tree的初始中心點選取算法

給出一組n個對象其中在N維空間中選擇數據對象方差最大的維度作為分割維度,分割值為該維度上坐標的中值,這樣將數據集分割為左右兩個大致相等的超矩形. 然后在每個超矩形上遞歸的執(zhí)行分割,直到任何超矩形不再劃分為止.

該方法以方差最大維度上的坐標中值進行分割,所以每個框中的對象個數大致相同. 該屬性顯示,如果超矩形中的物體的密度比其他超矩形中的物體密度更高,則該超矩形的體積更小.

假設超矩形i中所有對象的平均值為mi,計算公式如下：

其中n表示超矩形中數據對象的個數,xi表示超矩形中的數據對象.

超矩形的密度,顧名思義就是表示超矩形單元中數據對象的密集程度,我們用ρi表示,其定義如下：

其中,Ni表示超矩形單元內數據對象數量;Vi表示超矩形的體積;dmax、dmin分別表示超矩形內數據的最大值和最小值.

q個超矩形的密度表示為其對應的超矩形中心表示為選擇初始中心方法如下：首先選擇密度最高的超矩形中心mi作為第一個選取的初始中心點.

我們通過公式計算gi[11]來選擇第2個初始中心點.選擇最大gi的超矩形中心mi作為第2個初始中心點

當第t個初始中心點已經被選擇,那通過下面的公式計算gi來選取第t+1個初始中心點. 選擇滿足gi最大超矩形的mi作為第t+1個初始中心點：

算法描述如下：

算法1. 基于kd-tree的初始中心點選取算法.

2) forj=1,…,q計算超矩形的中心mi和密度ρi.

4) fort=2,…,k：

forj=1,…,q計算

第t個初始中心其中

1.3 基于kd-tree的K-means算法

在kd-tree中采用最近鄰查找思想,檢索kd-tree中與查詢點距離最近的數據點,可以很快速的找到最佳點,而不需要進行過多的距離計算. 在K-means算法中,我們引入kd-tree這一數據結構,建立聚類中心點的kd-tree,然后采用最近鄰查找思想,將各數據點分配給距離最近的中心點,很好地解決了K-means算法聚類迭代過程中距離冗余計算的問題.

本文提出的基于kd-tree優(yōu)化的K-means聚類算法的基本思想是：首先應用基于kd-tree改進的初始中心點選取算法即算法1,選取出k個有效的初始聚類中心點然后建立聚類中心點集C的kd-tree,數據點依次遍歷kd-tree,采用最近鄰查找的思想,將數據點分配給距離最近的中心點. 各數據點都分配給最近的聚類中心后,進行全局的聚類中心點更新,將更新后的聚類中心點與原中心點比較,判斷是否收斂. 若不收斂則進行迭代; 若收斂則退出迭代,輸出聚類結果.

算法描述如下：

算法2. 基于kd-tree優(yōu)化的K-means聚類算法.

輸出：k個最優(yōu)聚類結果簇.

1) 應用算法1,選出k個有效的初始聚類中心點

2) 建立中心點的kd-tree.

3) 將數據集中每個點依次遍歷kd-tree：

① 從kd-tree根節(jié)點出發(fā),遞歸地向下搜索,如果xi的當前維度上坐標值小于分裂點的值,則進入其左子樹進行搜索,否則進入到右子樹進行搜索,直到葉節(jié)點為止,記錄下搜索路徑,將葉節(jié)點標記為Nearest,計算葉節(jié)點與xi的距離Distance;

② 根據①中記錄的搜索路徑遞歸地向上回溯,計算搜索路徑上的每一個節(jié)點與目標點的距離,如果其與目標點xi的距離小于Distance,則更新此節(jié)點為最近點Nearest,同時更新Distance,比較Distance與xi到分裂軸的距離如果Distance比xi到分裂軸的距離大,則需要向此節(jié)點父節(jié)點的另一個分支進行搜索; 否則繼續(xù)回溯,直到退回到根節(jié)點,搜索結束,此時的Nearest即為xi的最近聚類中心.

4) 更新聚類中心點,并計算數據對象的誤差平方和判斷是否收斂,若收斂則停止迭代; 否則進入2) 重復以上步驟,直至算法收斂.

5) 輸出k個最優(yōu)聚類中心點,完成聚類.

2 基于Spark的K-means算法并行化實現

2.1 Spark框架

Spark[12]由加州大學伯克利分校的AMP實驗室開發(fā),在處理大規(guī)模數據時,Spark表現出其特有的優(yōu)勢.Spark通過引入內存計算,在各計算節(jié)點內存內分布式緩存數據集,從而大大減少了磁盤I/O操作時間,這一特性使Spark特別適合運用于需要多次迭代的機器學習算法中.

Spark運行架構如圖1所示. Spark可以高效的部署在一個計算節(jié)點到數千個計算節(jié)點之間,為了實現Spark集群在各個計算節(jié)點之間的通信與資源分配,Spark支持多種集群資源管理器(standalone、Mesos或Yarn). Spark context對象在主程序中負責總體調度,并可與集群管理器相連接,本文選擇的是Yarn模式.

圖1 Spark運行架構圖

2.2 初始點選取階段

基于kd-tree改進的K-means算法改善了初始點選擇問題,并減少了迭代過程中的距離計算,但kdtree的建立以及kd-tree的搜索都需要花費很多的時間代價,并不適用于海量數據的聚類. 本文利用Spark并行計算框架實現了基于kd-tree改進的K-means算法,使其能應用于海量數據聚類中. 基于Spark的kdtree優(yōu)化K-means算法主要分為兩個階段：初始點選取階段和基于kd-tree的K-means并行階段.

初始點選取階段,我們通過并行建樹和并行計算各超矩形屬性值,在確保初始聚類中心點選擇效果的同時,減少初始點選擇的時間. 啟動算法,集群從HDFS讀取數據集形成初始RDD0; RDD0啟動map算子執(zhí)行Vectors.dense(),將原始文本數據轉化為可處理的向量數據鍵值對,形成RDD1; RDD1啟動map算子通過statistics.clostats計算數據方差最大的維度值,并形成(維度值,維度值上的數據值)形式的鍵值對,保存為RDD2; RDD2啟動reduceByKey、countByKey算子計算該維度上數據分割點split、該維度上數據個數count; RDD1啟動map算子判斷各條數據劃分維度上的數據值與split的大小,并據此進行左右子樹劃分,左子樹的鍵在原key后面添加0作為新的鍵,右子樹的鍵在原key后面添加1作為新鍵. 然后再依次對RDD1執(zhí)行上述算子,將左右子樹進行劃分,每次循環(huán)的最后對相應RDD執(zhí)行count函數,計算出葉子節(jié)點個數,當葉子節(jié)點個數大于聚類個數k時,停止劃分.這樣完成了kd-tree并行建樹過程.

RDD1啟動countByKey計算各超矩形中包含數據的個數,記為countKey. 對RDD1啟動reduceBy Key算子,通過公式(1),可計算出各個葉超矩形的中心點形成RDDm. 對RDD1啟動reduceByKey算子,通過公式(2)來計算出各超矩形的密度,形成RDDd. 對RDDd啟動reduceByKey計算出密度最大的超矩形,并將其中心加入初始中心點集C中. 對于C中已有點,RDDm啟動mapValues算子,根據公式(4)計算出各超矩形的gi,選出最大的gi的超矩形中心加入C中,更新C繼續(xù)迭代計算. 當C中點的個數為k時,保存初始中心點數據,程序結束. 初始中心點選取階段流程如圖2.

圖2 初始中心點選取流程圖

2.3 基于kd-tree的K-means并行計算階段

K-means算法利用kd-tree的最近鄰搜索,可以有效地減少迭代過程中不必要的距離計算,將各個數據點快速劃入所屬簇中,從而大大地加快了聚類速度. 各從節(jié)點間的并行計算,總體上是采用“map”和“reduce”的思想,并行計算流程圖如圖3所示.

圖3 SKDk-means并行聚類算法流程

算法開始,程序讀取初始中心點選取階段選取的中心點數據,建立初始中心點的kd-tree,保存為center_tree,并將center_tree作為廣播變量發(fā)送給所有工作節(jié)點. 程序讀取原始數據集保存為RDD_data,RDD_data啟動map算子,map中的函數為kd-tree的最近鄰查找函數：首先比較數據點當前坐標是否小于分裂點的坐標,如果小于進入左子樹搜索,否則進入右子樹搜索,直到葉節(jié)點為止,標記為Nearest,計算葉節(jié)點與數據點距離記為Nearest; 進行回溯搜索,如果回溯點的超球面與父節(jié)點抄平面相交,進入相反空間搜索,更新Nearest,否則繼續(xù)向上回溯,回溯到根節(jié)點,返回Nearest. 數據集遍歷kd-tree,形成(Nearest,數據點)形式的鍵值對,記為RDD_kv. RDD_kv啟動reduceByKey算子,計算出新的聚類中心,并計算誤差平方和判斷是否收斂,若不收斂則建立新聚類中心的kd-tree,進行迭代; 若收斂則輸出聚類結果.

3 實驗結果與分析

3.1 實驗環(huán)境、實驗數據及評價指標

實驗采用阿里云平臺的服務器,創(chuàng)建了一個Master節(jié)點,6個Slave節(jié)點. Master配置為8 G內存,80 G硬盤; Slave配置為8 G內存,160 G硬盤.Hadoop版本為2.7.2,Spark版本為2.0.2.

實驗測試數據利用UCI[13]數據集下的Iris、Wine、Ecoli來驗證算法的有效性,數據集詳細情況如表所示.為了驗證算法的并行效果,采用了人工數據集Data1～4,數據集詳細信息如表1和表2所示.

表1 實驗測試數據集

表2 人工數據集Data1～4

為了測試SKDk-means算法的整體性能,采用以下評價指標：準確率、加速比(Sizeup)、擴展比(Scaleup).

3.2 實驗結果

1) 算法準確度

為了驗證算法的有效性,利用Iris、wine、Ecoli數據集進行20次實驗,取20次實驗的平均值為最終值. 在傳統(tǒng)k-means算法中,由于每次聚類初始中心為隨機選擇,聚類效果不穩(wěn)定,迭代次數較多,而本文算法優(yōu)化了初始中心點的選擇,擁有十分穩(wěn)定的聚類結果. 由表3可知,文本算法正確率高于傳統(tǒng)k-means算法.

表3 數據集測試結果

2) 算法擴展性

為了分析算法在Spark框架下并行執(zhí)行的性能,需要計算算法執(zhí)行的加速比. 加速比是用來衡量程序執(zhí)行并行化的重要指標. 算法的加速比曲線如圖4所示. 在數據量較小時,隨著節(jié)點數的增加,加速比開始時線性增加,后漸漸趨于平緩或逐漸下降,這是因為當數據規(guī)模較小時,數據量遠小于集群能夠處理的數據量,這時再將數據分成很多小塊發(fā)送給各子節(jié)點,隨著子節(jié)點數目增加,集群運行時間、任務調度時間、數據通信時間增加,降低了計算速度,此時并行效果不佳;數據量較大時,加速比隨著節(jié)點數增加線性上升,雖然距離“理想加速比”這個理想狀態(tài)還很遠,但此時的并行效果已很明顯. 這說明,數據規(guī)模越大,SKDkmeans算法的處理效率越高,聚類效果越明顯.

圖4 SKDk-means算法的加速比

當集群中的計算節(jié)點的數目不斷增加時,并行算法的加速比并不能無限地增大,此時僅用“加速比”已不能反映集群的利用率,因此引入并行算法效率(擴展比)的概念. 如圖5所示,數據量較小時擴展比下降很快,此時集群得不到很好的利用; 當數據量增大時,擴展比下降速率相對趨緩,并逐漸趨于穩(wěn)定. 綜合算法的加速比和擴展比,樣本規(guī)模越大,SKDk-means算法的處理效率越高,聚類效果越明顯.

圖5 SKDk-means算法的擴展比

4 結束語

本文針對傳統(tǒng)K-means算法隨機選擇初始點及迭代過程中冗余距離計算問題,通過引入kd-tree數據結構,對算法進行了改進,并將改進后的算法應用于Spark大數據計算框架,實現了算法的并行化. 實驗驗證了該算法具有較高的聚類準確率,并且具有優(yōu)良的加速比和擴展比,適合應用于海量數據聚類中.

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

2 毛典輝. 基于MapReduce的Canopy-Kmeans改進算法. 計算機工程與應用,2012,48(27)：22-26,68. [doi：10. 3778/ j.issn.1002-8331.2012.27.005]

3 衣治安,王月. 基于MapReduce的K_means并行算法及改進. 計算機系統(tǒng)應用,2015,24(6)：188-192.

4 翟東海,魚江,高飛,等. 最大距離法選取初始簇中心的K-means文本聚類算法的研究. 計算機應用研究,2014,31(3)：713-715,719.

5 張石磊,武裝. 一種基于Hadoop云計算平臺的聚類算法優(yōu)化的研究. 計算機科學,2012,39(S2)：115-118.

6 劉鵬,滕家雨,張國鵬,等. 基于Spark的大規(guī)模文本kmeans并行聚類算法. 第二屆CCF大數據學術會議論文集. 北京,中國. 2014. 1-11.

7 Tiwari S,Solanki T. An optimized approach for k-means clustering. 9th International ICST Conference on Heterogeneous Networking for Quality,Reliability,Security and Robustness. 2013. 5-7.

8 Bentley JL. Multidimensional binary search trees used for associative searching. Communications of the ACM,1975,18(9)：509-517. [doi：10.1145/361002.361007]

9 陳曉康,劉竹松. 基于改進Kd-Tree構建算法的k近鄰查詢. 廣東工業(yè)大學學報,2014,31(3)：119-123.

10 Panigrahy R. An improved algorithm finding nearest neighbor using Kd-trees. Proceedings of the 8th Latin American Conference on Theoretical informatics. Búzios,Brazil. 2008. 387-398.

11 Redmond SJ,Heneghan C. A method for initialising the K-means clustering algorithm using Kd-trees. Pattern Recognition Letters,2007,28(8)：965-973. [doi：10. 1016/j.patrec.2007.01.001]

12 Zaharia M,Chowdhury M,Franklin MJ,et al. Spark：Cluster computing with working sets. Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.Boston,MA,USA. 2010. 10.

13 UCI. UCI machine learning repository. http：//archive.ics.uci.edu/ml,2015-03-30.