基于MapReduce的K-Means并行算法设计.doc

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

1、.基于MapReduce的K-Means并行算法设计目录一、实验设计21.实验说明22.算法说明2(1).聚类2(2).基于划分的聚类方法2(3).K-Means算法2(4).MapReduce并行化聚类算法设计思路33.类说明3(1).Instance3(2).Cluster4(3).EuclideanDistance4(4).RandomClusterGenerator4(5).KMeans4(6).KmeansCluster4(7).KMeansDriver5二、实验结果说明51.实验设置52.源数据点63.聚类结果7三、性能和不足7四、源程序81.Instance

2、类82.Cluster类103.EuclideanDistance类124.PageRankDriver类125.KMeans类156.KMeansCluster类197.KMeansDriver类21五、心得体会23..一、实验设计1.实验说明在Eclipse环境下编写实现k-means算法。2.算法说明(1).聚类将给定的多个对象分成若干组，组内的各个对象是相似的，组间的对象是不相似的。进行划分的过程就是聚类过程，划分后的组称为簇(cluster)。几种聚类方法：基于划分的方法；基于层次的方法；基于密度的方法；......(2).基于划分的聚类方法给定N个对象，构造K

3、个分组，每个分组就代表一个聚类。K个分组满足以下条件：(1)每个分组至少包含一个对象；(2)每个对象属于且仅属于一个分组。K-Means算法是最常见和典型的基于划分的聚类方法(3).K-Means算法输入：待聚类的N个数据点，期望生成的聚类的个数K输出：K个聚类算法描述:选出K个点作为初始的clustercenterLoop:对输入中的每一个点p：｛..计算p到各个cluster的距离；将p归入最近的cluster;｝重新计算各个cluster的中心如果不满足停止条件，gotoLoop;否则，停止(1).MapReduce并行化聚类算法设计思路将所有的数据分布到不同的Ma

4、pReduce节点上，每个节点只对自己的数据进行计算。每个Map节点能够读取上一次迭代生成的clustercenters，并判断自己的各个数据点应该属于哪一个cluster。Reduce节点综合每个属于每个cluster的数据点，计算出新的clustercenters。每一个节点需要访问如下的全局文件：当前的迭代计数和K个表示不同聚类中心的如下的数据结构：｛clusteridclustercenter属于该clustercenter的数据点的个数｝这是唯一的全局文件。1.类说明(1).Instance该类对应文件中原始数据点的格式，以ArrayList存放数据点的各个分量

5、。需要编写加法，乘法，除法函数，用于计算簇中心：簇中所有点相加/簇中数据点的个数。..如果是在原有的簇中追加一个数据点，则用（簇中心点*簇中数据点个数+新的数据点）/（簇中数据点个数+1）。(1).Cluster该类记录簇的信息<簇的id，属于该簇的数据点的个数，簇中心>各个节点共享的全局信息，记录每次划分的簇的信息。(2).EuclideanDistance计算欧式距离，通过计算数据点与各个簇中心的距离，选择最小的欧式距离对应的簇中心作为该数据点属于的簇。(3).RandomClusterGenerator该类用于初始时生成k个簇中心，一开始将读入的每个节点作为簇中心，

6、并为其分配一个ID，当达到k个时，以1/(1+k)的概率返回一个[0,k-1]中的正整数，将其对应的簇ID的簇中心替换。(4).KMeans该类即是kmeans算法的实现。它的mapper类应该读入所有的簇中心的信息——kclusters。应在setup()时将之前计算的簇中心读入，作为全局文件。map()所要做的是，读取每个数据点寻找离该点最近的簇id，通过计算欧式距离，选择距离最小的那个簇中心，输出的格式是。它的combiner类将同一个节点的数据点各个簇计算新的簇中心。簇中所有点相加/簇中数据点的个数=新的簇中心。它的redu

7、cer类将不同节点的计算结果汇总，计算全局的新的簇中心。(5).KmeansCluster该类做的工作其实与KMeans类差不多，只不过是没有KMeans的reducer类。..在收敛条件满足且所有簇中心的文件最后产生后，再对输入文件中的所有实例进行划分簇的工作，最后把所有实例按照(实例,簇id)的方式写进结果文件。它的Mapper类也是在setup()时将之前计算的簇中心读入，作为全局文件。map()所要做的是，读取每个数据点寻找离该点最近的簇id，通过计算欧式距离，选择距离最小的那个簇中心，输出的格式是