hadoop下的mahout的kmeans测试.ppt

基于hadoop分布式平台下的mahout中的kmeans测试,山东农业大学 shandong agriculture university,信息科学与工程学院 崔文斌,Time,kmeans原理 二、mahout下的kmeans实现 三、mahout下的kmeans运行过程 四、运行中的问题,山东农业大学 shandong agriculture university,主要内容,一、kmeans原理,山东农业大学 shandong agriculture university,kmeans算法的原理： k-means 算法接受参数 k ；然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的,一、kmeans原理,山东农业大学 shandong agriculture university,kmeans算法流程： 首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。,一、kmeans原理,山东农业大学 shandong agriculture university,kmeans算法的原理： 输入：k, datan; （1） 选择k个初始中心点，例如c0=data0,ck-1=datak-1; （2） 对于data0.datan, 分别与c0ck-1比较，假定与ci差值最少，就标记为i; （3） 对于所有标记为i点，重新计算ci= 所有标记为i的dataj之和/标记为i的个数； （4） 重复(2)(3),直到所有ci值的变化小于给定阈值。,二、mahout下的kmeans实现,山东农业大学 shandong agriculture university,1、概述： mahout下的kmeans算法实在kmeans与hadoop中间加上了一个中间层来建立kmeans与hadoop之间的联系，实现kmeans的map reduce的任务的分配等工作。kmeans中的核心代码没有变化,二、mahout下的kmeans实现,山东农业大学 shandong agriculture university,2、具体实现过程： 2.1、参数input指定待聚类的所有数据点，clusters指定初始聚类中心如果指定参数k，由org.apache.mahout.clustering.kmeans.RandomSeedGenerator.buildRandom 通过org.apache.hadoop.fs直接从input指定文件中随机读取k个点放入clusters中,二、mahout下的kmeans实现,山东农业大学 shandong agriculture university,2.2、 根据原数据点和上一次迭代(或初始聚类)的聚类中心计算本次迭代 的聚类中心，输出到clusters-N目录下。 该过程由org.apache.mahout.clustering.kmeans下的 KMeansMapperKMeansCombinerKMeansReducerKMeansDriver实现 KMeansMapper：在configure中初始化mapper时读入上一次迭代产生或初始聚类中心 (每个mapper都读入所有的聚类中心); map方法对输入的每个点，计算距离其最近的类，并加入其中 输出key为该点所属聚类ID，value为KMeansInfo实例，包含点的个数和各分量的累加和,二、mahout下的kmeans实现,山东农业大学 shandong agriculture university,KMeansCombiner：本地累加KMeansMapper输出的同一聚类ID下的点个数和各分量的和 KMeansReducer：累加同一聚类ID下的点个数和各分量的和，求本次迭代的聚类中心； 并根据输入Delta判断该聚类是否已收敛：上一次迭代聚类中心与本次迭代聚类中心距离Delta； 输出各聚类中心和其是否收敛标记,二、mahout下的kmeans实现,山东农业大学 shandong agriculture university,KMeansDriver：控制迭代过程直至超过最大迭代次数或所有聚类都已收敛 每轮迭代后，KMeansDriver读取其clusters-N目录下的所有聚类，若所有聚类已收敛 则整个Kmeans聚类过程收敛了。,二、mahout下的kmeans实现,山东农业大学 shandong agriculture university,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,1、数据集准备： mahout下处理的文件必须是SequenceFile格式的，所以需要把txtfile转换成sequenceFile 而聚类必须是向量格式的 mahout seq2sparse：将SequenceFile转成向量文件，对应的源文件是org.apache.mahout.vectorizer.SparseVectorsFromSequenceFiles.java 采用的数据集为synthetic_control.data,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,2、执行的过程： 2.1、启动hadoop的所有节点执行以下命令： hadoop namenode -format start-all.sh启动所有的服务 jps查看服务是否都启动了，尤其是namenode,山东农业大学 shandong agriculture university,2.2、將数据集导入到分布式文件系统中去 hadoop fs -mkdir testdata hadoop fs -put /home/bigdata/synthetic_control.data testdata mahout在hadoop下默认的输入路径是testdata文件,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,2.3、执行mahout中的kmeans算法： 参数的获取主要是通过配置文件获取 mahout org.apache.mahout.clustering.syntheticcontrol.kmeans.Job 或是hadoop jar /home/bigdata/mahout-distribution-0.4/mahout-examples-0.4-job.jar org.apache.mahout.clustering.syntheticcontrol.kmeans.Job,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,2.4、 hadoop fs -lsr output $HADOOP_HOME/bin/hadoop fs -get output $MAHOUT_HOME/examples（将结果从分布式文件系统上导下来），$cd MAHOUT_HOME/examples/output 看到以下结果，那么算法运行成功：canopies clusters-1 clusters-3 clusters-5 clusters-7 pointsclusters-0 clusters-2 clusters-4 clusters-6 data,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,3、mahout运行过程分析： 3.1、Mahout总入口org.apache.mahout.driver.MahoutDriver主要是做一下的事情： 3.1.1、装载$MAHOUT_CONF_DIR目录下的一个名为ps的资源文件(如果找不到，则寻找ps文件)。,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,3.1.2、 装载ps中的类。如果mahout命令行第一个参数不是简写，则装载以第一个参数为名的类。,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,3.1.3、 装载“mahout命令行中第一个参数名.props”的配置文件，该配置文件中可以指定输入输出目录等等参数,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,3.1.4、 调用mahout命令行的第一个参数的类运行，并将命令行参数结合配置文件中的参数以字符的形式传递过去,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,4、Kmeans算法的分布式实现： 4.1、 org.apache.mahout.driver.MahoutDriver会调用org.apache.mahout.clustering.kmeans.KMeansDriver类。,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,4.2、 在KMeansDriver类的runIteration方法中，mahout提交了一个MapReduce任务 代码： job.setMapOutputKeyClass(Text.class); job.setMapOutputValueClass(ClusterObservations.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(Cluster.class); job.setInputFormatClass(SequenceFileInputFormat.class); job.setOutputFormatClass(SequenceFileOutputFormat.class); job.setMapperClass(KMeansMapper.class); job.setCombinerClass(KMeansCombiner.class); job.setReducerClass(KMeansReducer.class); FileInputFormat.addInputPath(job, input); FileOutputFormat.setOutputPath(job, clustersOut); job.setJarByClass(KMeansDriver.class);,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,对KMeans算法的分布式实现的研究，我们应主要关注Cluster、ClusterObservations、KMeansMapper、KMeansCombiner、KMeansReducer这几个类。,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,4.3、 Cluster告诉我们KMeans的cluster是如何表示的。 Cluster继承于org.apache.mahout.clustering.DistanceMeasureCluster类，后者继承于org.apache.mahout.clustering.AbstractCluster抽象类，再后者实现了org.apache.mahout.clustering. Cluster接口 总之，cluster内部有一个变量id（int类型）用于唯一的标识该聚类，numPoints（long类型）表示该聚类内部有多少个点，center（Vector类型，此Vector是数学中的N维向量，也可理解为N维点，非java.util.Vector）表示聚类中心点，radius（Vector类型）表示半径，还有聚合标志位converged（boolean类型）,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,4.4、 ClusterObservations类 跟Kmeans分布式算法有关，ClusterObservations有s0(double，点数目增量),s1(Vector，用于计算中心点增量),s2(Vector，用于计算半径增量),三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,4.5、 KMeansMapper Map过程，输入的key，value =WritableComparable key, VectorWritablepoint 计算每个point表示的点与每个cluster中心center距离，并将改点加入距离最近的cluster中，并计算该cluster的三个增量。,三、mahout下的kmeans运行过程,山东农业大学 shandong agriculture university,4.6、 KMeansCombiner 在Map阶段运行结束后，为了减少到Reduce阶段的网络数据输出，mahout对于同一个