k―means聚类算法在mapreduce框架下的实现

《k―means聚类算法在mapreduce框架下的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、K―Means聚类算法在MapReduce框架下的实现　　摘要：MapReduce是一种编程模型，这种编程模型编程简单，不必关心底层实现细节，可用于大规模数据集的并行计算。K-Means是一种简单、基本的数据挖掘聚类方法，它将对象组织成多个互斥的组或簇。针对K-Means的特点，给出了MapReduce编程模型下K-Means的实现方法。实验结果表明，MapReduce编程模型下的K-Means算法部署在Hadoop集群上运行具有较好的性能。　　关键词：K-Means；MapReduce；数据挖掘；聚类算法　　DOIDOI：10.11907/rjdk.162043

2、　　中图分类号：TP311　　文献标识码：A文章编号：1672-7800（2016）012-0030-03　　0引言7　　伴随着计算机技术的不断进步和互联网技术在各领域的深入发展，海量数据在各行业中不断产生。由于传统的数据挖掘算法往往运行在一台普通的计算机上，但面对大量的数据尤其是海量数据时，传统的计算机在计算能力、处理速度、存储容量、带宽速度等多个方面往往表现出力不从心。面对这些问题，云计算提出使得这些问题迎刃而解。云计算是基于网络平台上的一种计算模型，可以在多台计算机上同时平行运行。它的模型可以由一系列普通计算机加上网络组成，对计算机硬件要求相对较低，但其性能

3、可达到普通计算机的若干倍以上。这种计算模型为数据挖掘领域开辟了一条新路径。　　MapReduce模型[1]是美国谷歌公司提出的一种分布式并行编程模型，其主要功能是可以利用大量计算机处理海量的数据。对于MapReduce这种编程模型，Map和Reduce是其主要思想，通过Map和Reduce，编程人员可以在不通晓分布式并行编程的情况下，将自己的程序运行在分布式系统上。通过Apache开源社区Hadoop项目[2]，程序设计人员实现了该模型，使得该模型进行分布式并行计算成为可能。　　根据文献记载，多种数据挖掘算法已经在云计算编程模型MapReduce上实现。冀素琴等[

4、3]提出了基于MapReduce的K-Means聚类集成，谢雪莲等[4]提出了基于云计算的并行K-Means聚类算法研究，黄斌等[5]提出了基于MapReduce的数据挖掘平台设计与实现，毛典辉等[6]提出了基于MapReduce的Canopy-Kmeans改进算法。本文结合各自算法的思想与MapReduce的运行机理，提出K-Means聚类算法在MapReduce框架下的实现。在MapReduce框架下，K-Means聚类算法的使用范围由单机扩展到云计算平台，在面对海量数据时，极大地减少了K-Means聚类算法的运行时间，显著地提高了运行效率。　　1MapRed

5、uce编程模型　　MapReduce编程模型采用分治法的思想，在主节点管理下，MapReduce编程模型将海量的数据分发给各分节点共同完成，各节点对中间结果进行分类、排序、整合并得到最终结果。简言之，MapReduce就是任务分解与结果汇总。　　1.1MapRedue集群结构7　　MapReduce任务需由几个部分协作完成。它主要有4个部分组成：Client客户端、JobTracker、TaskTracker以及分布式文件系统。　　1.2MapReduce执行过程　　在Hadoop中，有两个机器角色用来执行MapReduce任务，一个是JobTracker，另一个

6、是TaskTracker。JobTracker的作用是执行调度工作，在Hadoop集群中有且只有一个，TaskTracker的作用是执行任务，在Hadoop集群中有若干个。图1描述了MapReduce的运行机制，在数据输入阶段，输入文件按照一定的标准进行分片；在Map阶段，在JobTracker的统一调度下，多个TaskTracker完成Map运算任务并生成中间结果；在Shuffle阶段完成中间计算结果的排序和分类；在Reduce阶段，在JobTracker统一调度下，多个TaskTracke完成Reduce任务；Reduce任务完成后通知JobTracker以产

7、生最后的输出结果。　　2K-Means聚类算法实现　　2.1K-Means聚类算法　　K-Means算法是很典型的基于距离的聚类算法，它将对象组织成多个互斥的组或簇，一般采用欧式距离作为评价指标，即认为两个对象的距离越近，其相似度就越大。假设数据集D包含n个欧式空间中的对象。聚类的目的是将D的对象分配到k个簇C1，…，Ck中，使得对于1≤i，j≤k，Ci∈D且Ci∩Cj=￠。聚类划分以簇内高相似性和簇间低相似性为目标。　　设p是空间中的点，表示给定的数据对象；ci是簇Ci的中心，其中p和ci都是多维数据。对象p∈7Ci与该簇的代表ci之差用dist（p，ci）度量

8、，其中di