数据挖掘聚类算法课程设计报告(共12页)

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

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

3、l,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的位置，就将该数据对象的字符串数组的第i位置为1。例如，一个数据对象为：abies fras

5、eri,ga,nc,tn,va。其分布区域包含ga,nc,tn和va四个地区，将这四个地区逐个与str中全部68个元素比较。假设这四个地区分别存在于str中的第0,1,2,3位置，则将为该数据对象设置的字符串数组中第0,1,2,3位置全部置为1。 数据预处理代码(包括数据清理和数据变换)：public ArrayList<String> getRaw_DataSet() ArrayList<String> raw_dataSet = new ArrayList<String>();/ 定义集合存储从本地获取的数据BufferedReader buffered

6、Reader = null;FileReader fileReader = null;File dataFile = new File(this.fileName);if (dataFile.exists() / 如果数据文件存在try fileReader = new FileReader(this.fileName);bufferedReader = new BufferedReader(fileReader);String data = null;while (data = bufferedReader.readLine() != null) if (isRightData(data)r

7、aw_dataSet.add(data); catch (Exception e) e.printStackTrace(); elsethis.isFileExit = false;return raw_dataSet;/ getRaw_DataSet,从本地txt文件获取数据集public ArrayList<DataItem> getFinished_DataSet() / 获取经过预处理，用来进行聚类的数据ArrayList<DataItem> finished_DataSet = new ArrayList<DataItem>();ArrayList

8、<String> temp_DataSet = this.getRaw_DataSet();for (int i = 0; i < temp_DataSet.size(); i+) ArrayList<String> eachRomItem = null;eachRomItem = this.spilt(temp_DataSet.get(i), ',');/ 除去","后的每一行数据DataItem data_Item = new DataItem(eachRomItem, true);finished_DataSet.add(

9、data_Item);/ forreturn finished_DataSet;public boolean isRightData(String data) / 筛选出合适的数据ArrayList<String> tempArrayList = new ArrayList<String>();tempArrayList = spilt(data, ' ');if (tempArrayList.size() <= 1)return false;return true;/ isRightData,筛选出合适的数据public ArrayList<

10、;String> spilt(String str, char ch) ArrayList<String> words = new ArrayList<String>();/ 用来存放找到的单词int beginIndex = 0;for (int i = 0; i < str.length(); i+) if (str.charAt(i) != ch) if (i != str.length() - 1)continue;else words.add(str.substring(beginIndex); else String temp = str.sub

11、string(beginIndex, i);words.add(temp);beginIndex = i + 1;/ forreturn words;3. 聚类分析 3.1 算法描述本实验采用了聚类分析中常用的K均值(K-Means)算法。该算法思想如下：算法：K均值。用于划分的K均值算法，每个簇的中心用簇中对象的均值表示。输入： k：簇的属目 D：包含n个对象的数据集。输出：k个簇的集合。方法： (1)从D中任意选择k个对象作为初始簇中心； (2)repeat (3) 根据簇中对象的均值，将每个对象(再)指派到最相似的簇； (4) 更新簇均值，既计算每个簇中对象的均值； (5)until 不

12、再发生变化开始从本地读取数据文件数据预处理输入k,簇的个数在数据集中随机选取k个数据对象作为初始中心点迭代开始。将数据集中每个数据对象与k个中心点作比较，把每个对象分到与其最相似的中心点所在的簇中计算每个簇中对象的均值，作为该簇新的中心点满足迭代终止条件迭代终止，输出结果。根据上述算法，结合本实验实际情况和数据集特征给出程序的执行流程图： 否是 图2 程序执行流程针对上面的流程图，有几点说明： 1.数据预处理主要包括前述数据清理和数据变换，最终生成用于聚类分析的数据集。 2.簇的个数k由用户指定，k越大聚类过程耗时越久。 3.图中“最相似”意思就是距离中心点距离最近，本实验中采用欧几里得距离，

13、其定义如下：其中和是两个n维数据对象。在本实验中，和分别代表为i,j两个数据对象设置的字符串数组(参看2.2)中下标为1的元素值，此处n为68。 4.流程图中的终止条件指的是：前后两次中心点之间的距离(仍然用欧几里得距离)是否小于设定的值。例如，第n次迭代完成后重新生成了k个新的中心点，计算k个新中心点与k个旧的中心点距离之和并将结果与设定的值比较，若小于设定值则终止迭代，聚类完成，否则继续迭代。 3.2 算法实现图3 代码文件的组织结构上图是本实验源码的组织结构，该项目包含五个Java类。每个类的功能描述如下：Cluster.java类 该类定义了簇的结构，包含簇标志，簇成员和簇中心点三个字

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

15、机选取中心点public void setCenter_ran() / 第一次，从数据集中随机选取中心点beginTime = System.currentTimeMillis();System.out.println("聚类过程开始,开始于:" + Tools.currentTime();Random ran = new Random();int order = 0;/ 随机选取中心点while (this.center.size() < numOfCluster) order = ran.nextInt(toBeProcessed.size();if (Tools

16、.isProCener(toBeProcessed.get(order), this.center)this.center.add(toBeProcessed.get(order);/ while (2)初始化簇集合public void initArrayCluster(ArrayList<DataItem> center) / 初始每个簇中的中心点属性this.arrayCluster.clear();/ 把簇集合清空for (int i = 0; i < center.size(); i+) Cluster cluster = new Cluster(i, center

17、.get(i);if (this.center.get(i).getIsDataItem()cluster.addMembers(center.get(i);this.arrayCluster.add(cluster); (3)执行聚类过程(计算距离，把数据对象派分到最相似簇中)public void runCluster(ArrayList<DataItem> center) int beyondIndex = 0;/ 判断数据项属于哪一个簇，初始默认为是0簇Random rd = new Random();/ 随机函数printBeginInfo();/ 打印以此迭代开始前的信

18、息。for (int i = 0; i < toBeProcessed.size(); i+) beyondIndex = 0;boolean isAlreadyExitInCluster = true;/ 标记当前处理的数据对象是否已经存在于某个簇中double minDistance = Tools.calcDistance(toBeProcessed.get(i),center.get(0), 0);int ranIndex = rd.nextInt(center.size();/ 随机产生一个中心点集合的索引for (int j = 0; j < center.size()

19、; j+) / 分别与每一个中心点进行比较if (center.contains(toBeProcessed.get(i)/ 如果正在处理的数据对象存在于中心点集合中，则跳出循环break;isAlreadyExitInCluster = false;if (ranIndex >= center.size()ranIndex = ranIndex % center.size();double correntDistance = Tools.calcDistance(toBeProcessed.get(i), center.get(ranIndex), 0);if (correntDist

20、ance < minDistance) minDistance = correntDistance;beyondIndex = ranIndex;/ 第二个ifranIndex+;/ 第二个forif (!isAlreadyExitInCluster) this.arrayCluster.get(beyondIndex).addMembers(toBeProcessed.get(i);/ 把数据对象加入到对应的簇中/ 第一个forSystem.out.println("第" + this.count + "次迭代完成。");printCluster

21、ingInfo(); (4)迭代过程(产生新的中心点，继续执行聚类过程直至满足终止条件)public void finishCluster() DecimalFormat df = new DecimalFormat("#.000");/ 格式化数据，保留三位小数for (int i = 0; i < NUM; i+) double moveDistance = 0.0;/ 存放各个簇新旧中心点欧几里得距离之和/ 重新计算簇中心点for (int j = 0; j < numOfCluster; j+) boolean isEmptyCluster = true

22、;DataItem newCenterItem;/ 声明新的中心点对象int size = this.arrayCluster.get(j).getMembers().size();double newCenterArea = new doubleNUMOFAREA;/ 计算簇中数据的均值for (int index = 0; index < NUMOFAREA; index+) double tempValue = 0.0;/ 暂存每一列区域值的加和for (int k = 0; k < size; k+) isEmptyCluster = false;tempValue +=

23、this.arrayCluster.get(j).getMembers().get(k).getAreas()index;if (!isEmptyCluster) newCenterAreaindex = Double.valueOf(df.format(tempValue / size); elsebreak;/ 第三个forif (!isEmptyCluster) / 如果簇不为空String name = "cluster" + j;newCenterItem = new DataItem(name, newCenterArea, false);/ 新的簇中心点对象D

24、ataItem oldCenter = 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 * numOfClu

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