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

概要研究背景基于MapReduce的K-Means算法设计实验结果和分析K-Means简介研究背景大数据时代的来临数据呈现爆炸性增长传统的平台无法满足需求亟需新的平台云计算的出现天才般的MapReduce计算框架开源的Hadoop平台聚类算法和大数据数据越大，聚类效果越好K-Means简介输入：聚类个数K，以及包含N个数据待聚类数据集输出：聚类中心不再变化的K个聚类中心算法过程：1.从从数据集中随机选取K个数据作为中心2.测量所有数据到每个中心的距离，并把它归到最近的中心的类3.重新计算已经得到的各个类的中心4.迭代2～3步直至新的中心与原中心的距离小于指定阈值，算法结束K-Means算法流程图K-Means示例基于MapReduce的K-Means算法设计算法设计伪代码Map伪代码Partion伪代码Reduce伪代码OutputFormat伪代码算法设计job：计算新的聚类中心Map：输入：Object，一条数据输出：所属类，数据Reduce：输入：，相应数据的集合输出：,新的聚类中心迭代job，直至相连两次的聚类中心小于阈值iCiCiC流程图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{@OverridepublicintgetPartition(Kkey,Vvalue,intn){//TODOAuto-generatedmethodstubreturnMath.abs(key.hashCode())%n;}@Overridepublicvoidconfigure(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,VextendsMultipleTextOutputFormatK,V{//使输出文件名为类型K的值，本例为1、2、3@OverrideprotectedStringgenerateFileNameForKeyValue(Kkey,Vvalue,Stringname){returnkey.toString();}@OverrideprotectedKgenerateActualKey(Kkey,Vvalue){returnnull;}}实验结果和分析开发环境实验数据运行结果结果分析开发环境RedHatLinux操作系统Hadoop开源软件，版本Hadoop-1.0.3节点数目：10节点配置：4个CPU，16核，内存12GJDK1.7.0Eclipse-SDK-4.2.1-linux-gtk实验数据数据集295个数据100个属性选取了3个聚类中心运行结果迭代前后的中心间的距离迭代次数距离10.416281752617621720.2261470651387958430.1643413181893543240.0891535211218527850.05741151849787401560.0297434007942915870.0278291782916929480.0302077319519657890.012126278742641175101.6540101356382944E-15运行结果迭代第5次的运行结果谢谢大家