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

1、实用标准文案数据挖掘聚类问题 (Plants Data Set)实验报告1. 数据源描述1.1 数据特征本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属 )以及它们生长的地区。数据集中总共有68 个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物 (或者某一科属 )及其在上述68 个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。植物名称 ( 科属 +名称 )分布区域图 1 数据格式例如一条数据 :abroniafragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abro

2、niafragrans是植物名称 (abronia是科属， fragrans是名称 ) ，从 az 一直到 wy是该植物的分布区域，采用缩写形式表示，如az 代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。1.2 任务要求聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。2. 数据预处理2.1 数据清理所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如：文档大全实用标准文

3、案abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,viabelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,viabelmoschus moschatus,hi,pr上述数据中第行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集合。在聚类过程中第行数据是无用的，因此要对其进行清理。2.2 数据变换本实验是依据植物的

4、分布区域进行聚类，所给数据集中的分布区域是字符串形式，不适合进行聚类，因此将其变换成适合聚类的数值形式。具体思想如下：数据集中总共包含68 个区域，每一种植物的分布区域是这68 个区域中的一部分。本实验中将 68 个区域看成是数据对象的68 个属性，这 68 个属性是二元类型的变量，其值只能去0 或者 1。步骤如下：1.把 68 个区域按一定顺序存放在字符串数组(记为 str) 中(顺序可以自己定，确定后不能改变 )。2.为数据集中的每个数据对象设置一个长度为68 字符串数组，初始元素值全为 0。将数据对象的分布区域逐个与 str 中的所有元素比较。如果存在于str中下标 i 的位置，就将该数

5、据对象的字符串数组的第i 位置为 1。例如，一个数据对象为：abies fraseri,ga,nc,tn,va。其分布区域包含ga,nc,tn和 va 四个地区，将这四个地区逐个与 str 中全部 68 个元素比较。 假设这四个地区分别存在于 str 中的第 0,1,2,3 位置，则将为该数据对象设置的字符串数组中第 0,1,2,3 位置全部置为 1 。文档大全实用标准文案数据预处理代码 ( 包括数据清理和数据变换) ：publicArrayList<String> getRaw_DataSet() ArrayList<String> raw_dataSet =newA

6、rrayList<String>();/定义集合存储从本地获取的数据BufferedReader bufferedReader =null ;FileReader fileReader =null ;File dataFile =newFile( this .fileName);if (dataFile.exists() /如果数据文件存在tryfileReader =newFileReader(this .fileName);bufferedReader =newBufferedReader(fileReader);String data =null ;while(data =

7、bufferedReader.readLine() !=null ) if (isRightData(data)raw_dataSet.add(data); catch(Exception e) e.printStackTrace(); elsethis .isFileExit= false ;returnraw_dataSet;文档大全实用标准文案/ getRaw_DataSet,从本地 txt 文件获取数据集publicArrayList<DataItem> getFinished_DataSet() /获取经过预处理，用来进行聚类的数据ArrayList<DataIte

8、m> 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),',' );/除去 "," 后的每一行数据DataItem da

9、ta_Item =newDataItem(eachRomItem,true );finished_DataSet.add(data_Item);/ forreturnfinished_DataSet;publicbooleanisRightData(String data) /筛选出合适的数据ArrayList<String> tempArrayList =newArrayList<String>();tempArrayList = spilt(data,' ' );if (tempArrayList.size() <= 1)returnfalse

10、 ;returntrue ;/ isRightData,筛选出合适的数据文档大全实用标准文案publicArrayList<String> spilt(String str,charch) ArrayList<String> words =newArrayList<String>();/用来存放找到的单词int beginIndex = 0;for(inti = 0; i < str.length(); i+) if (str.charAt(i) != ch) if (i != str.length() - 1)continue;else words.

11、add(str.substring(beginIndex); else String temp = str.substring(beginIndex, i);words.add(temp);beginIndex = i + 1;/ forreturnwords;3. 聚类分析3.1算法描述本实验采用了聚类分析中常用的K 均值 (K-Means) 算法。该算法思想如下：文档大全实用标准文案算法：K 均值。用于划分的K 均值算法，每个簇的中心用簇中对象的均值表示。输入：k ：簇的属目D ：包含 n 个对象的数据集。输出：k 个簇的集合。方法：(1)从 D 中任意选择 k 个对象作为初始簇中心；(2

12、) repeat(3) 根据簇中对象的均值，将每个对象 (再)指派到最相似的簇；(4) 更新簇均值，既计算每个簇中对象的均值；(5) until 不再发生变化根据上述算法，结合本实验实际情况和数据集特征给出程序的执行流程图：开始从本地读取数据文件数据预处理输入 k,簇的个数在数据集中随机选取k 个数据对象作为初始中心点迭代开始。将数据集中每个数据对象与 k 个中心点作比较，把每个对象分到与其 最相似 的中心点所在的簇中计算每个簇中对象的均值，作为该簇新的中心点满足迭代终迭代终止，输出结果。止条件文档大全实用标准文案是否图 2 程序执行流程针对上面的流程图，有几点说明：1.数据预处理主要包括前述

13、数据清理和数据变换，最终生成用于聚类分析的数据集。2.簇的个数 k 由用户指定， k 越大聚类过程耗时越久。3.图中“最相似” 意思就是距离中心点距离最近，本实验中采用欧几里得距离，其定义如下：d (i, j ) ( xi1222x j1)(xi 2 x j 2) .(xin x jn )其中 i( xi1 , xi 2 ,., xin ) 和 j( xj1 , xj 2 ,. xjn ) 是两个 n维数据对象。在本实验中，x 和 x 分别代表为 i,j 两个数据对象设置的字符串数组 (参看 2.2) 中下标为 1 的i 1j1元素值，此处 n 为 68 。4.流程图中的终止条件指的是：前后两

14、次中心点之间的距离(仍然用欧几里得距离 )是否小于设定的值。 例如，第 n 次迭代完成后重新生成了k 个新的中心点，计算 k 个新中心点与 k 个旧的中心点距离之和并将结果与设定的值比较，若小于文档大全实用标准文案设定值则终止迭代，聚类完成，否则继续迭代。3.2算法实现图 3 代码文件的组织结构上图是本实验源码的组织结构，该项目包含五个Java 类。每个类的功能描述如下：Cluster.java类 该类定义了簇的结构，包含簇标志，簇成员和簇中心点三个字段。该类的每一个实例对应于聚类过程中的一个簇。DataItem.java类 该类定义了数据对象的结构，主要包含数据对象名称( 即植物名称 )和数

15、据对象字符串数组(即植物的分布区域) 。该类的每一个实例对应于数据集中的一个数据对象。Main.java类 该类是程序的核心类，主要功能是执行聚类过程，包括中心点的选取与更新，计算各个数据对象与中心点之间的距离并把其派分到最相似的簇等。ReadData.java类 该类主要功能是生成聚类过程适用的数据集，包括读取文件，数据预处理等。Tools.java类 该类是一个工具类，其中定义了多个程序中使用到的静态方法。Mian.java类中的核心代码：(1) 随机选取中心点publicvoidsetCenter_ran() /第一次，从数据集中随机选取中心点文档大全实用标准文案beginTime= S

16、ystem. currentTimeMillis();System. out .println("聚类过程开始 ,开始于 :" + Tools.currentTime();Random ran =newRandom();int order = 0;/ 随机选取中心点while(this.center .size() <numOfCluster) order = ran.nextInt(toBeProcessed.size();if(Tools. isProCener (toBeProcessed.get(order),this .center)this .center

17、.add(toBeProcessed.get(order);/ while(2) 初始化簇集合publicvoidinitArrayCluster(ArrayList<DataItem> center) /初始每个簇中的中心点属性this .arrayCluster.clear(); /把簇集合清空for(inti = 0; i < center.size(); i+) Cluster cluster =newCluster(i, center.get(i);if (this .center .get(i).getIsDataItem()cluster.addMembers(

18、center.get(i);this .arrayCluster.add(cluster);(3) 执行聚类过程 ( 计算距离，把数据对象派分到最相似簇中)文档大全实用标准文案publicvoidrunCluster(ArrayList<DataItem> center) int beyondIndex = 0;/ 判断数据项属于哪一个簇，初始默认为是0 簇Random rd =newRandom(); / 随机函数printBeginInfo();/打印以此迭代开始前的信息。for(inti = 0; i <toBeProcessed.size(); i+) beyondI

19、ndex = 0;booleanisAlreadyExitInCluster =true ;/标记当前处理的数据对象是否已经存在于某个簇中doubleminDistance = Tools.calcDistance (toBeProcessed.get(i),center.get(0), 0);intranIndex = rd.nextInt(center.size();/随机产生一个中心点集合的索引for( int j = 0; j < center.size(); j+) /分别与每一个中心点进行比较if (center.contains(toBeProcessed.get(i)/如

20、果正在处理的数据对象存在于中心点集合中，则跳出循环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;文档大全实用标准文案b

21、eyondIndex = ranIndex;/第二个ifranIndex+;/第二个forif (!isAlreadyExitInCluster) this .arrayCluster.get(beyondIndex).addMembers(toBeProcessed.get(i); /把数据对象加入到对应的簇中/第一个 forSystem. out .println("第 " + this .count+ " 次迭代完成。");printClusteringInfo();(4) 迭代过程 ( 产生新的中心点，继续执行聚类过程直至满足终止条件)publi

22、cvoidfinishCluster() DecimalFormat df =newDecimalFormat("#.000");/格式化数据，保留三位小数for(inti = 0; i <NUM ; i+) doublemoveDistance = 0.0;/存放各个簇新旧中心点欧几里得距离之和/重新计算簇中心点for( int j = 0; j <numOfCluster; j+) booleanisEmptyCluster =true ;DataItem newCenterItem;/声明新的中心点对象文档大全实用标准文案int size =this .a

23、rrayCluster.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 +=this .arrayCluster.get( j).getMembers().get(k).getAreas

24、()index;if (!isEmptyCluster) newCenterAreaindex = Double.valueOf (df.format(tempValue / size); elsebreak ;/第三个forif (!isEmptyCluster) /如果簇不为空String name ="cluster"+ j;newCenterItem =newDataItem(name, newCenterArea,false );/新的簇中心点对象DataItem oldCenter =this .center .get( j); /获取旧的簇中心点moveDis

25、tance += 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

26、.center );runCluster(this .center );/第一个 for3.3问题与改进聚类分析要求不同簇之间的距离尽可能大，初始随机选取的中心点并不能保证不同中心点之间的距离尽可能远，本程序对算法进行改进， 在随机选取中心点时要求与已经选取的中心点之间的距离大于设定值。这样做保证了随机选取的中心点相对比较分散，提高了聚类效果。主要代码如下：publicstaticbooleanisProCener(DataItem centerItem,/判断是不是合适的中心点ArrayList<DataItem> center) if (center.size() > 0) /如果当前的中心点集合不为空文档大全实用标准文案for( int i = 0; i < center.s