《k-means算法的并行化》由会员分享，可在线阅读，更多相关《k-means算法的并行化（20页珍藏版）》请在金锄头文库上搜索。
1、 毕 业 论 文题 目：一种基于“云”计算平台的并行聚类K-means 算法设计与实现 学 院： 数学与信息科学学院 专 业： 计算机科学与技术 毕业年限： 2012 年 学生姓名： 陈 涛 学 号： 200871030305 指导教师： 黄 萍 陈涛 一种基于“云”计算平台的并行聚类K-means 算法设计与实现I摘 要云计算(Cloud Computing)是分布式计算(Distributed Computing)、并行计算(Parallel Computing)和网格计算(Grid Computing)的发展,云计算是一种新兴的分布式并行计算环境或模式,云计算的出现使得数据挖掘技术的网络
2、化和服务化将成为新的趋势。本文是对并行聚类算法 K-means 的研究。首先介绍了 K-means 算法在单个计算机上的聚类算法的设计思想,其次重点对 K-means 算法在集群环境下聚类算法的设计思想进行具体阐述。 K-means 聚类算法在面对海量数据时,时间和空间的复杂性已成为 K-means 聚类算法的瓶颈。本文在充分研究传统 K-Means 聚类算法的基础上, 提出了基于的并行 K-Means 聚类算法的设计思想, 给出了其加速比估算公式。并通过实验证明了该算法的正确性和有效性。关键字：K-means；并行；聚类；集群环境陈涛 一种基于“云”计算平台的并行聚类K-means 算法设计
3、与实现IIAbstractCloud Computing, which is a nascent distributed parallel computing environment or pattern, is the development of Distributed Computing, Parallel Computing and Grid Computing. The appearance of Cloud Computing makes the network and the service of the data mining technology become a new t
4、rend.The paper is a study of K-means which is among the parallel clustering algorithms. Firstly, it illustrates the design ideology of clustering algorithm of K-means algorithm on the every single computer. Secondly, it mainly elaborates the design ideology of K-means algorithm of clustering algorit
5、hms working in the clustering environment. Being confronted with a large quantity of data, the complexity of time and space has been the bottleneck of K-means. Based on the sufficient studies of traditional K-means, the paper puts forward the design ideology on the basis of the parallel K-means clus
6、tering algorithms and provides its estimation formula of speed-up ratio. The paper also proves the accuracy and the effectiveness of this algorithm by the means of the experiments. Key Words: K-means； Parallel; Clustering; Cluster environment陈涛 一种基于“云”计算平台的并行聚类K-means 算法设计与实现III目 录摘 要 .IAbstract.II目
7、 录 .III1 引言 .11.1 研究意义 .11.2 并行聚类算法国内外研究现状 .12聚类算法和 Hadoop 综述 .22.1 聚类算法简介 .22.2 Hadoop 平台简介 .33K-means 聚类算法分析 .44K-means 聚类算法并行原理分析 .74.1 K-means 聚类算法并行原理分析 .74.2 算法描述 .84.4 算法复杂度分析 .95 基于 Mapreduce 的 K-means 并行算法的具体实现思想 .106 实验与结果 .13参考文献 .I致 谢 .III陈涛 一种基于“云”计算平台的并行聚类K-means 算法设计与实现11 引言1.1 研究意义数据
8、挖掘（Data Mining ） ,又称为数据库中的知识发现（简称 KDD）,是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中未知的、有潜在应用价值的信息或模式的过程。计算机技术的迅猛发展以及网络的普及,使人们有更多机会使用便捷的方法与外界进行信息交流。可是,数据大量的涌入,增加了我们获取有用信息的难度。如何从大量的数据中获取有价值的信息,给数据挖掘系统的实现带来了难题,由于处理这些数据的复杂度很高,系统的计算能力很难达到要求,此时传统的单机服务器所能提供的有限计算资源往往不能满足要求,需要借助分布式计算技术来实现大规模并行计算。聚类是数据挖掘中的一项重要技术,是分析数据并
9、从中发现有用信息的一种有效手段。基于“物以类聚”的思想,它将数据对象分组成为若干各类或簇,使得在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别很大,通过聚类,人们能够识别密集和稀疏区域,发现全局的分布模式以及数据属性之间有趣的相互关系。K-means 属于聚类分析中一种基本的划分方法,常采用误差平方和准则函数作为聚类准则。所以我们采用基于 HADOOP 的分布式聚类方法,以提高聚类的执行效率。1.2 并行聚类算法国内外研究现状按照并行策略的不同,并行算法分为两类：数据并行和控制并行。数据并行首先把整个数据集分成多个小的数据子集,然后对每个数据子集执行相同的操作或指令。而控制并行是同
10、时执行不同的操作或指令。从数据挖掘的观点看,数据并行在许多方面优于控制并行。第一、基于数据并行策略的算法的执行流程和对应的串行算法相同。因此可以比较容易的实现一些串行算法的并行版本,简化开发过程。第二、数据并行有更高的平台无关性。因为数据并行算法的控制流仍然是并行的,因此不需要为每个并行平台设计专门的控制流。第三、基于数据并行的算法有更好的可伸缩性,适合处理大规模数据集。针对当前实际应用中海量的数据规模,国内外学者提出许多并行聚类算法。Dhillon提出一种并行 K-means 算法 ,该算法使用消息传递接口（Message Passing Interface,MPI）进行每个处理器之间的通信。在每次迭代中,每个处理器只处理分配给陈涛 一种基于“云”计算平台的并行聚类K-means 算法设计与实现2其自己的那一部分数据,处理完后各个处理器之间需要通信以便更新中心点坐标,从而进行下一次迭代。Du 等提出一种并行层次聚类算法 ,该算法的运行平台是一个分布式内存架构的集群,拥有大的网路带宽和小的传输延迟。实验表明,提出的算法拥有较好的可伸缩性。Feng 等首先从理论上分析了在集群系统下采用数据并行策略的并行聚类算法的相关问题,包括加速比和通讯策略的选择,然后提出一种并行
