基于Hadoop的并行聚類算法的研究

摘 要：本文介紹了Hadoop平臺(tái)下MapReduce的并行編程框架，分析了傳統(tǒng)Kmeans聚類算法的優(yōu)缺點(diǎn)，提出基于Canopy的Canopy-Kmeans聚類算法。使用Canopy聚類先對(duì)數(shù)據(jù)進(jìn)行“粗”聚類，以優(yōu)化Kmeans聚類算法初始聚類中心的選取。選用MapReduce并行編程方法。實(shí)驗(yàn)表明該方法相對(duì)于傳統(tǒng)Kmeans聚類算法有著更高的計(jì)算效率。

關(guān)鍵詞：Hadoop；MapReduce；聚類；Canopy-Kmeans算法

中圖分類號(hào)：TP391.1

Hadoop[1]是一種開源式的分布式平臺(tái)，由它的分布式文件系統(tǒng)（HDFS）和MapReduce編程模型組成，這是Hadoop的核心。Kmeans算法[2]是被廣泛使用的經(jīng)典的聚類算法之一，思想簡(jiǎn)單，收斂速度快，而且易于實(shí)現(xiàn)，但是要先確立初始聚類中心，容易受主觀因素的影響而造成聚類結(jié)果的局部最優(yōu)。為解決該問題，本文引入Canopy對(duì)算法初始中心點(diǎn)的選取進(jìn)行優(yōu)化處理。

1 MapReduce并行編程模型

MapReduce是現(xiàn)在各種云計(jì)算平臺(tái)的基礎(chǔ)模型。此模型的核心是Map和Reduce函數(shù)，他們都可以高度并行運(yùn)行。Map函數(shù)可以處理多組數(shù)據(jù)，把一對(duì)Key＼Value對(duì)映射成新的Key＼Value對(duì)，Reduce的輸入數(shù)據(jù)為Map函數(shù)的輸出數(shù)據(jù)。由并發(fā)Reduce函數(shù)來確保所有映射Key＼Value對(duì)中的每組都有相等的Key鍵值[3]。MapReduce的運(yùn)行機(jī)制是將大數(shù)據(jù)集分解成為許多小數(shù)據(jù)集splits，每個(gè)數(shù)據(jù)集分別由集群中的一個(gè)節(jié)點(diǎn)執(zhí)行Map過程并生成中間結(jié)果。接著這些中間結(jié)果被大批的并行執(zhí)行的 Reduce過程做相應(yīng)的處理，從而產(chǎn)生最終結(jié)果，輸出給用戶[4]。

2 Canopy-Kmeans算法

2.1 算法的思想

Canopy-Kmeans算法采用Canopy進(jìn)行初始聚類中心點(diǎn)的優(yōu)化。數(shù)據(jù)子集分別分布在集群中的各個(gè)不同的站點(diǎn)。在Map階段引用Canopy算法迅速地產(chǎn)生多個(gè)局部Canopy中心，各站點(diǎn)傳來的局部Canopy中心在Reduce階段被再次利用 Canopy算法得到全局的canopy中心集合。與Map階段不同的是可對(duì)閾值t1、t2（t1>t2）進(jìn)行重置。意思是Reduce階段的閾值可與Map階段的不同，以便能得到下步Kmeans所需的k個(gè)初始聚類中心。

2.2 基于MapReduce的Canopy-Kmeans算法

在基于Hadoop的并行Kmeans算法的基礎(chǔ)上，本文使用Canopy算法對(duì)Kmeans 算法進(jìn)行優(yōu)化。Canopy-Kmeans算法包括兩部分：Canopy生成中心點(diǎn)算法和Kmeans算法。Canopy中心點(diǎn)的生成過程包括Map和Reduce函數(shù)。算法實(shí)現(xiàn)需四個(gè)階段，分別用四個(gè)Job實(shí)現(xiàn)。如圖1所示。Job1生成k個(gè)canopy中心。Job2借助Job1階段的k個(gè)canopy中心點(diǎn)來生成k個(gè)相互重疊的canopy。Job3對(duì)處于同一canopy內(nèi)的數(shù)據(jù)集進(jìn)行K-means聚類。通過多次的迭代，生成穩(wěn)定的Kmeans聚類中心。最后，Job4使用穩(wěn)定的Kmeans聚類中心點(diǎn)開始聚類。直到輸出最終結(jié)果。

圖1 Canopy-Kmeans 實(shí)現(xiàn)流程

3 算法時(shí)間復(fù)雜度分析

傳統(tǒng)的Kmeans算法的時(shí)間復(fù)雜度為O（nck）。其中n為數(shù)據(jù)對(duì)象數(shù)量，c為迭代次數(shù)，k為類數(shù)量。該文引入Canopy聚類，產(chǎn)生k個(gè)canopy，每一個(gè)數(shù)據(jù)對(duì)象有可能同時(shí)屬于q（q≤k）個(gè)canopy。當(dāng)集群數(shù)量為p時(shí)，可知算法的時(shí)間復(fù)雜度為O（ncq2k/p）。可以看出該算法的時(shí)間復(fù)雜度與傳統(tǒng)的Kmeans時(shí)間復(fù)雜度相比明顯降低了。

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

4.1 數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)數(shù)據(jù)是從UCI機(jī)器學(xué)習(xí)庫中選取的部分?jǐn)?shù)據(jù)集，如表1所示。這些標(biāo)準(zhǔn)數(shù)據(jù)集用以準(zhǔn)確度量本文算法的聚類效果。

表1 實(shí)驗(yàn)數(shù)據(jù)集

數(shù)據(jù)集樣本數(shù)屬性數(shù)類別數(shù)

Synthetic_Control600606

Segmentation2310187

Waveform-405000403

Hadoop為開發(fā)平臺(tái)，運(yùn)用MapReduce編程框架完成實(shí)驗(yàn)。本實(shí)驗(yàn)是在5臺(tái)VMWare平臺(tái)下的虛擬機(jī)搭建成的Hadoop集群環(huán)境中完成，實(shí)驗(yàn)由5臺(tái)PC機(jī)構(gòu)成，其中一臺(tái)作為主節(jié)點(diǎn)，剩余四臺(tái)作為從節(jié)點(diǎn)。

4.2 實(shí)驗(yàn)結(jié)果及分析

將本文算法與MapReduce框架下的Kmeans聚類（算法a）、Weka環(huán)境下的串行Kmeans聚類（算法b）做比較。實(shí)驗(yàn)結(jié)果如表2所示。實(shí)驗(yàn)結(jié)果表明，算法a、b的正確率和誤差平方和相對(duì)接近，可以看出該算法的聚類效果明顯更好。

表2 實(shí)驗(yàn)結(jié)果

數(shù)據(jù)集算法a算法b本文算法

正確率/（%）誤差平方和迭代時(shí)間/ms正確率/（%）誤差平方和迭代時(shí)間/ms正確率/（%）誤差平方和Canopy聚類時(shí)間/ms迭代時(shí)間/ms

Synthetic_Control66.9600.0719154364.8604.651094871.35533.5418945173475

Segmentation56.70606.0720376254.9607.201169365.21390.6519715145665

Waveform-4061.83530.3299855759.1540.741094669.36490.9794810564431

從算法的迭代時(shí)間來看，算法a的迭代時(shí)間比本文算法的迭代時(shí)間要長(zhǎng)。這說明本文在引進(jìn)Canopy聚類后。大大減少了每次迭代中的計(jì)算量，降低了運(yùn)行時(shí)間。

5 結(jié)束語

針對(duì)大規(guī)模數(shù)據(jù)聚類的問題。本文提出了基于Map Reduce的并行化Canopy-Kmeans算法。對(duì)Kmeans聚類算法的優(yōu)化確實(shí)避免了傳統(tǒng)Kmeans算法的缺陷，明顯降低時(shí)間復(fù)雜度，減少了計(jì)算量，提高聚類效率。MapReduce是目前主流的并行編程模型，但該模型本身存在一些局限性。最新的并行計(jì)算框架Prlter，Spark等對(duì)MapReduce進(jìn)行了改進(jìn)，怎么在最新的并行計(jì)算框架上對(duì)算法進(jìn)行并行化設(shè)計(jì)和實(shí)現(xiàn)需要做進(jìn)一步的實(shí)踐。

參考文獻(xiàn)：

[1]陸嘉恒.Hadoop實(shí)戰(zhàn)[M].北京：機(jī)械工業(yè)出版社，2012.

[2]李應(yīng)安.基于MapReduce聚類算法的并行化研究[D].中山大學(xué)，2010.

[3]張石磊，武裝.一種基于Hadoop云計(jì)算平臺(tái)的聚類算法優(yōu)化的研究[J].計(jì)算機(jī)科學(xué)，2012（10）：114-118.

[4]賴玉霞，劉建平.K-means算法的初始聚類中心的優(yōu)化[J].計(jì)算機(jī)工程應(yīng)用，2008（10）：147-149.

作者簡(jiǎn)介：崔莉霞（1989-），女，甘肅會(huì)寧人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、并行分布式計(jì)算。

作者單位：江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，南昌 330022