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

基于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：输入：Object，一条数据输出：所属类，数据Reduce：输入：，相应数据的集合输出：,新的聚类中心迭代job，直至相连两次的聚类中心小于阈值

流程图

Map伪代码publicvoidmap(Objectkey,Textvalue, OutputCollectorIntWritable,Textoutput,Reporterreporter){ Stringline=value.toString().trim(); intsort=0;//聚类类别 doubleminDis=Double.MAX_VALUE; for(inti=1;i=K;i++){ doubletmpDis=calDis(i,line);//数据和类i间的距离 if(tmpDisminDis){ sort=i; minDis=tmpDis; } } output.collect(newIntWritable(sort),value);}

Partition伪代码publicclassKeyPartitionK,VimplementsPartitionerK,V{ @Override publicintgetPartition(Kkey,Vvalue,intn){ //TODOAuto-generatedmethodstub returnMath.abs(key.hashCode())%n; } @Override publicvoidconfigure(JobConfarg0){ //TODOAuto-generatedmethodstub }}

Reduce伪代码publicvoidreduce(IntWritablekey,IteratorTextvalues,OutputCollectorIntWritable,Textoutput,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()iCOLS){ records[i++]+=Double.parseDouble(itr.nextToken()); } } Stringline=; for(i=0;iCOLS;i++){ line+=records[i]/rows+\t; } output.collect(key,newText(line));}

OutputFormat伪代码publicclassFileNameMultipleOutputFormatK,Vextends MultipleTextOutputFormatK,V{//使输出文件名为类型K的值，本例为1、2、3 @Override protectedStringgenerateFileNameForKeyValue(Kkey,Vvalue,Stringname){ retu