基于MapReduce的K-Means算法设计与实现.pptx

基于MapReduce的K Means算法的设计与实现 西南交通大学信息学院主讲人 杨浩导师 李天瑞教授 概要 研究背景 基于MapReduce的K Means算法设计 实验结果和分析 K Means简介 研究背景 大数据时代的来临数据呈现爆炸性增长传统的平台无法满足需求亟需新的平台云计算的出现天才般的MapReduce计算框架开源的Hadoop平台聚类算法和大数据数据越大 聚类效果越好 K Means简介 输入 聚类个数K 以及包含N个数据待聚类数据集输出 聚类中心不再变化的K个聚类中心算法过程 从从数据集中随机选取K个数据作为中心测量所有数据到每个中心的距离 并把它归到最近的中心的类重新计算已经得到的各个类的中心迭代2 3步直至新的中心与原中心的距离小于指定阈值 算法结束 K Means算法流程图 K Means示例 基于MapReduce的K Means算法设计 算法设计伪代码Map伪代码Partion伪代码Reduce伪代码OutputFormat伪代码 算法设计 job 计算新的聚类中心Map 输入 输出 Reduce 输入 输出 迭代job 直至相连两次的聚类中心小于阈值 流程图 Map伪代码 publicvoidmap Objectkey Textvalue OutputCollectoroutput Reporterreporter Stringline value toString trim intsort 0 聚类类别doubleminDis Double MAX VALUE for inti 1 i K i doubletmpDis calDis i line 数据和类i间的距离if tmpDis minDis sort i minDis tmpDis output collect newIntWritable sort value Partition伪代码 publicclassKeyPartitionimplementsPartitioner OverridepublicintgetPartition Kkey Vvalue intn TODOAuto generatedmethodstubreturnMath abs key hashCode n Overridepublicvoidconfigure JobConfarg0 TODOAuto generatedmethodstub Reduce伪代码 publicvoidreduce IntWritablekey Iteratorvalues OutputCollectoroutput Reporterreporter introws 0 i 0 rows表示数据条数doublerecords newdouble COLS COLS为全局变量 表示属性的个数while values hasNext rows Stringtmp values next toString StringTokenizeritr newStringTokenizer tmp i 0 while itr hasMoreTokens OutputFormat伪代码 publicclassFileNameMultipleOutputFormatextendsMultipleTextOutputFormat 使输出文件名为类型K的值 本例为1 2 3 OverrideprotectedStringgenerateFileNameForKeyValue Kkey Vvalue Stringname returnkey toString OverrideprotectedKgenerateActualKey Kkey Vvalue returnnull 实验结果和分析 开发环境实验数据运行结果结果分析 开发环境 RedHatLinux操作系统Hadoop开源软件 版本Hadoop 1 0 3节点数目 10节点配置 4个CPU 16核 内存12GJDK