K—Means聚類算法在MapReduce框架下的實現(xiàn)

楊健兵

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

關(guān)鍵詞：K-Means；MapReduce；數(shù)據(jù)挖掘；聚類算法

DOIDOI：10.11907/rjdk.162043

中圖分類號：TP311

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

0 引言

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

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

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

1 MapReduce編程模型

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

1.1 MapRedue集群結(jié)構(gòu)

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

1.2 MapReduce執(zhí)行過程

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

2 K-Means聚類算法實現(xiàn)

2.1 K-Means聚類算法

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

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

E是數(shù)據(jù)集中所有對象的誤差平方和。

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

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

2.2 算法實現(xiàn)

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

2.2.1 Map函數(shù)設(shè)計

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

2.2.2 Reduce函數(shù)設(shè)計

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

2.3 算法時間復(fù)雜度分析

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

3 實驗結(jié)果

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

3.1 實驗環(huán)境

該實驗在南京工業(yè)大學(xué)云平臺上進行，平臺由一系列IBM服務(wù)構(gòu)建。其中管理節(jié)點1個，計算機節(jié)點16個，網(wǎng)絡(luò)采用萬兆網(wǎng)絡(luò)，操作系統(tǒng)采用RedHat Linux。在硬件配置上，每一個節(jié)點的CPU 采用Intel Xeon 2.0GCPU，8G內(nèi)存，100G硬盤，軟件配置Hadoop 。

3.2 實驗結(jié)果

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

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

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

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

4 結(jié)語

隨著互聯(lián)網(wǎng)業(yè)務(wù)的不斷發(fā)展，每天都有大量的數(shù)據(jù)產(chǎn)生，對于產(chǎn)生的數(shù)據(jù)用數(shù)據(jù)挖掘的方法對它進行分析并提取有益的信息已經(jīng)成為大家關(guān)注的重點。在源源不斷的數(shù)據(jù)產(chǎn)生以后，可以在MapReduce框架下采用K-Means方法對這些數(shù)據(jù)進行聚類。

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

參考文獻：

[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] 冀素琴，石洪波.面向海量數(shù)據(jù)的K-Means聚類優(yōu)化算法[J].計算工程與應(yīng)用，2014，50（14）：143-147.

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

[5] 黃斌，許舒人，蒲衛(wèi).基于MapReduce 的數(shù)據(jù)挖掘平臺設(shè)計與實現(xiàn)[J].計算機工程與設(shè)計，2013（2）：495-501.

（責(zé)任編輯：孫 娟）