k_means聚類算法的MapReduce并行化實現(xiàn)_圖文

1、第39卷增刊2011年6月華中科技大學(xué)學(xué)報(自然科學(xué)版J .H u a z h o n g U n i v .o f S c i .&T e c h .(N a t u r a l S c i e n c e E d i t i o n V o l .39S u p .J u n .2011收稿日期2011-03-15.作者簡介江小平(1974-,男,博士,E -m a i l :j i a n g x pm a i l .s c u e c .e d u .c n .基金項目中央高校基本科研業(yè)務(wù)費專項資金資助項目(C Z Y 11002;武漢市科技攻關(guān)項目(201110821229;華中科技

2、大學(xué)暨湖北省移動通信公司T D -S C D MA 聯(lián)合創(chuàng)新實驗室創(chuàng)新基金資助項目.k -m e a n s 聚類算法的M a pR e d u c e 并行化實現(xiàn)江小平1李成華1向文2張新訪2顏海濤3(1中南民族大學(xué)電子信息工程學(xué)院,湖北武漢430074;2華中科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院,湖北武漢430074;3中國移動通信集團湖北有限公司業(yè)務(wù)支撐中心,湖北武漢430040摘要針對k -m e a n s 聚類算法特點,給出了M a p R e d u c e 編程模型實現(xiàn)k -m e a n s 聚類算法的方法,M a p 函數(shù)完成每個記錄到聚類中心距離的計算并重新標(biāo)記其屬于的新聚類類別

3、,R e d u c e 函數(shù)根據(jù)M a p 函數(shù)得到的中間結(jié)果計算出新的聚類中心,供下一輪M a p R e d u c e J o b 使用.實驗結(jié)果表明:k -m e a n s 算法M a pR e d u c e 并行化后部署在H a d o o p 集群上運行,具有較好的加速比和良好的擴展性.關(guān)鍵詞云計算;并行計算;M a pR e d u c e 模型;數(shù)據(jù)挖掘;k -m e a n s 聚類算法中圖分類號T P 301文獻標(biāo)志碼A 文章編號1671-4512(2011S 1-0120-05P a r a l l e l i m p l e m e n t i n g k -m

4、e a n s c l u s t e r i n g a l g o r i t h m u s i n g M a p R e d u c e p r o g r a m m i n g m o d e J i a n g X i a o p i n g 1L i C h e n g h u a 1X i a n g W e n 2Z h a n g X i n f a n g 2Y a n H a i t a o 3(1C o l l e g e o f E l e c t r o n i c s a n d I n f o r m a t i o n E n g i n e e r i

5、 n g ,S o u t h -C e n t r a l U n i v e r s i t y f o r N a t i o n a l i t i e s ,W u h a n 430074,C h i n a ;2S c h o o l o f C o m p u t e r S c i e n c e a n d T e c h n o l og y ,H u a zh o n g U ni v e r s i t yo f S c i e n c e a n d T e c h n o l o g y ,W u h a n 430074,C h i n a ;3B u s i

6、n e s s S u p p o r t C e n t e r ,C h i n a M o b i l e G r o u p H u b e i C o .L t d .,W u h a n 430040,C h i n a A b s t r a c t H o w t o i m p l e m e n t t h e k -m e a n s c l u s t e r i n g a l g o r i t h m u s i n g M a p R e d u c e p r o g r a m m i n g m o d e w a s s t u d i e d .T h

7、 e d i s t a n c e b e t w e e n e a c h po i n t a n d e a c h c l u s t e r w a s c a l c u l a t e d a n d n e w c e n t e r I D w a s a s s i g n e d t o e a c h p o i n t i n t h e M a p f u n c t i o n .A l l t h e p o i n t s o f t h e s a m e k e y v a l u e (c u r r e n t c l u s t e r I D

8、w e r e s e n t t o a s i n g l e r e d u c e r a n d g e t t h e n e w c l u s t e r c e n t r o i d s f o r t h e n e x t M a pR e d u c e J o b .T h e e x -p e r i m e n t s o n t h e H a d o o p p l a t f o r m s h o w n s b a s i c a l l y l i n e a r s p e e d u p w i t h a n i n c r e a s i n

9、 g n u m b e r o f n o d e c o m p u t e r s a n d g o o d s c a l a b i l i t y.K e y w o r d s c l o u d c o m p u t i n g ;p a r a l l e l c o m p u t i n g ;M a p R e d u c e p r o g r a m m i n g m o d e ;d a t a m i n i n g ;k -m e a n s c l u s t e r i n g a l g o r i t h m 隨著信息技術(shù)的進步以及信息化社會的發(fā)

10、展,聚類計算任務(wù)所面臨的數(shù)據(jù)規(guī)模越來越大,k -m e a n s 算法是一種常用的數(shù)據(jù)挖掘算法,其串行計算方法的時間復(fù)雜度比較高,處理能力存在局限性.傳統(tǒng)高性能計算中的并行編程模型(如P T h r e a d ,M P I 和O pe n M P 等抽象度不高,開發(fā)人員需要熟悉底層的配置和并行實現(xiàn)細節(jié).M a p R e d u c e 模型1是G o o gl e 實驗室提出的分布式并行編程模型或框架,它能組織集群來處理大規(guī)模數(shù)據(jù)集,成為云計算平臺主流的并行數(shù)據(jù)處理模型.A p a c h e 開源社區(qū)的H a d o o p 項目2用j a v a 語言實現(xiàn)了該模型,同時H a d o

11、 o p 項目還設(shè)計了開放源代碼的云計算技術(shù)平臺.云計算技術(shù)國內(nèi)已有研究3-4,文獻5則對在多核集群上以M a p R e d u c e 的方式實現(xiàn)機器學(xué)習(xí)算法進行了研究.本文在基于H a d o o p 技術(shù)的云計算基礎(chǔ)平臺上,研究了k -m e a n s 聚類算法的M a p R e d u c e 并行編程實現(xiàn)方法,并進行了相關(guān)實驗.1M a p R e d u c e編程模型M a p R e d u c e編程模型的基本思路:將大數(shù)據(jù)集分解為成百上千的小數(shù)據(jù)集s p l i t s,每個(或若干個數(shù)據(jù)集分別由集群中的1個節(jié)點(一般就是一臺普通的計算機并行執(zhí)行M a p計算任務(wù)(指

12、定了映射規(guī)則并生成中間結(jié)果,然后這些中間結(jié) 果又由大量的節(jié)點并行執(zhí)行R e d u c e計算任務(wù)(指定了歸約規(guī)則,形成最終結(jié)果.圖1描述了M a p R e d u c e的運行機制.在數(shù)據(jù)輸入階段, J o b T r a c k e r獲得待計算數(shù)據(jù)片在N a m e N o d e上的存儲元信息;在M a p階段,J o b T r a c k e r指派多個T a s k T r a c k e r完成M a p運算任務(wù)并生成中間結(jié)果;S h u f f l e階段完成中間計算結(jié)果的混排交換; J o b T r a c k e r指派T a s k T r a c k e r完成R

13、 e d u c e任務(wù);R e d u c e任務(wù)完成后通知J o b T r a c k e r與N a m e-N o d e以產(chǎn)生最后的輸出結(jié)果. 的相關(guān)計算.這樣k -m e a n s 聚類算法中原來由1個主機處理的最耗時的運算(即n k t 次距離計算,將分散到多個節(jié)點并行處理,如果每個節(jié)點平均完成P 個M a p 任務(wù),那么其時間復(fù)雜度為n k t O /P .3實驗和結(jié)果分析3.1實驗環(huán)境圖5給出實驗中云計算平臺的結(jié)構(gòu):1臺機器作為N a m e N o d e 和J o b T r a c k e r 服務(wù)節(jié)點,其他10臺機器作為D a t e N o d e 和T a s

14、 k T r a c k e r 服務(wù)節(jié)點.每臺節(jié)點硬件配置如下:C P U 型號為I n t e lX e o n X 3330;內(nèi)存為8G B ;硬盤為2T B S A T A ;板載I n t e l 雙千兆網(wǎng)絡(luò)控制器.根據(jù)H a d o o p 項目官方網(wǎng)站介紹的方法配置基于H a d o o p .s 126870.20508988253700.4101621963161001.23048461154470493.691441351535507293.98143報告內(nèi)存不足1786784116.15240報告內(nèi)存不足2233.3集群加速比性能實驗實驗?zāi)康?加速比是衡量一個系統(tǒng)在擴展性

15、方面優(yōu)劣的主要指標(biāo),主要考察2個方面的性能,一是當(dāng)計算硬件資源增加時,對于相同規(guī)模的作業(yè),系統(tǒng)的處理能力;二是當(dāng)計算資源和處理作業(yè)的規(guī)模保持相近比例增長時,系統(tǒng)的處理能力.實驗數(shù)據(jù):利用k -m e a n s 聚類算法的M a p-R e d u c e 實現(xiàn)方法對移動用戶數(shù)據(jù)進行聚類實驗,以得到不同特征的客戶群組.實驗分別采用3組用戶數(shù)據(jù)集,如表2所示,每條記錄由35維數(shù)值型的數(shù)據(jù)組成,要求生成5個聚類類別,初始聚類中心隨機產(chǎn)生.表2實驗數(shù)據(jù)集情況數(shù)據(jù)集原始文件大小/M B 記錄數(shù)/106數(shù)據(jù)塊數(shù)占用H D F S 空間/M B A 2008.235.1840677814976B 4048.7410.36971516231104C 8021.612.04933231360096實