基于Canopy的高效K-means算法

摘要：基于Map-reduce的并行編程方法，針對大規模集群多處理器多集群的聚類算法K-means的應用。提出了基于Canopy的改進K-means優化算法。實驗結果證明，多核Canopy－K-means聚類算法的運行效率和準確度與處理器核數成線性比例。

關鍵詞：K-means 多核處理 Map-reduce Canopy

Canopy for efficient K-Means

Qiu Rongtai

(Zhejiang University of Media and Communications，Hangzhou，310018， Zhejiang)

Abstract: In this paper， we develop a applicable parallel programming method which based on Map-reduce . A improved K-means algorithm based on Canopy is presented according to it’s sensitiveity to the initial centers. Our experimental results show basically linear speedup with an increasing number of processors .

Key words: K-means Map-reduce Multi-core Canopy

1.引言

計算機性能的提高將越來越依賴于處理器的數量的增加以及集群的規模.本文核心目標是通過應用Map-reduce并行編程框架，高效的利用數量眾多的可并行的處理器核，允許程序員輕松高效地開發一個多核機群機器學習算法canopy-k means。文章改進如下：

a針對傳統K-means算法對初始聚類中心依賴，利用Canopy聚類劃分來優化初始聚類中心。

b先將數據集進行Canopies有覆蓋劃分，在計算數據點到哪個K-center最短時，只計算與它在同一個Canopy下的K-centers距離而不必計算其到所有K-centers的距離，效率大大提高。

C每個數據集相對獨立，可以使用Map-reduce編程模型進行并行處理。

d處理器核數及處理節點的越多，其執行效率線性增長。

2.基于Mapreduce的Kmeans改進算法

2.1 算法思想

首先所有數據集按某種特征劃分成K類，每類的數據成員的特征相同。初始數據根據數據存儲節點及mapper核的個數P劃分成C1 C2……CP個數據集，每個數據集可以分別分配給某一Mapper節點獨立執行。集群中選擇一個節點作為master節點進行并行任務的調度，在主節點處設置兩個共享文件，這兩個文件可以被所有處理器訪問，其中一個文件包含初始隨機選的K個聚類中心點和每次迭代執行后產生的K個聚類的聚類中心。這是一個全局文檔，每次迭代都在這個文件后面增加一些記錄。另一個文件保存產生Canopies列表供全局調度用。Master節點負責管理各個Mapper節點和Reduce節點的調度及數據分配與結果的回收，分配給Mapper核相應的小數據塊，并且傳給每個Mapper節點K個聚類中心以及Canopies列表。每個Mapper核并行計算各自要求的任務后通知Master，然后Master調度相應的Reduce進行處理，返回結果以決定是否下一輪迭代。

首先用Canopy聚類技術分兩個階段執行聚類：第一步就是快速和近似地把數據分成一些子集，稱之為罩蓋（Canopy）；然后對每個Canopy內的點用精確的計算方法再聚類。它在兩個階段使用了不同的距離度量方法，形成重疊的Canopy.創建好Canopy后，第二步就是針對Canopy內的點使用K-means算法進行聚類。現在只需要對罩蓋內的點進行精確的聚類，從而大大避免了傳統聚類算法中對所有數據點進行精確計算，另外允許有重疊的子集也增加了算法的容錯性和消除孤立點作用。從某種意義上說，只要保證第一步的準確性，整個算法就是準確的，通過實驗表明，使用這種罩蓋技術后，不僅極大地減少了距離的計算量，其準確程度比一般的聚類方法還略有提高。

2.2 算法流程

2.2.1 數據預處理

將數據進行格式化，每一個數據都按特定的格式（數據值，出現次數）即（datavalue，emergetime），將每個數據按key為datavalue進行聚合，聚合后的每個數據為數據和出現次數的組合。

Mapper:(offset，datavalue)à(datavalue，1)

Reducer: (datavalue，1) à (datavalue，emergetime)

2.2.2 Canopies劃分

⑴ 總體思路：預處理后每一個數據（即datavalue）看作一個中心點，按Canopy算法產生一些可覆蓋的劃分，初始劃分以隨機選的第一個數據作為本聚類標識Canopyid。對于每個Mapper節點的數據，都須判斷它是否落入先前產生的Canopies中，若落入其中任意一個Canopy則標識自己相應的Canopyid，否則產生一個新的Canopy，并用自己的數據值作為Canopid。

⑵實現過程:在Master計算節點上存儲已產生的Canopies，這樣若某個節點產生新的Canopid要及時傳送給Master節點，以便其他節點讀取。

⑶實現方法：

Mapper: (datavalue，emergetime)à(Canopyid，( datavalue，emergetime))

Reducer: (Canopyid，( datavalue，emergetime)) à

(Canopyid，( datavalue，emergetime)，……， ( datavalue，emergetime))

2.2.3 將數據分配到Canopies

（1）總體思路：經過2.2.3.2處理后的數據，整個數據空間的數據劃分成了幾個Canopies，這些Canopies存儲于Master中。每個Mapper節點讀取Master中的Canopies，然后判斷每一個數據落在哪幾個Canopies上，并輸出數據和相應的Canopies（用其Canopid表示）。

（2）實現過程:Mapper計算節點上每個數據所屬的Canopid。

（3）實現方法：

Mapper: (datavalue，emergetime)à(datavalue，（emergetime， Canopyid_list）)

Reducer: (datavalue，（emergetime， Canopyid_list）) à

(datavalue，（emergetime， Canopyid_list）)

2.2.4 實現Canopy-Kmeans聚類

（1）總體思路：根據Canopy算法產生的Canopies代替初始的K個聚類中心點，由于已經將所有數據點進行Canopies有覆蓋劃分，在計算數據離哪個k-center最近時，不必計算其到所有k-centers的距離，只計算和它在同一個Canopy下的k-centers。這樣可以提高效率。

（2）實現過程:

每次Mapper節點在進行map()前需要通過Master節點加載上一次產生的K-centers和產生的Canopies列表，并計算每個K-center落入哪些Canopies中。

每次迭代過程mapper的輸入數據都是2.2.3.3產生的(datavalue，（emergetime， Canopyid_list）)。每個數據只用與落入該數據在同一個Canopy中的K-centers比較距離，選擇最短的那個K-center作為要劃分的類，再以K-center作為key，產生一條格式為:“k-centerid dativalule emergetime Canopyid_list”的記錄。

距離試題函數：每個數據點的dativalule之間差的絕對值。

（3）實現方法：

Mapper: (datavalue，（emergetime， Canopyid_list）)à

(k-centerid，(datavalue，emergetime， Canopyid_list）)

Reducer: (k-centerid，(datavalue，emergetime， Canopyid_list）) à

(new_k-centerid，(datavalue，emergetime， Canopyid_list）)

（4）最終結果的輸出：

我們可以把每次迭代后產生的new_k-centers與上一次的k-centers作比較，當他們的距離瀕于預先設定的閾值時，認為迭代結束，輸出最后一次的(k-centerid，(datavalue，emergetime， Canopyid_list）)格式為：”k-centers，datavalue_list”。

2.3 算法復雜性分析

K-Means法隨機選擇K個數據作為初始的聚類中心，按照算法的迭代執行，整個算法的結束條件是類的重心(或凝聚點)不再改變。傳統的K-Means的計算復雜性是O(dkt)，其中，d為文獻數量，k為類的數量，t為迭代次數。在運用Canopy算法對K-Means進行優化的情況下，由于在劃分Canopies是可覆蓋劃分，即某一點有可能同時屬于n個Canopies，這樣聚類需要比較dkn2t/c次， 其中C為Canopies的數量. 在多核框架下，其理論復雜性是O([dkn2tcp+dkn2log(P)/c])，其中P為處理器核的數量。K-Means 在多核并行執行情況下其效率將近是單核下的P倍，隨著核數的增多，效率線性增長。

3 .實驗與分析

為了便于研究，把算法分兩種情況下執行：一個在我們設計的框架下，另一個以傳統的方式順序執行。實驗數據從網絡上采集，在實驗開始之前在實驗環境的存儲設備上準備完畢。網絡上的數據主要是兩個部分，一部分是圖書館的數據，一部分是學校學生成績的數據。圖書館的數據大概有10G多，存放在Hadoop的分布式文件系統HDFS中。學校學生成績數據也有將近900M，同樣放在HDFS中。我們進行了大量的試驗來測試其效率。不僅如此，我們還分別在擁有不同核個數的處理器上執行。我們在 Intel X86 ，Intel(R) Core#8482; Duo CPU 2 MHz CPUs ， 2GB 物理內存 。并且在運行HP－UNIX的機器HP9000上分別做實驗。另外我們通過4，6，8，16 核的處理器上模擬試驗得到如下結果。在雙處理器執行過程中，執行各個數據的平均效率比原來大約提高了1.9倍。這是由于原始的K-means算法并沒有很好的利用處理器時鐘周期，然而在我們把任務獨立分給不同處理器并行的情況下算法效率得到了很大的提高。通過在2，4，8，16 多處理器機器上實驗，我們可以很直觀地把我們得到的結果描繪成圖2.在圖中，實線代表平均加速倍數，虛線分別代表最大與最小的加速倍數。分析圖中可知，隨著處理器個數的增加，我們得到的加速倍數是線性增長的，然而這個加速斜率略低于1。通過分析可知，沒有得到完整的線性增速是由于處理器之間相互通信和集合階段沒有并行的原因。在多核的情況下我們通過模擬試驗，結果比現在更理想，因為他們之間共享存儲區域，其相互通信比以前少。

圖1

4.結語

在處理器的頻率不變的情況下，同樣可以提高k means的效率而不受限于處理器的頻率。，通過多核處理器可以計算更大的數據集和獲得更好的效率。利用Map-reduce編程方法，使K-means算法在雙核的情況下效率提高了兩倍，在64核的情況下得到56倍的執行效率，得到線性增長的效率，并且對的初始點用Canopy算法進行優化提高了聚類的準確度。算法具有很大的適用范圍，本文創新之處是我們并沒有對原來的算法做根本的改變，只是提出應用Map-reduce并行執行K－means聚類算法以及對K－means初始聚類中心優化方法，顯著提高了執行效率。

參考文獻：

[1] Jeffrey Dean， Sanjay Ghemanwat， MapReduce: Simplified Data Processing on Large Clusters

[2] K-means算法中的k值優化問題研究，系統工程理論與實踐，2006年2期

[3]Kenneth Heafield Hadoop Design and K-Means Clustering Google Inc January 15 2008

[4] The impact of the canopy structure on the spatial variability in forest floor carbon stocks.Geoderma: An International Journal of Soil Science， 2010 3/4

[5] Dummler， Rauber， Runger， Mapping Algorithms for Multiprocessor Tasks on Multi-core Clusters

作者簡介：

邱榮太（1982－ ），男，漢族，浙江傳媒學院播音學院實驗辦，工程師，碩士，主要研究分布式及流媒體應用。