数据挖掘聚类算法课程设计报告

数据挖掘聚类问题(PlantsDataSet)实验报告数据源描述数据特征植物名称(科属+名称)分布区域6868植物名称(科属+名称)分布区域图1数据格式:abroniafragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wyabroniafragrans(abroniaaz一直到azArizona和分布地区用逗号隔开，各地区之间也用逗号隔开。任务要求成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。2.数据预处理数据清理植物及其分布地区。例如：abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,viabelmoschusesculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,viabelmoschusmoschatus,hi,pr上述数据中第行给出了所有属于abelmoschus这一科属的植物的分布地abelmoschus布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集合。在聚类过程中第行数据是无用的，因此要对其进行清理。数据变换本实验是依据植物的分布区域进行聚类，所给数据集中的分布区域是字符串形式，不适合进行聚类，因此将其变换成适合聚类的数值形式。具体思想如下：686868686801。步骤如下：把68个区域按一定顺序存放在字符串数组(记为str定，确定后不能改变)。680。将数据对象的分布区域逐个strii1。例如，一个数据对象为：abiesfraseri,ga,nc,tn,va。其分布区域包含ga,nc,tnvastr68str0,1,2,30,1,2,31。publicArrayList<String>getRaw_DataSet(){ArrayList<String>raw_dataSet=publicArrayList<String>getRaw_DataSet(){ArrayList<String>raw_dataSet=newArrayList<String>();//定义集合存储从本地获取的数据BufferedReaderbufferedReader=null;FileReaderfileReader=null;FiledataFile=newFile(this.fileName);if(dataFile.exists()){//如果数据文件存在try{fileReader=newFileReader(this.fileName);bufferedReader=newBufferedReader(fileReader);Stringdata=null;while((data=bufferedReader.readLine())!=null){if(isRightData(data))raw_dataSet.add(data);}}catch(Exceptione){e.printStackTrace();}}elsethis.isFileExit=false;returnraw_dataSet;}//getRaw_DataSet,txt文件获取数据集publicArrayList<DataItemgetFinished_DataSet(//获取经过预处理，用来进行聚类的数据ArrayList<DataItem>finished_DataSet=newArrayList<DataItem>();ArrayList<String>temp_DataSet=this.getRaw_DataSet();for(inti=0;i<temp_DataSet.size();i++){ArrayList<String>eachRomItem=null;eachRomItem=this.spilt(temp_DataSet.get(i),',');//除去","后的每一行数据

DataItemdata_Item=newDataItem(eachRomItem,true);finished_DataSet.add(data_Item);}//forreturnfinished_DataSet;}publicbooleanisRightData(Stringdata){//筛选出合适的数据ArrayList<String>tempArrayList=newArrayList<String>();tempArrayList=spilt(data,'');if(tempArrayList.size()<=1)returnfalse;returntrue;}//isRightData,筛选出合适的数据publicArrayList<String>spilt(Stringstr,charch){ArrayList<String>words=newArrayList<String>();//用来存放找到的单词intbeginIndex=0;for(inti=0;i<str.length();i++){if(str.charAt(i)!=ch){if(i!=str.length()-1)continue;else{words.add(str.substring(beginIndex));}}else{Stringtemp=str.substring(beginIndex,i);words.add(temp);beginIndex=i+1;}}//forreturnwords;}聚类分析算法描述本实验采用了聚类分析中常用的K均值(K-Means)算法。该算法思想如下：算法算法：KK输入：k：簇的属目D：n输出：k方法：(1Dk(2)repeat(3)根据簇中对象的均值，将每个对象(再)指派到最相似的簇；(4)更新簇均值，既计算每个簇中对象的均值；(5)until不再发生变化根据上述算法，结合本实验实际情况和数据集特征给出程序的执行流程图：开始从本地读取数据文件

在数据集中随机选取k个数据对象作为初始中心点迭代开始。将数据集中每个数据对象与k个中心点作比较，把每个对象分数据预处理 到与最相似的中心点所在的簇中输入k,簇的个数计算每个簇中对象的均 值，作为该簇新的中心点迭代终止，输出结果。

满足迭代终 否止条件图2程序执行流程针对上面的流程图，有几点说明：据集。k，kj2injnj2injnd(i,j) (x

2 ( xxi2xx

2...(x x 2其中i(xxi1 i2

,...,xin

j

,xj1 j

,...

)是两个n维数据对象。在本实验中，jnx i1

分别代表为i,j两个数据对象设置的字符串数组(参看2.2)中下标为1j1的元素值，此处n为68。流程图中的终止条件指的是：前后两次中心点之间的距离(仍然用欧几里得nkkk算法实现图3代码文件的组织结构上图是本实验源码的组织结构，该项目包含五个Java类。每个类的功能描述如下：Cluster.java该类的每一个实例对应于聚类过程中的一个簇。DataItem.java称)和数据对象字符串数组(即植物的分布区域)。该类的每一个实例对应于数据集中的一个数据对象。Main.java与更新，计算各个数据对象与中心点之间的距离并把其派分到最相似的簇等。ReadData.java类数据预处理等。Tools.java该类是一个工具类，其中定义了多个程序中使用到的静态方法。★Mian.java类中的核心代码：publicvoidsetCenter_ran(){publicvoidsetCenter_ran(){//第一次，从数据集中随机选取中心点beginTime=System.currentTimeMillis();System.out.println("聚类过程开始,开始于:"+Tools.currentTime());Randomran=newRandom();intorder=0;//随机选取中心点while(this.center.size()<numOfCluster){order=ran.nextInt(toBeProcessed.size());if(Tools.isProCener(toBeProcessed.get(order),this.center))this.center.add(toBeProcessed.get(order));}//while}初始化簇集合publicvoidpublicvoidinitArrayCluster(ArrayList<DataItem//初始每个簇中的中心点属性this.arrayCluster.clear();//把簇集合清空for(inti=0;i<center.size();i++){Clustercluster=newCluster(i,center.get(i));if(this.center.get(i).getIsDataItem())cluster.addMembers(center.get(i));this.arrayCluster.add(cluster);}}publicvoidrunCluster(ArrayList<DataItem>center){publicvoidrunCluster(ArrayList<DataItem>center){intbeyondIndex0;//0簇Randomrd=newRandom();//随机函数printBeginInfo();//打印以此迭代开始前的信息。for(inti=0;i<toBeProcessed.size();i++){beyondIndex=0;booleanisAlreadyExitInClustertrue;//标记当前处理的数据对象是否已经存在于某个簇中doubleminDistance=Tools.calcDistance(toBeProcessed.get(i),的索引比较

center.get(0),0);intranIndexrd.nextInt(center.size())//随机产生一个中心点集合for(intj0jcenter.size()j++//分别与每一个中心点进行if(center.contains(toBeProcessed.get(i)))//如果正在处理的数据对象存在于中心点集合中，则跳出循环break;isAlreadyExitInCluster=false;if(ranIndex>=center.size())ranIndex=ranIndex%center.size();doublecorrentDistance=Tools.calcDistance(toBeProcessed.get(i),center.get(ranIndex),0);if(correntDistance<minDistance){minDistance=correntDistance;beyondIndex=ranIndex;}//第二个ifranIndex++;}//第二个forif(!isAlreadyExitInCluster){this.arrayCluster.get(beyondIndex).addMembers(toBeProcessed.get(i));//把数据对象加入到对应的簇中}}//第一个forSystem.out.println("第"+this.count+"次迭代完成。");printClusteringInfo();}publicvoidfinishCluster(){publicvoidfinishCluster(){DecimalFormatdf=newDecimalFormat("##.000");//格式化数据，保留三位小数for(inti=0;i<NUM;i++){doublemoveDistance=0.0;//存放各个簇新旧中心点欧几里得距离之和//重新计算簇中心点for(intj=0;j<numOfCluster;j++){booleanisEmptyCluster=true;DataItemnewCenterItem;//声明新的中心点对象intsize=this.arrayCluster.get(j).getMembers().size();double[]newCenterArea=newdouble[NUMOFAREA];//计算簇中数据的均值for(intindex=0;index<NUMOFAREA;index++){doubletempValue=0.0;//暂存每一列区域值的加和for(intk=0;k<size;k++){isEmptyCluster=false;tempValue+=tempValue+=this.arrayCluster.get(j).getMembers().get(k).getAreas()[index];}if(!isEmptyCluster){newCenterArea[index]=Double.valueOf(df.format(tempValue/size));}elsebreak;}//第三个forif(!isEmptyCluster){//如果簇不为空Stringname="cluster"+j;newCenterItem=newDataItem(name,newCenterArea,false);//新的簇中心点对象DataItemoldCenter=this.center.get(j);//获取旧的簇中心点moveDistance+=Tools.calcDistance(oldCenter,newCenterItem,0);//计算新旧中心点移动的距离this.center.remove(j);//更新簇中心点集合this.center.add(j,newCenterItem);}}//第二个for,重新计算簇中心//System.out.println(this.center.toString());//打印新的中心点信息if(moveDistance<EXIT*numOfCluster){break;}count++;initArrayCluster(this.center);runCluster(this.center);}//第一个for}问题与改进publicstaticpublicstaticbooleanisProCener(DataItemcenterItem,//判断是不是合适的中心点ArrayList<DataItem>center){if(center.size()>0){//如果当前的中心点集合不为空for(inti=0;i<center.size();i++){if(Tools.calcDistance(centerItem,center.get(i),0)<DIFF)returnfalse;}if(center.contains(centerItem))returnfalse;}returntrue;}开发与运行环境配置操作系统：Windows7开发工具：Eclipse开发语言：JavaCPU：2.2GHz内存：3.5GB两种运行方式：PlantsClusteringEclipseexe或更高版本。程序运行情况分析运行截图图4指定数据文件并输入聚类簇数Dplants.data.txt100图5迭代过程，输出中心点信息50图6第一次迭代后簇的信息 图7簇的信息和终止条件的判定一次迭代完成后会输出本次迭代后各簇的信息并计算新旧中心点的移动距离，与设定的值比较，判定是否继续迭代。图8把簇的信息保存到本地满足终止条件，迭代结束，此时会在D:\DataMining\目录下生成保存各个簇信息的文件，里面是该簇中包含的数据对象。聚类效果分析对聚类效果评判的参考。如下截图：除姿奻泉如7-:汪0内数据对祭距宽中心平距宫，1.19凶9162 81221463秏1内数据对宗距冉中心点平均距宅，8，52766心53977846秏距定，1.3口333333B3钰3距商263033175356钰4内勀扼对杂距宫中心点，0,061451633344汪5均距宫，8972OOll6516E5还钰6内数据对柔距宫中心点351钰1.6827351681957152簇1.7432.29328155375拜9内数:15933465116279El6程10平均距亩：112502程1.内数拥对柔距禹中均距商：0,072363652326659程12内数据对柔距离平均距商：1．压41'.ii丛4695, 5946钰平均距商2.35El7995798319316钰14平均距窝062B955650929B931程1对呆距窝:0.267587583程16对柔距窝平均距窝2385氐0857,8573程17内数据对录距窝中心点平均距窝：1．41340'46575辽2.45程18内数据对录距离中心点平均距窝：2.81150句27272729程19内数据对柔距离中心点平均距商：2.479'938.2470119545拜2O内数据对柔距离中心点平均距面：0．，05627766570695055拜卫内数据对柔距离中心点：2.491906493邸7拜22哟据对柔距画中心点平均距0.