Ch9.1-基于MapReduce的K-Means聚类并行算法ppt课件.ppt

《Ch9.1-基于MapReduce的K-Means聚类并行算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ch9.1MapReduce算法设计——K-Means聚类算法南京大学计算机科学与技术系主讲人：黄宜华，肖韬2011年春季学期MapReduce海量数据并行处理鸣谢：本课程得到Google公司(北京）中国大学合作部精品课程计划资助1.为什么选择数据挖掘作为并行计算的研究点2.K-Means聚类算法介绍3.K-Means算法为什么适合使用并行方法4.基于MapReduce的K-Means并行算法5.问题讨论定义：数据挖掘是通过对大规模观测数据集的分析，寻找确信的关系，并将数据以一种可理解的、且利于使用的新颖方式概括数据的方法。数据挖掘的特征之一：海量数据——Smalldatadoesnotr

2、equiredatamining,largedatacausesproblems——以上摘自黎铭的《数据挖掘》课件可见，数据挖掘是并行计算中值得研究的一个领域定义：将给定的多个对象分成若干组，组内的各个对象是相似的，组间的对象是不相似的。进行划分的过程就是聚类过程，划分后的组称为簇（cluster）。几种聚类方法：基于划分的方法；基于层次的方法；基于密度的方法；......给定N个对象，构造K个分组，每个分组就代表一个聚类。这K个分组满足以下条件：每个分组至少包含一个对象；每个对象属于且仅属于一个分组；K-Means算法是最常见和典型的基于划分的聚类方法输入：待聚类的N个数据点，期望生成的

3、聚类的个数K输出：K个聚类----算法描述-------------------------选出K个点作为初始的clustercenterLoop:对输入中的每一个点p：｛计算p到各个cluster的距离；将p归入最近的cluster;｝重新计算各个cluster的中心如果不满足停止条件，gotoLoop;否则，停止初始数据K=2选择初始中心------------------------------------------------------------------------------------------------------------------------------

4、------------------第1次聚类：计算距离++第1次聚类：归类各点------------------------------------------------------------------------重新计算聚类中心++第2次聚类：计算距离------------------------------------------------------------------------第2次聚类：归类各点++++聚类无变化，迭代终止第i轮迭代：生成新的clusters，并计算clustercenters第i+1轮迭代：根据第i轮迭代中生成的clusters和计算出的cl

5、ustercenters，进行新一轮的聚类如此不断迭代直到满足终止条件对初始clustercenters的选取会影响到最终的聚类结果由此带来的结果是：能得到局部最优解，不保证得到全局最优解相似度计算和比较时的计算量较大如果样本数据有n个，预期生成k个cluster，则K-Means算法t次迭代过程的时间复杂度为O(nkt)，需要计算ntk次相似度如果能够将各个点到clustercenter相似度的计算工作分摊到不同的机器上并行地计算，则能够减少计算时间本课将介绍利用MapReduce来将K-Means聚类过程并行化在进行K-Means聚类中，在处理每一个数据点时只需要知道：各个cluste

6、r的中心信息不需要知道关于其他数据点的任何信息所以，如果涉及到全局信息，只需要知道关于各个clustercenter的信息即可数据点的类型可分为：欧氏（Euclidean）非欧这二者在数据的表示以及处理上有较大的不同：怎样来表示cluster？怎样来计算相似度欧氏空间：取各个数据点的平均值（centroid）非欧空间取某个处于最中间的点取若干个最具代表性的点（clustroid）......欧氏空间：可以有较为简单的方法非欧氏空间：通常不能直接进行简单的数字计算Jaccard距离:Cosine距离：两个向量的夹角大小Edit距离：适合于string类型的数据本节课只讨论欧氏空间里的K-Me

7、ans聚类方法将所有的数据分布到不同的node上，每个node只对自己的数据进行计算每个node能够读取上一次迭代生成的clustercenters，并判断自己的各个数据点应该属于哪一个cluster每个node在每次迭代中根据自己的数据点计算出相关数据综合每个节点计算出的相关数据，计算出最终的实际clustercenters每一个节点需要访问如下的全局文件当前的迭代计数K个如下结构clusteridclustercen