《k-means算法的并行化解析.docx》由会员分享，可在线阅读，更多相关《k-means算法的并行化解析.docx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、题 目：一种基于“云”计算平台的并行聚类K-means算法设计与实现陈涛一种基于“云”计算平台的并行聚类一K-means算法设计与实现中心所代表的）聚类。然后再计算每个所新聚类的聚类中心（该聚类中所有对象的均值）。不断重复这一过程直到标准测度函数开始收敛为止。一般都采用计算欧氏距离的方式进行计算。具体计算公式（公式3.1）如下:-X ）2+（X - X ）2+（X - X ）2J2i3 j3in jn公式3.1欧氏距离计算公式K-means算法优点是可以处理大数据集,K-means算法是相对可伸缩的和高效率的,因为它的计算复杂度为O（nkt）,其中n为对象个数,k为聚类个数为迭代次数,通常有t
2、n,kn,因此它的复杂度通常也用0（n）表示。下面以一组二维数据为例，简要说明K-means的聚类过程。表3.1二维数据X71015X81116X9156X10165xn空间分布图如图3.2所示20To151413121110o01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20图3.2数据分布输入 k=3,k|=x1,k2=x2Jk3=x3O算法初始分别选定前三个数据作为初始聚类中心，进行一次迭代后的聚类如图3.3所24_5_6_7._8_9_143_L1_12 13 1J 1图3.3 一次迭代经过反复迭代后，最后的最佳聚类结果如图3.4所示
3、。图3.4聚类结果此外K-means算法不依赖于顺序,给定一个初始类分布，无论样本点的顺序如何，生成 的数据分类都一样。基于大规模的数据运算，显然单个计算机上面的K-means已经远远不能满足数据聚 类的处理，不断的迭代对运算时间造成考验，本文就K-means进行并行化，使得运算时间大 大降低，下面就K-means进行做出论述。4. K-means聚类算法并行原理分析4. 1 K-means聚类算法并行原理分析文献2对K-means进行改进，提出了分布式聚类算法DK-means,该算法可以作为 K-means聚类算法的并行实现。该算法设分布式系统中有p个站点，从中任意选定一个站 点Sm为主站点
4、，其余p-1个站点为从站点。首先在主站点随机产生k个聚簇中心帆,Ck 作为全局初始聚簇中心,并将其广播给所有从站点；各站点根据这些中心确认本站数据对 象所属聚簇，并通过公式4.1得到局部聚簇中心，同时,从站点将本站点的局部聚簇中心点 及相应簇的数据对象总数(c , n c , n ) (1 WWp)传送给主站点；主站点根据这 i1 i1ik ik些聚簇信息计算全局聚簇中心。n xc +n xc + + n xc - . . xC 二一MU24Pjw-,(1 j k)jn + n + + n1j 2jpj公式4.1计算局部聚簇中心迭代这一过程，直到全局判别函数E值稳定，也即全局聚簇中心稳定。算法
5、DK-means 在聚类过程中站点间不需要传送大量的数据对象，只需要传送聚簇中心点以及该簇的数 据对象总数,通信量很小,因此算法DK-means的效率很高。定理分布式聚类算法DK-means的聚类结果等同于利用K-means算法对分布式数 据进行集中聚类的结果。证明：分布式环境下执行DK-means算法，每个站点都划分为k个簇，中心点分别为c，c ，其中，1 WWp,ciky nijy叫y,1jk, n是簇w,中数据对象总数。则全局聚 ijJ簇中心点+ n xcPiPi1jij n2jy + n x2j1 j y外n +n +Zy+Zy+ 1：ryVuWVuW_ r IJ rPJ -n + n
6、 + + n1j 2jpj+ n pj1-y + + nna n=?jr pj 丫叫+npi利用算法K-means对分布式数据进行集中聚类得到k个聚簇，则聚簇中心点c (1 Ws sk)：1 y 1c = 乙 y =s n n + n + + n s yeWc 1s 2s(y+Ey+ +Zy)ps Byy=w2 sywWps故 C = C , j s定理得证。证毕。4. 2算法描述算法DK-means具体描述如下所示。算法分布式聚类算法K-DMeans输入：局部数据集DB，DB2，.,DBp,聚簇的个数k。输出：k个聚簇。步骤：master site Sm： broadcast (c , c,
7、c);/*主站点随机产生k个初始聚簇中心并m12 k广播*/while c，c is not stable do/*当未得到稳定的全局聚簇中心*/1kfor each slave site SJ 1 i . .C=T_W-；/*王站点计算 k个全局聚掇中心*/j n +n + +n1j 2jpj陈涛一种基于“云”计算平台的并行聚类一K-means算法设计与实现broadcast ( c , c，c );/*向从站点广播全局聚簇中心*/12 k)4. 4算法复杂度分析对于任何并行和分布式的聚类算法都有两个方面的复杂度，即时间复杂度和通 信复杂度Tcommo在计算过程中，主要的计算步骤是计算每一个
8、数据点相应中心矢量的距 离；在通信过程中中，需要从一个站点到其他站点传送数据，中心矢量和其他一些相关的 信息。首先分析分布式聚类算法在1次重复步骤中的复杂度。设Tdata为一个数据项的实 际通行时间；Tstart为建立连接所需要的时间。由于是并行执行,只需要传送一次数据，因 此没步的复杂度为：time- start-* data相似的，计算距离的复杂度为：式中：Tdist是计算1个单一数据点距离的时间；n=N/Po现在设T为K-means算法 所需的循环次数，则整个算法的复杂度为Ttime=T Tstart+KTdataT rinT- comm dist由于网络发达，简历连接的时间可以忽略不计
9、。因此，本文的算法的复杂度表达式可 以写成一下形式：TA； I I Zc+c, III -J- X Otime data5 comm dist5基于Mapreduce的K-means并行算法的具体实现思想根据K-means聚类算法并行原理分析将所有的数据分布到不同的node上，每个 node只对自己的数据进行计算。每个node能够读取上一次迭代生成的cluster centers, 并计算自己的各个数据点应该属于哪一个clustero每个node在一次迭代中根据自己的 数据点计算新的cluster centerso综合每个节点计算出的cluster centers,计算出最终的实际cluste
10、r centerso 每一个节点需要访问如下的全局文件,这是唯一的全局文件。A当前的迭代计数。A cluster idoA cluster centeroA属于该cluster center的数据点的个数。本文以表3.1里数据为例，将数据分别上传都两个DataNode上,数据分配如表5.1。表5.1 A node-0数据节点数据分配0X.XcXcx.123456X1223910y22531413表5.2B node-1数据节点数据分配X7XqXmX 11X1011151616y1516658若k=3；在开始之前，首先创建一个如前所述的全局文件，选取(l,2),x (2,2),x (2, 5)作
11、为中心点。全局文件如表5.3：表5.3初始化后的全局文件0迭代次数Cluster idcluster 中心cluster-0cluster-1(1,2)1 (2, 2)# of data points assigned0cluster-22X：, (2, 5)Map阶段：每个节点读取全局文件，以获得上一轮迭代生成的cluster centers等信 息，计算自己的每一个数据点到各个cluster center的距离为每一个数据 点,emitcluster assigned to ,数据点.由表5. 1中数据根据欧氏距离计算公式计 算每个节点上的数据与中心点的距离,现以第一次迭代为例得到数据如表
12、5. 4.表5.4 Map第一次迭代计算中心点结果区所属节点数据点到各个cluster的距离比较Assigned tocluster-0cluster-1cluster-2node-0node-0x iX2X3X 4X5X6X7X8X9X10X H-近 近 近 近 近 近 近 近 近cluster-0cluster-1cluster-2cluster-2cluster-2cluster-2cluster-2cluster-2cluster-2cluster-2cluster-2Combine阶段：利用combiner减少map阶段emit的大量数据。Combiner计算每一个cluster的c
13、enter,以及属于该cluster的数据点的个数。然后，为每一个cluster 发射 key-value pair。key - cluster id,value - # of data points of this cluster ,average value node-0 发射: cluster-0, cluster-l, cluster-2, node-1 发射: 1, (2, 2) 4, (6, 8.75) 5, (13.6, 10) Reduce阶段：每个reduce收到关于某一个cluster的信息,包括：该cluster的 id以及该cluster的数据点的均值及对应于该均值的数
14、据点的个数。然后输出当前的迭 代计数、cluster id、cluster center （即均值）、属于该 cluster center 的数据 点的个数。现以第一次迭代为例:Reducer-0：Reducer-1：Reducer-2：4, (6, 8. 75) 5, (13.6, 10) cluster-2, 并行计算(Parallel Computing)和网格计算(Grid Computing)的发展，云计 算是一种新兴的分布式并行计算环境或模式，云计算的出现使得数据挖掘 技术的网络化和服务化将成为新的趋势。本文是对并行聚类算法K-means的研究。首先介绍了 K-means算法在 单
15、个计算机上的聚类算法的设计思想，其次重点对K-means算法在集群环境 下聚类算法的设计思想进行具体阐述。K-means聚类算法在面对海量数据 时,时间和空间的复杂性已成为K-means聚类算法的瓶颈。本文在充分研究 传统K-Means聚类算法的基础上，提出了基于的并行K-Means聚类算法的 设计思想，给出了其加速比估算公式。并通过实验证明了该算法的正确性 和有效性。关键字：K-means；并行；聚类；集群环境致 谢在论文完成之际,我要特别感谢我的指导老师黄萍老师的热情关怀和悉心指导。也感 谢我的班主任马慧芳老师给我论文的认真指导。在我撰写论文的过程中，黄萍老师和马慧 芳都倾注了大量的心血和
16、汗水,无论是在论文的选题、构思和资料的收集方面，还是在论 文的研究方法以及成文定稿方面,我都得到了老师们悉心细致的教诲和无私的帮助，特别 是她们广博的学识、深厚的学术素养、严谨的治学精神和一丝不苟的工作作风使我终生 受益，在此表示真诚地感谢和深深的谢意。在论文的写作过程中，也得到了许多同学的宝贵建议，同时还到许多在工作过程中许 多同事的支持和帮助，在此一并致以诚挚的谢意。感谢所有关心、支持、帮助过我的良师益友。最后，向在百忙中抽出时间对本文进行评审并提出宝贵意见的各位老师表示衷心地 感谢！AbstractCloud Computing, which is a nascent distribut
17、ed 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 trend.The paper is a study of K-means which is among the pa
18、rallel 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 algorithms working in the clustering environment. Being confronte
19、d 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 clustering algorithms and provides its estimation formula of s
20、peed-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目录摘要Abstract II目录Ill1引言11.1 研究意义11.2 并行聚类算法国内外研究现状 12.聚类算法和Hadoop综述21. 1聚类算法简介22. 2 Hadoop 平台简介33. K-means聚类算法分析44. K-
21、means聚类算法并行原理分析74. 1 K-means聚类算法并行原理分析74. 2算法描述.84. 4算法复杂度分析|95基于Mapreduce的K-means并行算法的具体实现思想 106实验与结果13参考文献I致 谢Ill1引言1.1 研究意义数据挖掘(Data Mining),又称为数据库中的知识发现(简称KDD),是从大量的、 不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中未知的、有潜在应用价 值的信息或模式的过程。计算机技术的迅猛发展以及网络的普及,使人们有更多机会使 用便捷的方法与外界进行信息交流。可是,数据大量的涌入,增加了我们获取有用信息的 难度。如何从大量的数据
22、中获取有价值的信息，给数据挖掘系统的实现带来了难题，由于 处理这些数据的复杂度很高,系统的计算能力很难达到要求,此时传统的单机服务器所 能提供的有限计算资源往往不能满足要求,需要借助分布式计算技术来实现大规模并行 计算。聚类是数据挖掘中的一项重要技术,是分析数据并从中发现有用信息的一种有效 手段。基于“物以类聚”的思想，它将数据对象分组成为若干各类或簇，使得在同一个簇 中的对象之间具有较高的相似度,而不同簇中的对象差别很大,通过聚类,人们能够识别 密集和稀疏区域，发现全局的分布模式以及数据属性之间有趣的相互关系。K-means属于 聚类分析中一种基本的划分方法,常采用误差平方和准则函数作为聚类
23、准则。所以我们 采用基于HADOOP的分布式聚类方法，以提高聚类的执行效率。1.2 并行聚类算法国内外研究现状按照并行策略的不同，并行算法分为两类：数据并行和控制并行。数据并行首先把 整个数据集分成多个小的数据子集,然后对每个数据子集执行相同的操作或指令。而控 制并行是同时执行不同的操作或指令。从数据挖掘的观点看，数据并行在许多方面优于控制并行。第一、基于数据并行策 略的算法的执行流程和对应的串行算法相同。因此可以比较容易的实现一些串行算法的 并行版本，简化开发过程。第二、数据并行有更高的平台无关性。因为数据并行算法的 控制流仍然是并行的，因此不需要为每个并行平台设计专门的控制流。第三、基于数
24、据 并行的算法有更好的可伸缩性,适合处理大规模数据集。针对当前实际应用中海量的数据规模，国内外学者提出许多并行聚类算法。Dhillon 提出一种并行K-means算法该算法使用消息传递接口(Message Passing Interface,MPI) 进行每个处理器之间的通信。在每次迭代中，每个处理器只处理分配给其自己的那一部 分数据,处理完后各个处理器之间需要通信以便更新中心点坐标,从而进行下一次迭代。 Du等提出一种并行层次聚类算法,该算法的运行平台是一个分布式内存架构的集群,拥 有大的网路带宽和小的传输延迟。实验表明,提出的算法拥有较好的可伸缩性。Feng等 首先从理论上分析了在集群系统
25、下采用数据并行策略的并行聚类算法的相关问题，包括 加速比和通讯策略的选择,然后提出一种并行层次聚类算法。实验证明了文中的理论分 析。Olman等提出了一种并行聚类算法应用于生物信息学中的数据。在该算法中，应用 最小支撑树来求解聚类问题。Boutsinas等提出了一种聚类算法的框架,能够扩展聚类算 法的计算规模，从而解决大规模数据的聚类问题。Xu提出了一种并行DBSCAN算法，它在 由多个计算机组成的完全共享框架的网络中,采用一种称为dR*树的分布式空间索引结 构。实验表明，该算法具有近似线性的加速比。Judd等提出了三种剪枝技术并将它们集 成到并行聚类工具P-CLUSTER中，采用计算剪枝技术
26、后,P-CLUSTER的性能得到显著 提高。其他的并行聚类算法还包括Rasmussen 1989, Olson 1995, Foti 2000, Dash 2007等。尽管国内外学者提出了许多并行聚类算法，但是，之前的并行算法的设计，用户需把 很大精力用在数据划分、任务调度、负载平衡、处理器通信等工作上。对于一般用户这 些技术不易掌握,人们迫切需要一种易学易用的平台用于并行程序的设计,从而使人们 能够把更多的精力用于聚类算法本身的设计上。近几年来，云计算作为一种新兴的商业计算模型得到了人们的广泛关注。Hadoop 是一个可以更容易开发和并行处理大规模数据的云计算平台。它的主要特点是：扩容能 力
27、、成本低、高效率。可靠性等。Hadoop是一个实现了 MapReduce计算模型,借助于 MapReduce,可以轻松地编写并行程序，将其运行于计算机集群上，完成海量数据的计 算。本文对根据云计算平台下的并行数据聚类K-means算法与理论,采用误差平方和准 则函数作为聚类准则使算法简单、快速而且能够有效的处理大数据集做出详细论述。2.聚类算法和Hadoop综述2.1 聚类算法简介聚类是一个将数据集划分为着干个子集的过程,并使得同一集合内的数据对象具有 较高的相似度，而不同集合中的数据对象则是不相似的，相似或不相似的度量是基于数据 Buyya 2008, Armbrust 2009, Erdo
28、gmus 2009,郑纬民 2009 对象描述属性的取值来确定的,通常就是利用各个聚类间的距离来进行描述的。聚类分析 的基本指导思想是最大程度地实现类中对象相似度最大，类间对象相似度最小。聚类与分类不同，在分类模型中,存在样本数据，这些数据的类标号是已知的,分类的 目的是从训练样本集中提取出分类的规则，用于对其他类标号未知的对象进行类标识。在 聚类中，预先不知道目标数据的有关类的信息,需要以某种度量为标准将所有的数据对象 划分到各个簇中。因此，聚类分析又称为无监督的学习。聚类算法的目的就是获得能够反映N维空间中这些样本点的最本质的“类”的性质。 这一步没有领域专家的参与，它除了集合知识外不考虑
29、任何的领域知识，不考虑特征变量 在其领域中的特定含义，仅仅认为它是特征空间中的一维而己。聚类算法的选择取决于数据的类型、聚类的目的和应用。大体上聚类算法可以分为 如下几类：基于划分的方法(pa血ioning method)：给定要构建的划分的数目k,划分方法首先 创建一个初始划分。然后采用一种迭代的重定位技术,尝试通过对象在划分间移动来改进 划分。目前比较流行的是K-means算法,K-medoids算法两种启发式的划分方法。(2)基于层次的方法(hierarchical method)：对给定的数据对象集合进行层次的分解。 BIRCH.CUREIn和CHAMELEON等算法是层次聚类的典型。
30、(3)基于密度的方法(dens计y-based method)：基于距离的聚类方法只能发现球形的 簇，而在发现任意形状的簇上遇到了困难,为此提出了基于密度的聚类，这种方法可以用来 过滤噪声数据，发现任意形状的簇。DBSCANQPTICS和CLIQUE是其中三种有代表性 的方法。(4)基于模型的方法(modH-based method)：为每个簇假定了一个模型,寻找数据对给 定模型的最佳拟合，基于模型的算法可以通过构造反映数据点空间分布的密度函数来定 位聚类，也可以基于标准的统计数字自动决定聚类数目。(5)基于网格的方法(grid-based method)：基于网格的方法把对象空间量化为有限数
31、 目的单元，形成一个网格结构，所有的聚类操作都在这个网格结构上进行。2. 2 Hadoop平台简介Hadoop是由Apache基金会开发的分布式基础框架，用户可以在不了解分布式底层 细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。Hadoop实现了 一个分布式文件系统(Hadoop Distributed File System ),简称HDFSo HDFS有着高容错性的特点，并且设计用来部署在低廉的(low-cost)硬件上。而且它提供高传输率(high throughput)来访问应用程序的数据,适合那些有着超大数据集(large data set)的应用程 序。HDFS放
32、宽了 (relax) POSIX的要求(requirements)这样可以流的形式访问(streaming access)文件系统中的数据。Hadoop 有许多元素构成。其最底部是 Hadoop Distributed File System (HDFS), 它存储Hadoop集群中所有存储节点上的文件。HDFS的上一层MapReduce引擎, 该引擎由 JobTrackers 和 TaskTrackers 组成。MapReduce是一种高效的分布式编程模型 也是一种用于处理和生成大规模数 据集的实现方式MapReduce计算。模型各个阶段的工作流程如下：(1) Input：一个基于Hadoo
33、p平台MapReduce框架的应用通常需要一对通过实 现合适的接口或抽象类提供的Map和Reduce函数还应该指明输入、输出的位置和 其他一些运行参数此阶段还会把输入目录下的大数据文件划分为若干独立的数据 块。Map: MapReduce框架把应用的输入看作一组Key,value键值对,在Map这 个阶段，框架会调用用户自定义的Map函数，处理每个Key,value键值对，同时生成 一批新的中间Key,value键值对，这两组键值对的类型可能不同。Shuffle：为了保证Reduce的输入是Map排好序的输出，在Shuffle阶段，框架 通过HTTP为每个Reduce获得所有Map输出中与之相
34、关的Key,value键值对， M叩Redus框架按照Key值对Reduce阶段的输入进行分组，因为不同Map的输出中 可能会有相同的Key0(4)Reduce：此阶段会遍历中间数据对每一个唯一的Key执行用户自定义的 Reduce函数 输入参数是Key,list of value),输出是新的Key,value键值对。(5)Output：此阶段会把Reduce输出的结果写入到输出目录指定的位置 这样一 个典型的MapReduce过程就完成了。3 . K-means聚类算法分析MacQue既在1967年提出的K-means算法，是一种被广泛应用于科学研究和工业应 J . B . MacQuee
35、n Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, eds L. M. Le Cam & J. Neyman, 1, pp. 281 -297. Berkeley, 用中的经典聚类算法。K-means算法的核心思想是把n个数据对象划分为k个聚类，使每 个聚类中的数据点到该聚类中心的平方和最小，算法处理过程：输入：聚
36、类个数k,包含n个数据对象的数据集。输出：k个聚类。(1)从n个数据对象中任意选取k个对象作为初始的聚类中心。(2)分别计算每个对象到各个聚类中心的距离，把对象分配到距离最近的聚类中。(3)所有对象分配完成后，重新计算k个聚类的中心。(4)与前一次计算得到的k个聚类中心比较，如果聚类中心发生变化，转(2),否则转(5)。(5)输出聚类结果。K-means算法的工作流程如图3.1所示。初始化k个聚类中心分配各个数据对象到距离最近的类中重新计算各个聚类的中心不是否收敛口是输入聚类的结果结束图3.1 K-means流程图首先从n个数据对象中任意选择k个对象作为初始聚类中心;而对于所剩下的其它 对象则根据他们与这些聚类中心的相似度(距离)，分别将他们分配给与其最相似的(聚类CA: University of Ca