摘 要： 隨著大數據時代的到來，傳統的聚類算法很難高效地處理海量數據，而云計算平臺憑借負載均衡、網絡存儲、虛擬化等技術，有效地突破了耗時耗能的瓶頸，為海量數據的處理提供了良好的解決方案。主要研究了Hadoop平臺下的MapReduce編程模型及傳統K-means算法，提出了一種基于MapReduce的并行化K-means算法的設計方案，包括Map函數和Reduce函數的設計。通過實驗，驗證了并行化K-means算法適用于較大規模數據集的分析和挖掘。
關鍵詞： 云計算；數據挖掘；MapReduce編程模型；K-means聚類算法；并行化
0 引言
隨著信息化社會的發展，各個行業中產生的數據都在以爆炸式的速度增長。典型的聚類算法——K-means算法是基于劃分的聚類算法，因其快速、簡單的特性而被廣泛應用。但在面對海量數據時，傳統的K-means算法無論是在時間復雜度還是空間復雜度上都遇到了瓶頸[1]，而云計算技術的出現為海量數據的處理提供了良好的解決方案。
云計算是一種基于互聯網的計算方式。Hadoop則是云計算技術的開源實現，具有高容錯、跨平臺等優勢。它主要包含兩個部分：分布式文件系統（HDFS）和MapReduce編程模型。本文在基于Hadoop云計算平臺，利用MapReduce編程模型實現了傳統K-means聚類算法的并行化設計，并進行了相關實驗的驗證。
1 MapReduce編程模型
MapReduce編程模型，顧名思義，由Map（映射）階段和Reduce（規約）階段組成，分別用兩個函數表示，即Map函數和Reduce函數[2]。MapReduce作業流程如圖1所示。
Map階段：Map任務運行在集群的從節點上，多個Map任務相互間是獨立運行的。原始數據在進入Map函數前，會將原始大數據集劃分并格式化為<key1，value1>鍵值對的形式。經過Map函數的運算處理后產生一個或多個中間鍵值對<key2，value2>。
Shuffle階段：它由Partition（數據分割）和Combine（數據合并）組成。Combine就是將Map任務輸出的中間結果中有相同key2的<key2，value2>對合并成一對。Partition則是采用默認hash函數將中間結果按照key2值的范圍分成R份，發送并保證某一范圍內的key2由同一個Reduce任務來處理。
Reduce階段：每個Reduce任務需要從多個Map任務節點取得其負責的key2區間內的中間結果。Reduce函數接收到形如<key2，（list of value2）>形式的輸入，進行處理后產生鍵值對<key3，value3>作為結果，并將結果輸出到HDFS上。
為了方便理解，上述過程中數據格式的變化如圖2所示。
2 基于MapReduce的并行K-means算法的設計
2.1 K-means聚類算法的基本思路
K-means算法是聚類算法中使用最廣泛的基于劃分的算法，其基本思想是：將空間中的n個對象集合以K個點為中心進行簇的劃分，歸類到與其距離最近的中點[3]。通過迭代的方式，逐次更新聚類中心的值并重新劃分簇，直至目標函數收斂。K-means算法采用距離作為相似性的評價指標，其目標函數可表示為：
其中，xi表示數據集X={x1，x2，…，xN}中第i個樣本，N為樣本總數；Cj表示第j個簇，K為簇的總個數，zj則表示第j個簇的中心。
假設共有n個數據對象，計劃劃分為K個簇，t為迭代次數，O為一次迭代中計算某一對象到各個類的中心距離的時間復雜度，那么串行實現K-means算法的時間復雜度為n×K×t×O[4]。由此可見，當面對大數據時，算法的時間復雜度將成倍地增加。
2.2 K-means聚類算法的MapReduce化的設計
K-means算法中，計算數據對象與聚類中心距離是該算法中反復進行的操作，并且每個數據對象到聚類中心距離的計算過程都是相互獨立的。圖3描述了基于MapReduce的并行K-means算法的設計方法，其中數據的分片由MapReduce環境自行完成，只需要編寫Map函數和Reduce函數的實現代碼即可。
2.2.1 Map函數的設計
首先，Map函數逐行掃描數據段，按行作為數據對象，記錄為<行號，數據內容>鍵值對；接著，與保存在全局變量中聚類中心進行運算，得出數據對象與各個聚類中心的距離；最后，將數據對象分配給距離最近的類中，產生<聚類ID，數據內容>鍵值對作為函數輸出。Map函數的偽代碼如下：
void map（LongWritable key，Text point，Context context）{
centerIndex=0；//初始化數據對象所在的類
minDis=MAXDISTANCE；
//初始化數據對象與聚類中心的最小距離
for（int i=0；i<k；i++）{//遍歷各個聚類中心
tempDis=Dis（point，cluster[i]）；
//計算數據對象與聚類中心的距離
if（tempDis<minDis）{
//將數據對象分配至距離最近的類
minDis=tempDis；
centerIndex=i；
}
}
context.write（centerIndex+1，point）；
//輸出<類ID，數據對象>鍵值對
}
2.2.2 Reduce函數的設計
首先，將擁有相同聚類ID的數據對象分配給同一個Reduce任務；接著，Reduce函數將記錄所接收到的樣本個數并將數據對象各個維坐標分別累加；最后，將各維坐標之和除以樣本個數得到各個維坐標的均值，計算結果就是該類新的聚類中心。Reduce函數的偽代碼如下：
void reduce（IntWritable key，Iterable<Text>value，Context context）{
int colnum=value.get（0）.size（）；//數據對象的屬性個數
for（int i=0；i<colnum；i++）{
double sum=0；
int rownum=value.size（）；//獲取數據對象的個數
for（int j=0；j<rownum；j++）{//計算每列的平均值
sum+=value.get（j）.get（i）；
}
avg[i] = sum/rownum；
}
context.write（key，avg）；
//輸出<聚類ID，聚類中心>鍵值對
}
將本輪reduce函數輸出的聚類中心與上一輪的聚類中心比較，若目標函數收斂，則算法結束；否則，本輪的聚類中心將寫入中心文件，作為新的聚類中心。
3 實驗與分析
實驗目的是比較在相同的硬件配置下，Hadoop集群中1個運算節點和普通計算機分別使用并行K-means算法和傳統串行K-means處理相同規模數據的能力。考慮到K-means算法對初始聚類中心有較強的依賴性，在相同數據集的條件下重復進行實驗10次，取平均值作為最終的實驗數據，實驗結果如表1所示。
表1中，t1表示使用傳統串行K-means算法處理數據集所花的時間；t2表示使用并行化K-means算法處理數據集所花的時間。通過實驗數據可以發現，當數據集的規模較小時，串行K-means算法的執行效率優于并行化K-means算法的執行效率，這是由于數據量小時，其計算任務所消耗的資源較少，但是在Hadoop平臺上啟動、分配任務以及進行作業間的交互卻需要耗費固定的資源。但隨著數據集規模的增大，計算任務所占用的資源的比例將不斷增大，使并行化算法的優勢得以體現，其運行時間的增長速度遠小于串行算法。另外，由于串行算法所消耗的資源快速地增長，系統將會報告內存不足。
4 結論
本文對Hadoop的MapReduce編程模型以及聚類算法K-means進行了研究，給出了基于MapReduce的并行化K-means算法的設計方案并進行了實驗驗證。實驗結果表明，基于MapReduce的并行化K-means算法適用于處理較大規模的數據挖掘任務，并且具有較好的計算效率。
參考文獻
[1] 謝雪蓮，李蘭友.基于云計算的并行K-means聚類算法研究[J].計算機測量與控制，2014，22（5）：1510-1512.
[2] 冀素琴，石洪波.基于MapReduce的K-means聚類集成[J].計算機工程，2013，39（9）：84-87.
[3] 周婷，張君瑛，羅成.基于Hadoop的K-means聚類算法的實現[J].計算機技術與發展，2013，23（7）：18-21.
[4] 趙衛中，馬慧芳，傅燕翔，等.基于云計算平臺Hadoop的并行K-means聚類算法設計研究[J].計算機科學與探索，2011，38（10）：166-168，176.