一種改進(jìn)K—means聚類算法的MapReduce并行化實(shí)現(xiàn)

栗國(guó)保++韓青菊

摘要：針對(duì)K-means聚類算法對(duì)初始聚類中心點(diǎn)的選擇較敏感的問(wèn)題，本文借鑒最大最小距離的思想，提出了一種改進(jìn)的K-means聚類算法。該算法通過(guò)優(yōu)化初始聚類中心點(diǎn)來(lái)減少算法的迭代次數(shù)，提高聚類的性能。采用MapReduce編程模型，將改進(jìn)的K-means聚類算法并行化設(shè)計(jì)，使用局部和全局的方法處理數(shù)據(jù)集，改變了傳統(tǒng)分布式K-means聚類算法的工作方式，有效的降低了算法執(zhí)行過(guò)程中的通信開(kāi)銷。實(shí)驗(yàn)結(jié)果表明改進(jìn)K-means算法的并行化實(shí)現(xiàn)具有良好的加速比。

關(guān)鍵詞：MapReduce模型 K-means 分布式聚類

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）12-0134-01

1 引言

聚類分析是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法，不需要預(yù)先對(duì)數(shù)據(jù)集進(jìn)行訓(xùn)練和測(cè)試等操作，是數(shù)據(jù)挖掘中對(duì)數(shù)據(jù)進(jìn)行分析處理的重要工具和方法[1]。由于聚類分析算法的簡(jiǎn)單、高效和易用等特點(diǎn)，其應(yīng)用范圍十分廣泛，針對(duì)各個(gè)領(lǐng)域的聚類算法也不盡相同。其中K-means聚類算法是聚類分析算法中最典型的算法，該算法的優(yōu)點(diǎn)是簡(jiǎn)單且易于實(shí)現(xiàn)，但隨著信息產(chǎn)業(yè)的快速發(fā)展，需處理數(shù)據(jù)的規(guī)模越來(lái)越大，其串行計(jì)算的處理能力的局限性更加明顯，于是分布式聚類的思想被廣泛關(guān)注[2-3]。但現(xiàn)有的分布式聚類算法在聚類過(guò)程中大多數(shù)需傳遞大量的數(shù)據(jù)，效率較低。為克服上述缺點(diǎn)，本文使用MapReduce編程模型實(shí)現(xiàn)了一種改進(jìn)K-means算法的分布式聚類。該算法在執(zhí)行過(guò)程中只需要傳遞各個(gè)聚簇信息，就能實(shí)現(xiàn)分布式聚類，降低了整個(gè)執(zhí)行過(guò)程的通信開(kāi)銷。

2 K-means聚類算法的MapReduce并行化

2.1 算法基本思想

從K-means聚類算法的特點(diǎn)不難看出，其并行化也是一個(gè)不斷迭代的計(jì)算算法，每次迭代都需要消耗大量的時(shí)間和通信量，所以本文對(duì)K-means聚類算法在初始中心點(diǎn)的確定上進(jìn)行了改進(jìn)，借鑒最大最小距離的思想計(jì)算出初次聚類的中心點(diǎn)，避免了該算法在隨機(jī)選擇中心點(diǎn)時(shí)中心點(diǎn)過(guò)于鄰近的情況發(fā)生，也降低了并行算法的迭代次數(shù)。同時(shí)，根據(jù)MapReduce模型的特點(diǎn)，在算法執(zhí)行的Map端，使用Combiner類對(duì)Map端生成的相同簇ID的數(shù)據(jù)點(diǎn)信息進(jìn)行歸并，減少了從Map端向Reduce端傳輸?shù)臄?shù)據(jù)量，從而降低了傳輸開(kāi)銷。

2.2 算法描述

輸入：數(shù)據(jù)集，聚類中心點(diǎn)個(gè)數(shù)

輸出：個(gè)聚類中心點(diǎn)

將原始數(shù)據(jù)集切塊后，存儲(chǔ)在HDFS中，Hadoop負(fù)責(zé)管理切分后的數(shù)據(jù)塊。

Stage1.初始聚類中心的計(jì)算。

1）各個(gè)Map節(jié)點(diǎn)讀取存放在本地的數(shù)據(jù)集，采用最大最小距離算法生成多個(gè)聚類集合。

2）在Reduce階段將Map階段生成的若干聚類集合采用K-means聚類算法生成個(gè)聚類中心點(diǎn)。

3）將生成的聚類中心點(diǎn)信息寫入cluster目錄中，并將該目錄中的文件加入到Hadoop的分布式緩存（DistributedCache）中用來(lái)作為下一階段聚類迭代時(shí)的全局共享信息。

Stage2.K-means算法的MapReduce實(shí)現(xiàn)。

1）每個(gè)Map節(jié)點(diǎn)在setup（）方法中讀入分布式緩存中上一輪迭代產(chǎn)生的簇中心信息。

2）通過(guò)Map方法計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與各簇中心點(diǎn)距離，找到離其最近的簇中心點(diǎn)，將該簇中心的ID作為key，該數(shù)據(jù)點(diǎn)信息作為value傳輸出去。

3）在Map端利用Combiner類將每個(gè)Map節(jié)點(diǎn)的相同簇ID的鍵值對(duì)分別進(jìn)行合并，以此減輕數(shù)據(jù)的網(wǎng)絡(luò)傳輸開(kāi)銷。

5）若最近兩次臨時(shí)中心點(diǎn)的變化小于指定值時(shí)，則轉(zhuǎn)6），否則轉(zhuǎn)1）。

6）結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

該實(shí)驗(yàn)利用VMware Workstation虛擬機(jī)，在其上虛擬出6臺(tái)機(jī)器，1臺(tái)作為NameNode和JobTracker服務(wù)節(jié)點(diǎn)，其他5臺(tái)作為DataNode和TaskTracker服務(wù)節(jié)點(diǎn)，每臺(tái)機(jī)器的配置為：Intel i3雙核處理器，內(nèi)存1G，操作系統(tǒng)是CentOS 6.4，Hadoop版本是0.20.2。

3.2單機(jī)處理實(shí)驗(yàn)分析

本實(shí)驗(yàn)使用UCI機(jī)器學(xué)習(xí)庫(kù)上的OULAD數(shù)據(jù)集，由于該數(shù)據(jù)集數(shù)據(jù)量大，故從中抽取3組數(shù)據(jù)作為獨(dú)立的數(shù)據(jù)集，編號(hào)分別為1、2、3，每個(gè)數(shù)據(jù)集包含2000條記錄。在相同數(shù)據(jù)集的條件下，比較K-means和本文改進(jìn)算法的迭代次數(shù)，實(shí)驗(yàn)數(shù)據(jù)如表1所示。從表中可看出，本文改進(jìn)的聚類算法較傳統(tǒng)K-means聚類算法有更好的收斂速度。

3.3 集群加速比性能實(shí)驗(yàn)分析

加速比是用來(lái)衡量并行系統(tǒng)或并行程序擴(kuò)展性的重要指標(biāo)[4]，是指一個(gè)任務(wù)在單處理器系統(tǒng)中運(yùn)行所消耗的時(shí)間與并行處理系統(tǒng)中運(yùn)行所消耗時(shí)間的比值。通過(guò)程序生成S1、S2、S3三個(gè)實(shí)驗(yàn)數(shù)據(jù)集，其數(shù)據(jù)量大小分別為：1G、2G、4G，利用改進(jìn)算法的MapReduce實(shí)現(xiàn)對(duì)每個(gè)數(shù)據(jù)集進(jìn)行聚類，分別選擇1、2、3、4、5個(gè)TaskTracker節(jié)點(diǎn)參與實(shí)驗(yàn)，考察節(jié)點(diǎn)數(shù)與加速比之間的關(guān)系。實(shí)驗(yàn)結(jié)果如圖1所示，從圖1可以看出：當(dāng)節(jié)點(diǎn)數(shù)逐漸增加時(shí)，加速比也隨之增加，但逐漸變慢，這是由于增加節(jié)點(diǎn)導(dǎo)致通信開(kāi)銷變大；當(dāng)數(shù)據(jù)量逐漸增大時(shí)，加速比的值也逐漸增大，這表明該并行算法在處理大數(shù)據(jù)集時(shí)，具有較高的效率。該實(shí)驗(yàn)數(shù)據(jù)表明本文改進(jìn)的聚類算法在MapReduce 上執(zhí)行具有良好的加速比。

4 結(jié)語(yǔ)

本文借鑒最大最小距離算法的思想，改進(jìn)了K-means聚類算法存在對(duì)初始聚類中心點(diǎn)的選擇敏感的缺陷，為提高改進(jìn)算法的計(jì)算效率，將該改進(jìn)算法并行化設(shè)計(jì)，使其能夠較好的運(yùn)行在Hadoop平臺(tái)上。實(shí)驗(yàn)表明該改進(jìn)算法的并行化設(shè)計(jì)具有較好的聚類性能。

參考文獻(xiàn)

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008，19（1）：48-61.

[2]宋玲，戚云楓，齊東陽(yáng).分布式k-means聚類算法的改進(jìn)[J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2014（5）：1060-1065.

[3]王愷.基于MapReduce的聚類算法并行化研究[D].南京師范大學(xué)，2014.

[4]江小平，李成華，向文，等.k-means聚類算法的MapReduce并行化實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2011，39（s1）：120-124.