K-means实验报告.doc

人工智能大作业 目 录1. 问题描述22. 设计要求23. 需求分析34. 详细设计35. 测试及运行结果46. 程序源码及注释57. 课程设计心得体会151.问题描述 k-means算法是根据聚类中的均值进行聚类划分的聚类算法。 输入：聚类个数k，以及包含n个数据对象的数据。 输出：满足方差最小标准的k个聚类。处理流程：Step 1. 从n个数据对象任意选择k个对象作为初始聚类中心；Step 2. 循环Step 3到Step 4直到每个聚类不再发生变化为止；Step 3. 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；Step 4. 重新计算每个（有变化）聚类的均值（中心对象）k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： (1)其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。2.设计要求 首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然 后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。 输入：聚类个数k，以及包含 n个数据对象的数据库。 输出：满足方差最小标准的k个聚类3.需求分析 K-Mean 是一种分割式分群方法，其主要目标是要在大量高纬的资料点中找出具有代表性的资料点；这些资料点可以称为群中心，代表点；然后再根据这些群中心，进行后续的处理，这些处理可以包含1 ）资料压缩：以少数的资料点来代表大量的资料，达到资料压缩的功能；2 ）资料分类：以少数代表点来代表特点类别的资料，可以降低资料量及计算量； 分割式分群法的目的是希望尽量減小每个群聚中，每一点与群中心的距离平方差（square error）。 假設我们現在有一組包含c个群聚的資料，其中第 k 个群聚可以用集合 Gk來表示，假设 Gk包含nk个資料 x1, x2, , xnk），此群聚中心为yk，则该群聚的平方差 ek可以定义为： ek = S i |xi-yk|2 ，其中 xi是属于第 k 群的资料点。而这c个群聚的总和平方差E便是每个群聚的平方差总和： E = S k=1c ek我们分群的方法，就改成是一个最佳化的問題，換句话說，我們要如何选取 c 个群聚以及相关的群中心，使得 E 的值为最小。4.详细设计 k-means算法是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。此算法以k为参数，把n 个对象分为k个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。此算法首先随机选 择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类 的新质心。重复上述过程，直到准则函数会聚。k-means算法是一种较典型的逐点修改迭代的动态聚类算法，其要点是以误差平方和为准则函数。逐点修改类 中心：一个象元样本按某一原则，归属于某一组类后，就要重新计算这个组类的均值，并且以新的均值作为凝聚中心点进行下一次象元素聚类；逐批修改类中心：在 全部象元样本按某一组的类中心分类之后，再计算修改各类的均值，作为下一次分类的凝聚中心点。 k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means算法把N个点聚集成K个组合的算法，要求任意输入K各对象作为初始中心点，这个的最大疑问就是怎么能够通过这随便选择的K个点来达到满足要求的K个组合呢。 K-means算法其实每次迭代都会改变中心，也就是初始的K各对象作为中心点在每一次迭代后都会更新。首先以这K各顶点作为初始K个聚类的中心顶点，第一轮计算所有的其他顶点与这个K个顶点的相似度，取相似度最大的或者说与这K个顶点中某个顶点距离最近的顶点加入这个顶点所代表的cluster中，注意在第一轮检测所有顶点的距离并判断其属于哪个簇的过程中，这K各簇的中心仍然是以这K个顶点作为代表的。 第一轮计算完毕之后，相当于形成了以这K个顶点为中心的K个聚类，此时计算这K个聚类的聚集度，即各个顶点与其中心顶点的距离和作为考察条件，在进行下一轮的迭代的时候，中心顶点就变了，此时就变成第一轮生成的K个聚类的中心顶点作为新的中心顶点并按照第一轮迭代的方法进行重新聚类，并计算各个聚类的聚合度，当聚合度不变的时候或者定义了最大迭代次数的时候，算法表示运算完毕。5.测试及运行结果0.49, 0.29, 0.48, 0.5, 0.56, 0.24, 0.350.07, 0.4, 0.48, 0.5, 0.54, 0.35, 0.440.56, 0.4, 0.48, 0.5, 0.49, 0.37, 0.460.59, 0.49, 0.48, 0.5, 0.52, 0.45, 0.360.23, 0.32, 0.48, 0.5, 0.55, 0.25, 0.350.67, 0.39, 0.48, 0.5, 0.36, 0.38, 0.460.29, 0.28, 0.48, 0.5, 0.44, 0.23, 0.340.21, 0.34, 0.48, 0.5, 0.51, 0.28, 0.39重复聚类次数:10分类正确率:78.27381%选择的下标如下:19 180 213 220 230 236 266 329 分类结果列表:222626226.程序源码及注释/* * K-Means聚类的主程序类*/public class K_Means public K_Means() / TODO 自动生成构造函数存根clusterList=new ClusterSet();dataSet=new Matrix();classData=new ArrayList();static double squareDistance(PointND p1,PointND p2)if(p1.dimension=p2.dimension)double distance=0.0;for(int i=0;ip1.dimension;i+)double p1p=p1.pointND.get(i);double p2p=p2.pointND.get(i);distance+=Math.pow(p1p-p2p),2 );return distance;return -1.0;/* * 从外部数据文件中构造Matrix数据集 * param dataFile 外部数据文件,文件中的每一行中数据间使用逗号分隔 * return Matrix对象数据集 * throws IOException */private Matrix buildMatrix(File dataFile) throws IOExceptionMatrix matrix=new Matrix();ArrayList rows=matrix.rows;FileInputStream fin=new FileInputStream(dataFile);BufferedReader reader=new BufferedReader(new InputStreamReader(fin);String line=reader.readLine();String items=line.split( );matrix.setWidth(items.length);/读取文件中的每一行while(line!=null)items=line.split(,);DataItem row=new DataItem();PointND p=row.rowdata; /每一行为一个N维坐标点ArrayList points=p.pointND;/将每个数据转为浮点型for(int i=0;iitems.length;i+)points.add(Double.parseDouble(itemsi);rows.add(row);line=reader.readLine();matrix.setHeight();reader.close();return matrix;/* * 由Matrix数据集对象初始化簇类列表 * 使用随机选择的方法 * param theDataSet Matrix数据集 * param num 簇类数目 * return */private ClusterSet initClusterSet(Matrix theDataSet,int num)return randomInit(theDataSet,num);/return this.bestInit(dataSet,num);/* * 随机选择k个数据项,作为k个簇类的中心 * param theDataSet Matrix数据集对象 * param num 簇类个数 * return 簇类列表 */private ClusterSet randomInit(Matrix theDataSet,int num)/哈希集,记录生成的下标HashSet ht=new HashSet();ClusterSet newClusterList=new ClusterSet();int range=theDataSet.height;ArrayList rows=theDataSet.rows;/System.out.println(随机选择+num+个数据项构造簇集.);/随机选择法int index=(int)(range*Math.random();ht.add(index); /生成num个簇类for(int i=0;inum;i+) index=(int)(range*Math.random(); /保证不会生成两个相同的下标 while(ht.contains(index) index=(int)(range*Math.random(); goodIndexesi=index; ht.add(index);/int index=i;/System.out.print(index+ );DataItem row=rows.get(index);PointND center=row.rowdata;Cluster clus=new Cluster(center);newClusterList.clusterList.add(clus);newClusterList.setCount();return newClusterList;/* * 对数组进行简单的插入排序 * param array * return */private int sortArray(int array)for(int i=1;i0&tmparrayj-1;j-)arrayj=arrayj-1;arrayj=tmp;return array;/* * 聚类过程 * param clusterList 簇集列表 * param theDataSet 数据集 */private void clustering(ClusterSet clusterList,Matrix theDataSet)ArrayList rows=theDataSet.rows;/数据集的数据行列表 /对于每一个数据行,找出最接近它的簇类,增加此簇类的成员数目,/同时减少上一次聚类时最接近这个数据行的簇类的成员数目for(int i=0;irows.size();i+)DataItem row=rows.get(i);Cluster oldNeighbor=row.mostNearestCluster; /上一次聚类最接近的簇类row.setNeighbors(clusterList);Cluster cluster=row.findMostNearestNeighbor(); /新的最接近的簇类PointND rowdata=row.rowdata;/将数据添加到最接近的簇集中ArrayList memList=cluster.memberList;memList.add(rowdata);cluster.counts+;/从上次最接近的簇类中删除数据 /oldNeighbor为空时表示第一次聚类if(oldNeighbor!=null)ArrayList oldmemList=oldNeighbor.memberList;oldmemList.remove(rowdata);oldNeighbor.counts-; /int c=oldNeighbor.counts;/* * K-Means聚类的接口 * 调用聚类过程方法,当所有簇类的平均值不再改变时停止 * param clusterList 簇类列表 * param dataSet 数据集 */private void kMeansClustering(ClusterSet clusterList,Matrix theDataSet)/首先进行第一次聚类this.clustering(clusterList, theDataSet);K_Means.repeatCounts+; /记录聚类次数ArrayList cluList=clusterList.clusterList;int size=cluList.size();int noChangeCounts=0;for(int i=0;icluList.size();i+)Cluster atomClu=cluList.get(i);/更新簇的中心,如果中心不改变,则计数增1if(atomClu.noChange()noChangeCounts+;/所有簇类的平均值不再改变时结束while(noChangeCounts!=size)noChangeCounts=0;this.clustering(clusterList, theDataSet);cluList=clusterList.clusterList;for(int i=0;icluList.size();i+)Cluster atomClu=cluList.get(i);/更新簇的平均值if(atomClu.noChange()noChangeCounts+;size=cluList.size();/累计重复聚类次数K_Means.repeatCounts+;/* * 根据聚类结果对数据集分类 * param dataSet 数据集 */private void classify(Matrix theDataSet)ArrayList rows=theDataSet.rows;for(int i=0;irows.size();i+)DataItem rowdata=rows.get(i);ClusterSet neighbors=rowdata.neighborClusters;Cluster cluster=rowdata.mostNearestCluster;/最接近簇类在簇集列表中的下标int labelIndex=neighbors.clusterList.indexOf(cluster);labelIndex+;/标记类标识rowdata.setLabel(+labelIndex);/* * 计算分类准确度 * param dataSet 要测试的数据集 * throws IOException */private void checkClassification(Matrix theDataSet) throws IOException/System.out.println(重复聚类次数:+K_Means.repeatCounts);ArrayList rows=theDataSet.rows;/计算分类正确率int origin=0; /起始下标int correctCount=0; /正确分类的数据行数int groupCount; /组的成员数int tmp; /存储类包含的成员数目for(int i=0;iclassData.size();i+) groupCount=classData.get(i); tmp=new intclassData.size();/判别每一个组中的正确分类的元素个数for(int j=origin;jorigin+groupCount;j+)DataItem item=rows.get(j);int label=Integer.parseInt(item.cLabel);tmplabel-1+; /相应的类计数增1/找出数组中的最大元素,以这个元素作为这个组的类计数int maxValue=0;for(int k=0;kmaxValue)maxValue=tmpk;correctCount+=maxValue;origin+=groupCount; this.correctPercent=(float)correctCount/rows.size(); /保存分类说明及结果 if(this.correctPercentborder) System.out.println(重复聚类次数:+K_Means.repeatCounts); System.out.println(分类正确率:+this.correctPercent*100+%); this.saveFile(); /float correctPercent=(float)correctCount/rows.size();/System.out.println(分类正确率:+this.correctPercent*100+%);/* * 计算分类准确度的公用接口 * throws IOException */public void checkClassification() throws IOExceptionthis.checkClassification(this.dataSet);/* * 保存分类文件 * throws IOException */private void saveFile() throws IOExceptionSystem.out.println(保存分类文件.);File classFile=new File(class.txt);if(classFile.exists()classFile.delete();FileOutputStream fout=new FileOutputStream(classFile);PrintWriter pWriter=new PrintWriter(fout);ArrayList rows=this.dataSet.rows;pWriter.println(重复聚类次数:+K_Means.repeatCounts);pWriter.println(分类正确率:+this.correctPercent*100+%);pWriter.println(选择的下标如下:);/对数组排序goodIndexes=this.sortArray(goodIndexes);for(int i=0;igoodIndexes.length;i+)pWriter.write(goodIndexesi+ );pWriter.println();pWriter.println(分类结果列表:);for(int i=0;irows.size();i+)DataItem item=rows.get(i);pWriter.println(item.cLabel);pWriter.flush();pWriter.close();/* * 对类文件进行归类 * param classFile 类文件 * param classData 归类表 * return * throws IOException */private ArrayList buildClassData(File classFile,ArrayList classData) throws IOExceptionFileInputStream fin=new FileInputStream(classFile);BufferedReader reader=new BufferedReader(new InputStreamReader(fin);String line=reader.readLine();int label,oldLabel;int labelCount=0;label=Integer.parseInt(line); /第一个标识oldLabel=label; /下一行的标识/int elementCount=0; /classData的大小是Ecoli类文件中类的个数,每一个单元存的是属于该类的行数while(true)/elementCount+;label=Integer.parseInt(line);if(label!=oldLabel)classData.add(labelCount);/记下属于这个类的个数labelCount=1; /找到第一个新的类标号else/当前一个标识和下一个标识相等时,计数增1labelCount+; line=reader.readLine(); if(line=null) classData.add(labelCount); break; oldLabel=label; /System.out.println(行数:+elementCount);reader.close();return classData;/* * 对类文件进行归类 * param classFile 类文件 * throws IOException */public void buildClassData(File classFile) throws IOExceptionclassData=this.b