K—Means聚類算法在MapReduce框架下的實現

楊健兵

摘 要：MapReduce是一種編程模型，這種編程模型編程簡單，不必關心底層實現細節，可用于大規模數據集的并行計算。K-Means是一種簡單、基本的數據挖掘聚類方法，它將對象組織成多個互斥的組或簇。針對K-Means的特點，給出了MapReduce編程模型下K-Means的實現方法。實驗結果表明，MapReduce編程模型下的K-Means算法部署在Hadoop集群上運行具有較好的性能。

關鍵詞：K-Means；MapReduce；數據挖掘；聚類算法

DOIDOI：10.11907/rjdk.162043

中圖分類號：TP311

文獻標識碼：A文章編號：1672-7800（2016）012-0030-03

0 引言

伴隨著計算機技術的不斷進步和互聯網技術在各領域的深入發展，海量數據在各行業中不斷產生。由于傳統的數據挖掘算法往往運行在一臺普通的計算機上，但面對大量的數據尤其是海量數據時，傳統的計算機在計算能力、處理速度、存儲容量、帶寬速度等多個方面往往表現出力不從心。面對這些問題，云計算提出使得這些問題迎刃而解。云計算是基于網絡平臺上的一種計算模型，可以在多臺計算機上同時平行運行。它的模型可以由一系列普通計算機加上網絡組成，對計算機硬件要求相對較低，但其性能可達到普通計算機的若干倍以上。這種計算模型為數據挖掘領域開辟了一條新路徑。

MapReduce模型[1]是美國谷歌公司提出的一種分布式并行編程模型，其主要功能是可以利用大量計算機處理海量的數據。對于MapReduce這種編程模型，Map和Reduce是其主要思想，通過Map和Reduce，編程人員可以在不通曉分布式并行編程的情況下，將自己的程序運行在分布式系統上。通過Apache開源社區Hadoop項目[2]，程序設計人員實現了該模型，使得該模型進行分布式并行計算成為可能。

根據文獻記載，多種數據挖掘算法已經在云計算編程模型MapReduce上實現。冀素琴等[3]提出了基于MapReduce的K-Means聚類集成，謝雪蓮等[4]提出了基于云計算的并行K-Means聚類算法研究，黃斌等[5]提出了基于MapReduce 的數據挖掘平臺設計與實現，毛典輝等[6]提出了基于MapReduce的Canopy-Kmeans改進算法。本文結合各自算法的思想與MapReduce 的運行機理，提出K-Means聚類算法在MapReduce框架下的實現。在MapReduce框架下，K-Means聚類算法的使用范圍由單機擴展到云計算平臺，在面對海量數據時，極大地減少了K-Means聚類算法的運行時間，顯著地提高了運行效率。

1 MapReduce編程模型

MapReduce編程模型采用分治法的思想，在主節點管理下，MapReduce編程模型將海量的數據分發給各分節點共同完成，各節點對中間結果進行分類、排序、整合并得到最終結果。簡言之，MapReduce就是任務分解與結果匯總。

1.1 MapRedue集群結構

MapReduce任務需由幾個部分協作完成。它主要有4個部分組成：Client客戶端、JobTracker、TaskTracker以及分布式文件系統。

1.2 MapReduce執行過程

在Hadoop中，有兩個機器角色用來執行MapReduce任務，一個是JobTracker，另一個是TaskTracker。JobTracker的作用是執行調度工作，在Hadoop集群中有且只有一個，TaskTracker的作用是執行任務，在Hadoop集群中有若干個。圖1描述了MapReduce的運行機制，在數據輸入階段，輸入文件按照一定的標準進行分片；在Map階段，在JobTracker的統一調度下，多個TaskTracker完成Map運算任務并生成中間結果；在Shuffle階段完成中間計算結果的排序和分類；在Reduce階段，在JobTracker統一調度下，多個TaskTracke完成Reduce任務；Reduce任務完成后通知JobTracker以產生最后的輸出結果。

2 K-Means聚類算法實現

2.1 K-Means聚類算法

K-Means算法是很典型的基于距離的聚類算法，它將對象組織成多個互斥的組或簇，一般采用歐式距離作為評價指標，即認為兩個對象的距離越近，其相似度就越大。假設數據集D包含n個歐式空間中的對象。聚類的目的是將D的對象分配到k個簇C1，…，Ck中，使得對于1≤i，j≤k，Ci∈D且Ci∩Cj=￠。聚類劃分以簇內高相似性和簇間低相似性為目標。

設p是空間中的點，表示給定的數據對象；ci是簇Ci的中心，其中p和ci都是多維數據。對象p∈Ci與該簇的代表ci之差用dist（p，ci）度量，其中dist（x，y）是兩個點x和y之間的歐式距離。簇Ci的質量可以用簇內變差度量，它是Ci中所有對象與中心ci之間的誤差平方和，定義為：

E是數據集中所有對象的誤差平方和。

根據給定的公式，K-Means算法的具體實現過程如下：在初始化過程中，在數據集中任意選擇k個對象，每個對象代表該簇的中心點，對于其余的每個對象，根據它們與各簇中心的距離，將該對象劃分到最近的簇。然后對于k個簇，重新計算其均值。更新后的均值作為該簇新的簇中心。迭代繼續，直到分配穩定。圖2為K-Means聚類算法的串行計算流程。

K-mean均值的算法復雜度為O（nkt），其中n是對象總數，k是用戶指定的簇數，t為迭代次數。通常情況下k<

2.2 算法實現

K-Means聚類算法在MapReduce模型下處理的基本思路如下：對K-Means的串行計算過程執行MapReduce計算，Map階段完成每個記錄到簇中心點距離的計算，并標記到每個記錄所屬的類別；在Reduce階段，根據Map函數得到的結果進行分類排序即可計算出新的聚類中心，供下一輪Map使用，如果本輪Reduce得到的聚類中心與上輪相比變化小于給定的閾值則算法結束，反之進行新一輪的MapReduce過程。

2.2.1 Map函數設計

Map階段的主要任務是通過計算每個記錄到簇中心點距離，并將該記錄標記所屬的簇。在進行Map計算之前，MapReduce會根據輸入文件計算輸入數據片分片，每個數據片針對一個Map任務，輸入數據片存儲的并非數據本身，而是，key為行號，value為該記錄行的內容。Map函數對輸入的每個記錄行計算其到所有簇中心的距離，并根據最小距離將該記錄標示到最近的簇中心，并作出新類別標記。輸出中間結果以對的形式展現。

2.2.2 Reduce函數設計

在Reduce階段，根據Map函數得到的中間結果將相同類別的數據組成一個簇，并計算出新的聚類中心，供下一輪Map使用。輸入數據以（key， value）對的形式展示，key為聚類所屬類別，value為該簇中記錄向量，所有key相同的數據送給一個Reduce任務，累計計算key相同數據的均值，得到新的聚類中心。輸出結果，其中key為聚類類別，value是均值。Map和Reduce處理過程如圖3所示。

2.3 算法時間復雜度分析

在MapReduce框架下處理K-Means聚類算法，數據預處理階段，通過Hadoop平臺下的分布式文件系統，把要處理的數據先存儲在其中，然后將數據根據分塊原則分別存儲在不同的節點上。在Map計算階段，通過將相應的數據塊分配給Map任務進行計算。如果每個節點完成p個Map任務，那么其時間復雜度為O（nkt/p）。這樣可大大提高計算效率和計算速度，節省算法運行時間。

3 實驗結果

通過實驗，對K-Means聚類方法在MapReduce框架下的實現效果進行了展示和評估。

3.1 實驗環境

該實驗在南京工業大學云平臺上進行，平臺由一系列IBM服務構建。其中管理節點1個，計算機節點16個，網絡采用萬兆網絡，操作系統采用RedHat Linux。在硬件配置上，每一個節點的CPU 采用Intel Xeon 2.0GCPU，8G內存，100G硬盤，軟件配置Hadoop 。

3.2 實驗結果

單個樣本為15個整數，分別生成106（54M）、107（540M）、108（5400M）個樣本作為數據集。K-Means算法的實驗結果如圖4、圖5、圖6所示。

從圖4可看出，并行運行時間遠遠地大于單擊運行時間。這是由于MapReduce進行并行計算之初，其初始化過程需要一定的時間，耗費一定的機器性能。同時由于該文件只有54M，只需要分配給一個Map任務去執行。因此對于數據量比較少的數據，單機運行的效率反而高、時間耗費反而少。

從圖5可看出，隨著數據量的增多，MapReduce的優勢慢慢地凸顯出來。根據理論計算，540兆數據可以分為9個分片，通過分析，如果節點數量比較少的時候，MapReduce的優勢不但不夠明顯，反而還不如單機K-Means計算，但是隨著節點逐漸增多，MapReduce的計算優勢逐漸顯露起來，并且計算時間逐漸減少。但是當節點超過5個時，節點數目已經飽和，所以運行時間基本保持不變。

從圖6可看出，當數據量非常大時，MapReduce的絕對優勢一覽無遺，并且隨著集群中節點數量的增加，運行時間逐漸減少。當節點到達一定數目時，MapReduce運行算法達到它的極限值，該任務的運行時間達到最小。

4 結語

隨著互聯網業務的不斷發展，每天都有大量的數據產生，對于產生的數據用數據挖掘的方法對它進行分析并提取有益的信息已經成為大家關注的重點。在源源不斷的數據產生以后，可以在MapReduce框架下采用K-Means方法對這些數據進行聚類。

本文提出了面對大量數據時如何使用MapReduce框架去處理這些數據的基本思路。實驗表明，該解決方法在處理大量數據時可以極大地提高運行速度和效率。

參考文獻：

[1] DEAN J，GHEMAWAT S.MapReduce simplified data processing on large cluster[J].Communication of the ACM，2006，51（1）：107-113.

[2] APACHE HADOOP. Hadoop[EB/OL].http：//hadoop.apache.org.

[3] 冀素琴，石洪波.面向海量數據的K-Means聚類優化算法[J].計算工程與應用，2014，50（14）：143-147.

[4] 謝雪蓮，李蘭友.基于云計算的并行K-Means聚類算法研究[J].計算機測量與控制，2014，22（5）：1510-1512.

[5] 黃斌，許舒人，蒲衛.基于MapReduce 的數據挖掘平臺設計與實現[J].計算機工程與設計，2013（2）：495-501.

（責任編輯：孫 娟）