数据挖掘聚类问题(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 fragrans 是植物名称(abronia是科属，fragrans 是名称) ，从az 一直到wy 是该植物的分布区域，采用缩写形式表示，如az 代表的是美国Arizona 州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。
1.2任务要求
聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。
2. 数据预处理
2.1数据清理
所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如：
①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi
②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr
上述数据中第①行给出了所有属于abelmoschus 这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus 科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集
合。在聚类过程中第 行数据是无用的，因此要对其进行清理。
2.2数据变换
本实验是依据植物的分布区域进行聚类，所给数据集中的分布区域是字符串形式，不适合进行聚类，因此将其变换成适合聚类的数值形式。具体思想如下：
数据集中总共包含68个区域，每一种植物的分布区域是这68个区域中的一部分。本实验中将68个区域看成是数据对象的68个属性，这68个属性是二元类型的变量，其值只能去0或者1。步骤如下：
1. 把68个区域按一定顺序存放在字符串数组(记为str) 中(顺序可以自己定，确定后不能改变) 。
2. 为数据集中的每个数据对象设置一个长度为68字符串数组，初始元素值全为0。将数据对象的分布区域逐个与str 中的所有元素比较。如果存在于str 中下标i 的位置，就将该数据对象的字符串数组的第i 位置为1。
例如，一个数据对象为：abies fraseri,ga,nc,tn,va。其分布区域包含ga,nc,tn 和va 四个地区，将这四个地区逐个与str 中全部68个元素比较。假设这四个地区分别存在于str 中的第0,1,2,3位置，则将为该数据对象设置的字符串数组中第0,1,2,3位置全部置为1。
★数据预处理代码(包括数据清理和数据变换) ： public ArrayList getRaw_DataSet() {
ArrayList raw_dataSet = new ArrayList();// 定义集合存BufferedReader bufferedReader = 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 ) { } e.printStackTrace(); if (isRightData(data)) raw_dataSet.add(data); 储从本地获取的数据 } catch (Exception e) { } else
this . isFileExit = false ; return raw_dataSet; }// getRaw_DataSet,从本地 public ArrayList getFinished_DataSet() {// 获取经过预处理，用来 } public boolean isRightData(String data) {// 筛选出合适的数据 ArrayList tempArrayList = new ArrayList(); tempArrayList = spilt(data, ' '); if (tempArrayList.size() finished_DataSet = new ArrayList(); ArrayList temp_DataSet = this .getRaw_DataSet(); for (int i = 0; i eachRomItem = null ; eachRomItem = this .spilt(temp_DataSet.get(i), ',' ); // 除去"," 后的DataItem data_Item = new DataItem(eachRomItem, true ); finished_DataSet.add(data_Item); 进行聚类的数据 每一行数据 }// for return finished_DataSet; }// isRightData,筛选出合适的数据 public ArrayList spilt(String str, char ch) { ArrayList words = new ArrayList();// 用来存放找到的单词 } int beginIndex = 0; for (int i = 0; i
3. 聚类分析
3.1 算法描述
本实验采用了聚类分析中常用的K 均值(K-Means)算法。该算法思想如下： 算法：K 均值。用于划分的K 均值算法，每个簇的中心用簇中对象的均值表示。 输入：
■k ：簇的属目
■D ：包含n 个对象的数据集。
输出：k 个簇的集合。
方法：
(1)从D 中任意选择k 个对象作为初始簇中心；
(2)repeat
(3) 根据簇中对象的均值，将每个对象(再) 指派到最相似的簇；
(4) 更新簇均值，既计算每个簇中对象的均值；
(5)until 不再发生变化
根据上述算法，结合本实验实际情况和数据集特征给出程序的执行流程图：
图2 程序执行流程
针对上面的流程图，有几点说明：
1.数据预处理主要包括前述数据清理和数据变换，最终生成用于聚类分析的数据集。
2.簇的个数k 由用户指定，k 越大聚类过程耗时越久。
3.图中“最相似”意思就是距离中心点距离最近，本实验中采用欧几里得距离，其定义如下：
d (i , j ) =x i 1-x j 1) +(x i 2-x j 2) +... +(x in -x jn ) 222
其中i =(x i 1, x i 2,..., x in ) 和j =(x j 1, x j 2,... x jn ) 是两个n 维数据对象。在本实验中，
x i 1和x j 1分别代表为i,j 两个数据对象设置的字符串数组(参看2.2) 中下标为1
的元素值，此处n 为68。
4.流程图中的终止条件指的是：前后两次中心点之间的距离(仍然用欧几里得距离) 是否小于设定的值。例如，第n 次迭代完成后重新生成了k 个新的中心点，计算k 个新中心点与k 个旧的中心点距离之和并将结果与设定的值比较，若小于设定值则终止迭代，聚类完成，否则继续迭代。
3.2 算法实现
图3 代码文件的组织结构
上图是本实验源码的组织结构，该项目包含五个Java 类。每个类的功能描述如下： ◆Cluster.java 类 该类定义了簇的结构，包含簇标志，簇成员和簇中心点三个字段。该类的每一个实例对应于聚类过程中的一个簇。
◆DataItem.java 类 该类定义了数据对象的结构，主要包含数据对象名称(即植物名称) 和数据对象字符串数组(即植物的分布区域) 。该类的每一个实例对应于数据集中
的一个数据对象。
◆Main.java 类 该类是程序的核心类，主要功能是执行聚类过程，包括中心点的选取与更新，计算各个数据对象与中心点之间的距离并把其派分到最相似的簇等。
◆ReadData.java 类 该类主要功能是生成聚类过程适用的数据集，包括读取文件，数据预处理等。
◆Tools.java 类 该类是一个工具类，其中定义了多个程序中使用到的静态方法。 ★Mian.java 类中的核心代码：
(1) 随机选取中心点
public void setCenter_ran() {// 第一次，从数据集中随机选取中心点 } beginTime = System.currentTimeMillis (); System. out .println(" 聚类过程开始, 开始于:" + Tools.currentTime ()); Random ran = new Random(); int order = 0;// 随机选取中心点 while (this . center .size()
(2)初始化簇集合
public void initArrayCluster(ArrayList center) {// 初始每个簇中 } this . arrayCluster .clear();// 把簇集合清空 for (int i = 0; i
(3)执行聚类过程(计算距离，把数据对象派分到最相似簇中)
public void runCluster(ArrayList center) {
int beyondIndex = 0;// 判断数据项属于哪一个簇，初始默认为是0簇 Random rd = new Random();// 随机函数 printBeginInfo();// 打印以此迭代开始前的信息。 for (int i = 0; i
已经存在于某个簇中
} double minDistance = Tools.calcDistance (toBeProcessed .get(i), center.get(0), 0); int ranIndex = rd.nextInt(center.size());// 随机产生一个中心点集合for (int j = 0; j = center.size()) ranIndex = ranIndex % center.size(); toBeProcessed .get(i), center.get(ranIndex), 0); double correntDistance = Tools.calcDistance ( if (correntDistance
(4)迭代过程(产生新的中心点，继续执行聚类过程直至满足终止条件)
public void finishCluster() {
DecimalFormat df = new DecimalFormat("##.000"); // 格式化数据，保留三位for (int i = 0; i
点
} for (int k = 0; k
3.3 问题与改进
聚类分析要求不同簇之间的距离尽可能大，初始随机选取的中心点并不能保证不同中心点之间的距离尽可能远，本程序对算法进行改进，在随机选取中心点时要求与已经选取的中心点之间的距离大于设定值。这样做保证了随机选取的中心点相对比较分散，提高了聚类效果。主要代码如下：
public static boolean isProCener(DataItem centerItem,// 判断是不是合适的中 ArrayList center) { 心点
} if (center.size() > 0) {// 如果当前的中心点集合不为空
} return true ; for (int i = 0; i
4. 开发与运行环境配置
●操作系统：Windows 7
●开发工具：Eclipse
●开发语言：Java
●CPU 频率：2.2GHz
●内存：3.5GB
两种运行方式：①解压源程序，将PlantsClustering 工程导入Eclipse 即可运行；②直接运行打包生成的exe 文件。两种方式均要求电脑上安装有JDK1.5或更高版本。
5. 程序运行情况分析
5.1 运行截图
图4 指定数据文件并输入聚类簇数
程序运行开始时需要用户指定数据文件的路径，不指定的话默认是D 盘根目录下的plants.data.txt 文件。之后需要用户输入聚类产生的簇数，簇数介于1到100之间。
图5 迭代过程，输出中心点信息
每次迭代会输出本次迭代的中心点信息。上图是第一次迭代的部分中心点信息(总共有50个中心点) 。
图6 第一次迭代后簇的信息 图7 簇的信息和终止条件的判定
一次迭代完成后会输出本次迭代后各簇的信息并计算新旧中心点的移动距
离，与设定的值比较，判定是否继续迭代。
图8 把簇的信息保存到本地
满足终止条件，迭代结束，此时会在D:\DataMining\目录下生成保存各个簇信息的文件，里面是该簇中包含的数据对象。
5.2 聚类效果分析
聚类分析要求得到的簇之间相异度尽可能大，簇内的数据对象相异度尽可能小。本程序会在聚类分析完成后会输出各簇内的平均距离和簇间平均距离，作为对聚类效果评判的参考。如下截图：
图9 聚类效果
5.3 总结
K 均值聚类算法的效果与簇数和初始中心点有关。初始中心点选取应尽可能分散。簇数越多聚类效果越好，但同时程序运行的时间开销也会加大，平衡二者找到一个合适的k 是该算法的一个重点。