基于mapreduce的聚类算法研究
5星 · 超过95%的资源 需积分: 10 185 浏览量
2013-10-27
09:20:01
上传
评论
收藏 405KB DOC 举报 
基于 MapReduce 的 k-means 聚类算法探究
摘要本文针对 k-means 算法特点，在 MpaReduce 编程模型的基础上实现了 k-means 聚类算
法，Map 函数完成每个记录到聚类中心距离的计算并重新标记其属于的新聚类类别 ，
Reduce 函数根据 Map 函数得到的中间结果计算出新的聚类中心，供下一轮 MapReduce Job
使用。结果说明 k-means 算法 MapReduce 并行化后在 hadoop 集群上具有良好的加速比和
扩展性。
关键词并行计算；mapreduce；聚类；k-means
Abstract How to implement the k-means clustering algorithm using MapReduce programing
mode was studied. The distance between each point and each cluster was calculated and new
center ID was assigned to each point in the Map funcon. All the points of the same key value
were sent to a single reducer and get the new cluster centroids for the next MapReduce Job. The
experiments on the Hadoop pla$orm shows basically linear speedup with an increasing number
of node computers and good scalability.
Key wordsparallel compung; Mapreduce; clustering; k-means
Hadoop 是 Apache 软件基金会旗下的一个开源分布式计算平台。以 Hadoop 分布式文件
系统和 MapReduce 为核心的 Hadoop 为用户提供了系统底层细节透明的分布式基础架构 。
HDFS 的高容错性、高伸缩性等优点允许用户将 Hadoop 部署在低廉的硬件上，形成分布式
系统；MapReduce 分布式编程模型允许用户在不了解分布式系统底层细节的情况下开发并
行应用程序。本文在基于 Hadoop 技术的云计算基础平台上，研究了 k-means 聚类算法的
MapReduce 并行编程实现方法。
1 MapReduce 编程模型
在 Hadoop 中，每个 Mapreduce 任务都被初始化为一个 Job。每个 Job 又可以分为两个
阶段：Map 阶段和 Reduce 阶段。这两个阶段分别用两个函数来表示。即 Map 函数和
Reduce 函数。Map 函数接受一个<key,value>形式的输入，然后产生同样为<key,ualue>形式
的中间输出，Hadoop 会负责将所有具有相同中间 key 值的 value 集合到一起传给 Reduce 函
数，Reduce 函数接收一个如<key,(list of value)>形式的输入，然后对这个 value 集合进行处理
并输出结果，Reduce 的输出也是<key,value>形式的。
为了方便理解，分别将三个<key,value>对标记为<k1,v1>、<k2,v2>、<k3,v3>，那么上述
过程可以用图 1.1 表示
评论1
最新资源