基于MapReduce的聚類算法的并行化研究.pdf

1、本文對(duì)基于MapReduce的聚類算法的并行化進(jìn)行了研究。聚類分析是數(shù)據(jù)挖掘中的重要內(nèi)容，在工業(yè)、商業(yè)和科研等領(lǐng)域發(fā)揮著越來(lái)越重要的作用，然而隨著這些領(lǐng)域中產(chǎn)生的數(shù)據(jù)量高速增長(zhǎng)，在傳統(tǒng)的計(jì)算機(jī)上對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行聚類分析需要花費(fèi)很長(zhǎng)的時(shí)間。使用并行算法可以有效的解決這一問(wèn)題。由Google提出的MapReduce并行計(jì)算模型主要是針對(duì)海量數(shù)據(jù)的處理，相對(duì)傳統(tǒng)的并行計(jì)算模型，它由底層對(duì)數(shù)據(jù)分割、任務(wù)分配、并行處理、容錯(cuò)等細(xì)節(jié)問(wèn)題進(jìn)行封裝，

2、極大的簡(jiǎn)化了并行程序設(shè)計(jì)。在使用MapReduce進(jìn)行并行計(jì)算開(kāi)發(fā)時(shí)，用戶只需集中注意力在自身要解決的并行計(jì)算任務(wù)上。k—means算法屬于聚類分析中的一種基本劃分方法，常采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則，該算法在處理數(shù)據(jù)集上相對(duì)可伸縮且高效率。但面對(duì)大規(guī)模數(shù)據(jù)集時(shí)，其在計(jì)算數(shù)據(jù)對(duì)象間的距離上遇到瓶頸。數(shù)據(jù)規(guī)模變大，則運(yùn)算次數(shù)也隨之增大，運(yùn)算的耗時(shí)加長(zhǎng)。為了突破這個(gè)瓶頸，本文使用MapReduce計(jì)算模型，在Hadoop平臺(tái)上實(shí)現(xiàn)k—

3、means算法的并行化。為了進(jìn)一步提高k—means聚類算法的效率，本文使用canopy算法對(duì)k—means算法進(jìn)行優(yōu)化，并使用MapReduce計(jì)算模型，在Hadoop平臺(tái)上實(shí)現(xiàn)了canopy—k—means算法的并行化。最后在聚類結(jié)果的有效性、加速比以及可擴(kuò)展性上對(duì)基于MapReduce的k—means并行算法和canopy—k—means并行算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，這兩種并行算法能夠得到較好的聚類結(jié)果，在大數(shù)據(jù)集上具有較好的