k-means算法的并行化

陈涛一种基于“云”计算平台的并行聚类—K-means算法设计与实现I题目：一种基于“云”计算平台的并行聚类——K-means算法设计与实现陈涛一种基于“云”计算平台的并行聚类—K-means算法设计与实现II摘要云计算(CloudComputing)是分布式计算(DistributedComputing)、并行计算(ParallelComputing)和网格计算(GridComputing)的发展,云计算是一种新兴的分布式并行计算环境或模式,云计算的出现使得数据挖掘技术的网络化和服务化将成为新的趋势。本文是对并行聚类算法K-means的研究。首先介绍了K-means算法在单个计算机上的聚类算法的设计思想,其次重点对K-means算法在集群环境下聚类算法的设计思想进行具体阐述。K-means聚类算法在面对海量数据时,时间和空间的复杂性已成为K-means聚类算法的瓶颈。本文在充分研究传统K-Means聚类算法的基础上,提出了基于的并行K-Means聚类算法的设计思想,给出了其加速比估算公式。并通过实验证明了该算法的正确性和有效性。关键字：K-means；并行；聚类；集群环境陈涛一种基于“云”计算平台的并行聚类—K-means算法设计与实现IIIAbstractCloudComputing,whichisanascentdistributedparallelcomputingenvironmentorpattern,isthedevelopmentofDistributedComputing,ParallelComputingandGridComputing.TheappearanceofCloudComputingmakesthenetworkandtheserviceofthedataminingtechnologybecomeanewtrend.ThepaperisastudyofK-meanswhichisamongtheparallelclusteringalgorithms.Firstly,itillustratesthedesignideologyofclusteringalgorithmofK-meansalgorithmontheeverysinglecomputer.Secondly,itmainlyelaboratesthedesignideologyofK-meansalgorithmofclusteringalgorithmsworkingintheclusteringenvironment.Beingconfrontedwithalargequantityofdata,thecomplexityoftimeandspacehasbeenthebottleneckofK-means.BasedonthesufficientstudiesoftraditionalK-means,thepaperputsforwardthedesignideologyonthebasisoftheparallelK-meansclusteringalgorithmsandprovidesitsestimationformulaofspeed-upratio.Thepaperalsoprovestheaccuracyandtheeffectivenessofthisalgorithmbythemeansoftheexperiments.KeyWords:K-means；Parallel;Clustering;Clusterenvironment陈涛一种基于“云”计算平台的并行聚类—K-means算法设计与实现IV目录摘要....................................................................................................................IIAbstract..............................................................................................................III目录.................................................................................................................IV1引言....................................................................................................................11.1研究意义..................................................................................................11.2并行聚类算法国内外研究现状..............................................................12．聚类算法和Hadoop综述...............................................................................22.1聚类算法简介.........................................................................................22.2Hadoop平台简介....................................................................................33．K-means聚类算法分析.................................................................................44．K-means聚类算法并行原理分析..................................................................74.1K-means聚类算法并行原理分析..........................................................74.2算法描述.................................................................................................94.4算法复杂度分析...................................................................................105基于Mapreduce的K-means并行算法的具体实现思想.............................106实验与结果.....................................................................................................13参考文献................................................................................................................I致谢.............................................................................................................III陈涛一种基于“云”计算平台的并行聚类—K-means算法设计与实现11引言1.1研究意义数据挖掘（DataMining）,又称为数据库中的知识发现（简称KDD）,是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中未知的、有潜在应用价值的信息或模式的过程。计算机技术的迅猛发展以及网络的普及,使人们有更多机会使用便捷的方法与外界进行信息交流。可是,数据大量的涌入,增加了我们获取有用信息的难度。如何从大量的数据中获取有价值的信息,给数据挖掘系统的实现带来了难题,由于处理这些数据的复杂度很高,系统的计算能力很难达到要求,此时传统的单机服务器所能提供的有限计算资源往往不能满足要求,需要借助分布式计算技术来实现大规模并行计算。聚类是数据挖掘中的一项重要技术,是分析数据并从中发现有用信息的一种有效手段。基于“物以类聚”的思想,它将数据对象分组成为若干各类或簇,使得在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别很大,通过聚类,人们能够识别密集和稀疏区域,发现全局的分布模式以及数据属性之间有趣的相互关系。K-means属于聚类分析中一种基本的划分方法,常采用误差平方和准则函数作为聚类准则。所以我们采用基于HADOOP的分布式聚类方法,以提高聚类的执行效率。1.2并行聚类算法国内外研究现状按照并行策略的不同,并行算法分为两类：数据并行和控制并行。数据并行首先把整个数据集分成多个小的数据子集,然后对每个数据子集执行相同的操作或指令。而控制并行是同时执行不同的操作或指令。从数据挖掘的观点看,数据并行在许多方面优于控制并行。第一、基于数据并行策略的算法的执行流程和对应的串行算法相同。因此可以比较容易的实现一些串行算法的并行版本,简化开发过程。第二、数据并行有更高的平台无关性。因为数据并行算法的控制流仍然是并行的,因此不需要为每个并行平台设计专门的控制流。第三、基于数据并行的算法有更好的可伸缩性,适合处理大规模数据集。针对当前实际应用中海量的数据规模,国内外学者提出许多并行聚类算法。Dhillon提出一种并行K-means算法,该算法使用消息传递接口（MessagePassingInterface,MPI）进行每个处理器之间的通信。在每次迭代中,每个处理器只处理分配给其自己的那一部陈涛一种基于“云”计算平台的并行聚类—K-means算法设计与实现2分数据,处理完后各个处理器之间需要通信以便更新中心点坐标,从而进行下一次迭代。Du等提出一种并行层次聚类算法,该算法的运行平台是一个分布式内存架构的集群,拥有大的网路带宽和小的传输延迟。实验表明,提出的算法拥有较好的可伸缩性。Feng等首先从理论上分析了在集群系统下采用数据并行策略的并行聚类算法的相关问题,包括加速比和通讯策略的选择,然后提出一种并行层次聚类算法。实验证明了文中的理论分析。Olman等提出了一种并行聚类算法应用于生物信息学中的数据。在该算法中,应用最小支撑树来求解聚类问题。Boutsinas等提出了一种聚类算法的框架,能够扩展聚类算法的计算规模,从而解决大规模数据的聚类问题。Xu提出了一种并行DBSCAN算法,它在由多个计算机组成的完全共享框架的网络中,采用一种称为dR*树的分布式空间索引结构。实验表明,该算法具有近似线性的加速比。Judd等提出了三种剪枝技术并将它们集成到并行聚类工具P-CLUSTER中,采用计算剪枝技术后,P-CLUSTER的性能得到显著提高。其他的并行聚类算法还包括Rasmussen1989,Olson1995,Foti2000,Dash2007等。尽管国内外学者提出了许多并行聚类算法,但是,之前的并行算法的设计,用户需把很大精力用在数据划分、任务调度、负载平衡、处理器通信等工作上。对于一般用户这些技术不易掌握,人们迫切需要一种易学易用的平台用于并行程序的设计,从而使人们能够把更多的精力用于聚类算法本身的设计上。近几年来,云计算①作为一种新兴的商