1、基于 MapReduce 的 K-Means 并行算法设计目录一、 实验设计 .21. 实验说明 .22. 算法说明 .2(1). 聚类 .2(2). 基于划分的聚类方法 .2(3). K-Means 算法 .2(4). MapReduce 并行化聚类算法设计思路 .33. 类说明 .3(1). Instance.3(2). Cluster.4(3). EuclideanDistance.4(4). RandomClusterGenerator.4(5). KMeans .4(6). KmeansCluster .4(7). KMeansDriver .5二、 实验结果说明 .51. 实验设置
2、 .52. 源数据点 .63. 聚类结果 .7三、 性能和不足 .7四、 源程序 .81. Instance 类 .82. Cluster 类 .103. EuclideanDistance 类 .124. PageRankDriver 类 .125. KMeans 类 .156. KMeansCluster 类 .197. KMeansDriver 类 .21五、 心得体会 .23一、 实验设计1. 实验说明在 Eclipse 环境下编写实现 k-means 算法。2. 算法说明(1).聚类将给定的多个对象分成若干组，组内的各个对象是相似的，组间的对象是不相似的。进行划分的过程就是聚类过程，
3、划分后的组称为簇(cluster)。几种聚类方法： 基于划分的方法； 基于层次的方法； 基于密度的方法； .(2).基于划分的聚类方法给定 N 个对象，构造 K 个分组，每个分组就代表一个聚类。K 个分组满足以下条件：(1)每个分组至少包含一个对象； (2)每个对象属于且仅属于一个分组。K-Means 算法是最常见和典型的基于划分的聚类方法(3). K-Means 算法输入：待聚类的 N 个数据点，期望生成的聚类的个数 K输出：K 个聚类算法描述:选出 K 个点作为初始的 cluster centerLoop:对输入中的每一个点 p： 计算 p 到各个 cluster 的距离；将 p 归入最近
4、的 cluster;重新计算各个 cluster 的中心如果不满足停止条件，goto Loop; 否则，停止(4). MapReduce 并行化聚类算法设计思路将所有的数据分布到不同的 MapReduce 节点上，每个节点只对自己的数据进行计算。每个 Map 节点能够读取上一次迭代生成的 cluster centers，并判断自己的各个数据点应该属于哪一个 cluster。Reduce 节点综合每个属于每个 cluster 的数据点，计算出新的 cluster centers。每一个节点需要访问如下的全局文件：当前的迭代计数和 K 个表示不同聚类中心的如下的数据结构： cluster idcl
5、uster center属于该 cluster center 的数据点的个数这是唯一的全局文件。3. 类说明(1). Instance该类对应文件中原始数据点的格式，以 ArrayList 存放数据点的各个分量。需要编写加法，乘法，除法函数，用于计算簇中心：簇中所有点相加/簇中数据点的个数。如果是在原有的簇中追加一个数据点，则用（簇中心点*簇中数据点个数+新的数据点）/（簇中数据点个数 +1） 。(2). Cluster该类记录簇的信息各个节点共享的全局信息，记录每次划分的簇的信息。(3). EuclideanDistance计算欧式距离，通过计算数据点与各个簇中心的距离，选择最小的欧式距离对
6、应的簇中心作为该数据点属于的簇。(4). RandomClusterGenerator该类用于初始时生成 k 个簇中心，一开始将读入的每个节点作为簇中心，并为其分配一个 ID，当达到 k 个时，以 1/(1+k)的概率返回一个 0,k-1中的正整数，将其对应的簇 ID 的簇中心替换。(5). KMeans该类即是 kmeans 算法的实现。它的 mapper 类应该读入所有的簇中心的信息 kclusters。应在 setup()时将之前计算的簇中心读入，作为全局文件。map() 所要做的是，读取每个数据点寻找离该点最近的簇 id，通过计算欧式距离，选择距离最小的那个簇中心，输出的格式是。它的
7、combiner 类将同一个节点的数据点各个簇计算新的簇中心。簇中所有点相加/ 簇中数据点的个数= 新的簇中心。它的 reducer 类将不同节点的计算结果汇总，计算全局的新的簇中心。(6). KmeansCluster该类做的工作其实与 KMeans 类差不多，只不过是没有 KMeans 的 reducer类。在收敛条件满足且所有簇中心的文件最后产生后，再对输入文件中的所有实例进行划分簇的工作，最后把所有实例按照(实例, 簇 id)的方式写进结果文件。它的 Mapper 类也是在 setup()时将之前计算的簇中心读入，作为全局文件。map()所要做的是，读取每个数据点寻找离该点最近的簇 i
8、d，通过计算欧式距离，选择距离最小的那个簇中心，输出的格式是。(7). KMeansDriver该类是用来启动整个 MapReduce，启动参数包括 k: 簇中心数，iteration num: 迭代数，input path: 输入路径，output path: 输出路径。首先调用 RandomClusterGenerator 类的 generateInitialCluster()初始化簇中心，然后用 KMeans 类进行簇中心的迭代计算，最后用 KMeansCluster 类为每个数据点选择最终确定的距离最近的簇。二、 实验结果说明1. 实验设置簇个数设置为 5，迭代次数设置为 102. 源
9、数据点3. 聚类结果三、 性能和不足k-means 算法对初始 cluster centers 的选取会影响到最终的聚类结果，能得到局部最优解，不保证得到全局最优解。相似度计算和比较时的计算量较大。四、 源程序1. Instance 类public class Instance implements WritableArrayList value;public Instance()value = new ArrayList();public Instance(String line)String valueString = line.split(“,“);value = new ArrayLi
10、st();for(int i = 0; i ();for(int i = 0; i getValue()return value;public Instance add(Instance instance)if(value.size() = 0)return new Instance(instance);else if(instance.getValue().size() = 0)return new Instance(this);else if(value.size() != instance.getValue().size()try throw new Exception(“can not
11、 add! dimension not compatible!“ + value.size() + “,“+ instance.getValue().size(); catch (Exception e) e.printStackTrace();return null;elseInstance result = new Instance();for(int i = 0;i ();if(size = in.readInt() != 0)for(int i = 0; i size; i+)value.add(in.readDouble();2. Cluster 类public class Cluster implements Writableprivate int clusterID;private long numOfPoints;private Instance center;public Cluster()
