数据挖掘基础算法在MapReduce中的实现

鸣谢：本课程得到Google公司(北京）中国大学合作部精品课程计划资助9.1数据挖掘并行算法研究的重要性9.2基于MapReduce的K-Means聚类算法9.3基于MapReduce的分类算法9.4基于MapReduce的频繁项集挖掘算法数据挖掘是通过对大规模观测数据集的分析，寻找隐藏在这些数据集中的有用信息和事实的过程。数据挖掘的特征之一：海量数据Smalldatadoesnotrequiredatamining,largedatacausesproblems——摘自黎铭的《数据挖掘》课件研究发现大数据隐含着更为准确的事实因此海量数据挖掘是并行计算中值得研究的一个领域2001年微软研究院的BankoandBrill*等研究发现数据越大，机器学习的精度越高；当数据不断增长时，不同算法的分类精度趋向于相同！*M.BankoandE.Brili(2001).Scalingtoveryverylargecorporafornaturallanguagedisambiguation.ACL2001研究发现大数据隐含着更为准确的事实研究发现大数据隐含着更为准确的事实2007年Google公司Brants等基于MapReduce研究了一个2万亿单词训练数据集的语言模型，发现大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果*T.Brants,A.C.Popat,etal.LargeLanguageModelsinMachineTranslation.InEMNLP-CoNLL2007-Proceedingsofthe2007JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning9.1数据挖掘并行算法研究的重要性9.2基于MapReduce的K-Means聚类算法9.3基于MapReduce的分类算法9.4基于MapReduce的频繁项集挖掘算法9.2基于MapReduce的K-Means聚类算法1.K-Means聚类算法介绍2.基于MapReduce的K-Means并行算法设计3.实验结果与小结4.聚类算法应用实例定义：将给定的多个对象分成若干组，组内的各个对象是相似的，组间的对象是不相似的。进行划分的过程就是聚类过程，划分后的组称为簇(cluster)。几种聚类方法：基于划分的方法；基于层次的方法；基于密度的方法；......数据点的数值类型数据点的类型可分为：欧氏（Euclidean）非欧这二者在数据的表示以及处理上有较大的不同：怎样来表示cluster？怎样来计算相似度Cluster的表示欧氏空间：取各个数据点的平均值（centroid）非欧空间取某个处于最中间的点取若干个最具代表性的点（clustroid）......相似度(距离)的计算欧氏空间：可以有较为简单的方法非欧氏空间：通常不能直接进行简单的数字计算Jaccard距离:1-|S∩T|/|S∪T|Cosine距离：两个向量的夹角大小Edit距离：适合于string类型的数据基于划分(Partitioning)的聚类方法给定N个对象，构造K个分组，每个分组就代表一个聚类。K个分组满足以下条件：每个分组至少包含一个对象；每个对象属于且仅属于一个分组；K-Means算法是最常见和典型的基于划分的聚类方法K-Means算法输入：待聚类的N个数据点，期望生成的聚类的个数K输出：K个聚类算法描述:选出K个点作为初始的clustercenterLoop:对输入中的每一个点p：｛计算p到各个cluster的距离；将p归入最近的cluster;｝重新计算各个cluster的中心如果不满足停止条件，gotoLoop;否则，停止初始数据K=2选择初始中心----------------------------------------------------------------------------------------------第1次聚类：计算距离++过程示例第1次聚类：归类各点-----------------------------------------------重新计算聚类中心++过程示例(cont.)第2次聚类：计算距离-----------------------------------------------第2次聚类：归类各点++++聚类无变化，迭代终止过程示例(Cont.)第i轮迭代：生成新的clusters，并计算clustercenters第i+1轮迭代：根据第i轮迭代中生成的clusters和计算出的clustercenters，进行新一轮的聚类如此不断迭代直到满足终止条件K-Means是个不断迭代的过程对初始clustercenters的选取会影响到最终的聚类结果由此带来的结果是：能得到局部最优解，不保证得到全局最优解相似度计算和比较时的计算量较大K-Means算法的局限性如果样本数据有n个，预期生成k个cluster，则K-Means算法t次迭代过程的时间复杂度为O(nkt)，需要计算ntk次相似度如果能够将各个点到clustercenter相似度的计算工作分摊到不同的机器上并行地计算，则能够大幅提高计算速度本课将介绍利用MapReduce来将K-Means聚类过程并行化K-Means计算性能的瓶颈在进行K-Means聚类中，在处理每一个数据点时只需要知道各个cluster的中心信息不需要知道关于其他数据点的任何信息所以，如果涉及到全局信息，只需要知道关于各个clustercenter的信息即可考虑数据相关度将所有的数据分布到不同的MapReduce节点上，每个节点只对自己的数据进行计算每个Map节点能够读取上一次迭代生成的clustercenters，并判断自己的各个数据点应该属于哪一个clusterReduce节点综合每个属于每个cluster的数据点，计算出新的clustercentersMapReduce并行化聚类算法设计思路需要全局共享的数据每一个节点需要访问如下的全局文件当前的迭代计数K个表示不同聚类中心的如下的数据结构clusteridclustercenter属于该clustercenter的数据点的个数这是唯一的全局文件原始数据点数据文件Mapper1Mapper2Mapper3聚类中心信息ShuffleandSortReducer1Reducer2Map阶段的处理在Map类的初始化方法setup中读取全局的聚类中心信息对Map方法收到的每一个数据点p，计算p与所有聚类中心间的距离，并选择一个距离最小的中心作为p所属的聚类，输出ClusterID,(p,1)键值对对每个Map节点上即将传递到Reduce节点的每一个ClusterID,(p,1)键值对，用Combiner进行数据优化，合并相同ClusterID下的所有数据点并求取这些点的均值pm以及数据点个数nMap阶段的处理Mapper伪代码classMappersetup(…){读出全局的聚类中心数据Centers}map(key,p)//p为一个数据点{minDis=Double.MAXVALUE;index=-1;fori=0toCenters.length{dis=ComputeDist(p,Centers[i]);ifdisminDis{minDis=dis;index=i;}}emit(Centers[i].ClusterID,(p,1));}Map阶段的处理Combiner伪代码classCombinerreduce(ClusterID,[(p1,1),(p2,1),…]){pm=0.0；n=数据点列表[(p1,1),(p2,1),…]中数据点的总个数;fori=0tonpm+=p[i];pm=pm/n;//求得这些数据点的平均值emit(ClusterID,(pm,n));}思考题：在map中，最后一行emit(Centers[i].ClusterID,(p,1))语句中，为什么输出值必须是（p,1)而不能是p？如果写成p会带来什么问题？Reduce阶段的处理经过Map和Combine后从Map节点输出的所有ClusterID相同的中间结果ClusterID,[(pm1,n1),(pm2,n3)…],计算新的均值pm，输出ClusterID,pm所有输出的ClusterID,(pm,n)形成新的聚类中心，供下一次迭代计算思考题答案：用不用Combiner仅仅会影响性能，不能改变计算结果。因此，Combiner输出时不允许改变Map输出键值对中Value的格式和类型，否则会出错Reduce阶段的处理Reducer伪代码classReducerreduce(ClusterID,value=[(pm1,n1),(pm2,n2)…]){pm=0.0；n=0;k=数据点列表中数据项的总个数;fori=0tok{pm+=pm[i]*n[i];n+=n[i];}pm=pm/n;//求得所有属于ClusterID的数据点的均值emit(ClusterID,(pm,n));//输出新的聚类中心的数据值}令k=2，欲生成cluster-0和cluster-1随机选取A(1,1)作为cluster-0的中心，C(4,3)作为cluster-1的中心假定将所有数据分布到2个节点node-0和node-1上,即node-0：A(1,1)和C(4,3)node-1：B(2,1)和D(5,4)MapReduceK-Means聚类处理示例在开始之前，首先创建一个如前所述的全局文件MapReduceK-Means聚类处理示例Map阶段每个节点读取全局文件，以获得上一轮迭代生成的clustercenters等信息计算本节点上的每一个点到各个clustercenter的距离，选择距离最近的cluster为每一个数据点，emitclusterassignedto,数据点自身MapReduceK-Means聚类处理示例Map阶段计算各个数据点到各个cluster的距离，假定是如下的结果Node-0Node-1node-0输出：cluster-0,A(1,1)cluster-1,C(4,3)node-1输出：cluster-1,B(2,1)cluster-1,D(5,4)MapReduceK-Means聚类处理示例Map阶段的Combine处理利用combiner合并map阶段产生的大量的ClusterID相同的键值对ClusterID,pCombiner计算要emit的所有数据点的均值，以及这些数据点的个数然后，为每一个cluster发射新的键值对ClusterID,(pm,n)MapReduceK-Means聚类处理示例Map阶段的Combine处理Map的输出（即Combiner的输入）：Combiner的输出key-ClusterIDvalue-ClusterID,(pm,n)node-0发射：cluster-0,[(1,1),1]cluster-1,[(4,3),1]node-1发射：cluster-1,[(3.5,2.5),2]MapReduceK-Means聚类处理示例node-0输出：cluster-0,A(1,1)cluster-1,C(4,3)node-1输出：cluster-1,B(2,1)cluster-1,D(5,4)Reduce阶段由于map阶段emit的key是clusterID，所以每个cluster的全部数据将被发送同一个reducer，包括：该cluster的ID该cluster的数据点的均值，及对应于该均值的数据点的个数然后经计算后输出当前的迭代计数ClusterID