k-means算法的并行化解析.docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《k-means算法的并行化解析.docx》由会员分享,可在线阅读,更多相关《k-means算法的并行化解析.docx(20页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- means 算法 并行 化解
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内