k_means聚类算法的MapReduce并行化实现_图文

1、第39卷增刊2011年6月华中科技大学学报(自然科学版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 .基金项目中央高校基本科研业务费专项资金资助项目(C Z Y 11002;武汉市科技攻关项目(201110821229;华中科技

2、大学暨湖北省移动通信公司T D -S C D MA 联合创新实验室创新基金资助项目.k -m e a n s 聚类算法的M a pR e d u c e 并行化实现江小平1李成华1向文2张新访2颜海涛3(1中南民族大学电子信息工程学院,湖北武汉430074;2华中科技大学计算机科学与技术学院,湖北武汉430074;3中国移动通信集团湖北有限公司业务支撑中心,湖北武汉430040摘要针对k -m e a n s 聚类算法特点,给出了M a p R e d u c e 编程模型实现k -m e a n s 聚类算法的方法,M a p 函数完成每个记录到聚类中心距离的计算并重新标记其属于的新聚类类别

3、,R e d u c e 函数根据M a p 函数得到的中间结果计算出新的聚类中心,供下一轮M a p R e d u c e J o b 使用.实验结果表明:k -m e a n s 算法M a pR e d u c e 并行化后部署在H a d o o p 集群上运行,具有较好的加速比和良好的扩展性.关键词云计算;并行计算;M a pR e d u c e 模型;数据挖掘;k -m e a n s 聚类算法中图分类号T P 301文献标志码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 随着信息技术的进步以及信息化社会的发

10、展,聚类计算任务所面临的数据规模越来越大,k -m e a n s 算法是一种常用的数据挖掘算法,其串行计算方法的时间复杂度比较高,处理能力存在局限性.传统高性能计算中的并行编程模型(如P T h r e a d ,M P I 和O pe n M P 等抽象度不高,开发人员需要熟悉底层的配置和并行实现细节.M a p R e d u c e 模型1是G o o gl e 实验室提出的分布式并行编程模型或框架,它能组织集群来处理大规模数据集,成为云计算平台主流的并行数据处理模型.A p a c h e 开源社区的H a d o o p 项目2用j a v a 语言实现了该模型,同时H a d o

11、 o p 项目还设计了开放源代码的云计算技术平台.云计算技术国内已有研究3-4,文献5则对在多核集群上以M a p R e d u c e 的方式实现机器学习算法进行了研究.本文在基于H a d o o p 技术的云计算基础平台上,研究了k -m e a n s 聚类算法的M a p R e d u c e 并行编程实现方法,并进行了相关实验.1M a p R e d u c e编程模型M a p R e d u c e编程模型的基本思路:将大数据集分解为成百上千的小数据集s p l i t s,每个(或若干个数据集分别由集群中的1个节点(一般就是一台普通的计算机并行执行M a p计算任务(指

12、定了映射规则并生成中间结果,然后这些中间结 果又由大量的节点并行执行R e d u c e计算任务(指定了归约规则,形成最终结果.图1描述了M a p R e d u c e的运行机制.在数据输入阶段, J o b T r a c k e r获得待计算数据片在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运算任务并生成中间结果;S h u f f l e阶段完成中间计算结果的混排交换; 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任务;R e d u c e任务完成后通知J o b T r a c k e r与N a m e-N o d e以产生最后的输出结果. 的相关计算.这样k -m e a n s 聚类算法中原来由1个主机处理的最耗时的运算(即n k t 次距离计算,将分散到多个节点并行处理,如果每个节点平均完成P 个M a p 任务,那么其时间复杂度为n k t O /P .3实验和结果分析3.1实验环境图5给出实验中云计算平台的结构:1台机器作为N a m e N o d e 和J o b T r a c k e r 服务节点,其他10台机器作为D a t e N o d e 和T a s

14、 k T r a c k e r 服务节点.每台节点硬件配置如下:C P U 型号为I n t e lX e o n X 3330;内存为8G B ;硬盘为2T B S A T A ;板载I n t e l 双千兆网络控制器.根据H a d o o p 项目官方网站介绍的方法配置基于H a d o o p .s 126870.20508988253700.4101621963161001.23048461154470493.691441351535507293.98143报告内存不足1786784116.15240报告内存不足2233.3集群加速比性能实验实验目的:加速比是衡量一个系统在扩展性

15、方面优劣的主要指标,主要考察2个方面的性能,一是当计算硬件资源增加时,对于相同规模的作业,系统的处理能力;二是当计算资源和处理作业的规模保持相近比例增长时,系统的处理能力.实验数据:利用k -m e a n s 聚类算法的M a p-R e d u c e 实现方法对移动用户数据进行聚类实验,以得到不同特征的客户群组.实验分别采用3组用户数据集,如表2所示,每条记录由35维数值型的数据组成,要求生成5个聚类类别,初始聚类中心随机产生.表2实验数据集情况数据集原始文件大小/M B 记录数/106数据块数占用H D F S 空间/M B A 2008.235.1840677814976B 4048.7410.36971516231104C 8021.612.04933231360096实