姓名：张金增 学号：200612017081202016 专业：计算机软件与理论 一、引言
数据挖掘技术(Data Mining)是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中 ,发现并提取隐含在其中未知的、可信的、有用的模式的过程 。目前 ,数据挖掘已广泛应用于大中型企业、商业、银行、保险、医学等领域。
聚类是数据挖掘中的一类重要技术 ,是分析数据并从中发现有用信息的一种有效手段。它将物理或抽象对象集合分成相似对象类的过程 ,这些对象与同一个簇中的对象彼此相似，而与其他簇中的对象相异。作为数据挖掘的一种一向功能，聚类分析可以用作独立的工具，获得数据分布的情况，观察每个簇的特征，集中对某些特定的簇做进一步的分析。作为统计学的一个分支和一种无监督的学习方法 ,聚类从数学分析的角度提供了一种准确、细致的分析工具。而K-means算法是属于聚类算法中一种基本的划分方法。 二、K-means算法的基本思想 1、相关定义 定义1 K均值算法
以k为输入参数，把n个对象的集合分为K个簇，使得结果簇内的相似度高，而簇间的相似度低 定义2 欧几里得距离
它的定义如下：
d(i,j)(|xx|2|xx|2...|xx|2)i1j1i2j2ipjp其中i = (xi1, xi2, …, xip)和 j = (xj1, xj2, …, xjp) 是两个 p-维数据对象。 定义3 一个样本点与一个样本集的距离
定义为这个样本点与这个样本集中所有样本点当中最近的距离.则一个样本点X和一个样本集合V 之间的距离定义如下
d(X,V)=min(d(X,Y),Y∈V) 2．算法基本思想 K-means算法的过程：
输入: 簇的个数k以及包含n个数据对象的数据集 输出: 满足方差最小标准的K个聚类 处理流程
(1) 从 n个数据对象中任意选择k个对象作为初始聚类中心.
1
(2)循环下述流程 (3) 到 (4)直到每个聚类不再发生变化为止.
(3)根据每个聚类中所有对象的均值(中心对象)计算样本集中每个对象与这些中心对象的欧几里得距离,并根据最小距离重新对相应对象进行划分. (4)更新聚类均值，即计算每个(有变化)聚类的均值(中心对象).
在K-means算法中,选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率,研究的目的是如何找到与数据在空间分布上相一致的初始聚类中心,对数据进行划分最根本的目的是使得一个聚类中的对象是相似的 ,而不同聚类中的对象是不相似的. 如果用距离表示对象间的相似程度相似的对象间的距离比不相似的对象间的距离要小。如果能够寻找到k个初始中心,它们分别代表了相似程度较大的数据集合, 那么就找到了与数据在空间分布上相一致的初始聚类中心. 三、算法描述
1、K-means算法描述如下：
输入：NumPattern个数据对象集合及簇的个数NumClusters
输出：NumClusters个聚类中心cluster[i].center[j]及NumClusters个聚类数据对象集
合z[i]。
K-means.cpp源程序如下：
#include // DEFINES #define SUCCESS 1 #define FAILURE 0 #define TRUE 1 #define FALSE 0 #define MAXVECTDIM 20 #define MAXPATTERN 20 #define MAXCLUSTER 10 2 char *change(double x, int width)//把字符串x转换成字符串 { char cbuf[255]; char *cp; int i,k; int d,s; cp=fcvt(x,width,&d,&s);/*把浮点数x转换为字符串,d为小数点在串中的位置，s 为 符号标志*/ if (s)//如果x为正数，s为0，如果x为负数，s为非0值 { strcpy(cbuf,\"-\"); } else { strcpy(cbuf,\" \"); } /* endif */ if (d>0) { for (i=0; i strcat(cbuf,\".\"); strcat(cbuf,cp); } else { 3 k=-d; strcat(cbuf,\".\"); for (i=0; i double Center[MAXVECTDIM]; //簇中心 int Member[MAXPATTERN]; //属于这个簇的成员索引 int NumMembers; //一个簇中成员的数目 }; class System {//类system定义 private: double Pattern[MAXPATTERN][MAXVECTDIM+1]; aCluster Cluster[MAXCLUSTER]; int NumPatterns; // 数据集中对象的个数 int SizeVector; // vector的维数 int NumClusters; // 簇的个数 char z[255]; // 保存簇数据对象集合 void DistributeSamples(); // K-means 算法步骤2 int CalcNewClustCenters(); // K-means 算法步骤3 double EucNorm(int, int); // 计算欧几里得距离 int FindClosestCluster(int); //查找距离数据对象最近的簇的索引号 4 public: system(); int LoadPatterns(char *fname); // 加载被分类的数据集 void InitClusters(); //K-means 算法步骤1 void RunKMeans(); // K-means的整个运行过程 void ShowClusters(); // 运行结果在屏幕上显示出来 void SaveClusters(char *fname); // 将运行结果保存到文件名为fname的文件 中 void ShowCenters(); }; void System::ShowCenters(){ int i; printf(\"Cluster centers:\\n\"); for (i=0; i int System::LoadPatterns(char *fname){//从文件名为fname的文件中读出测试数据 FILE *InFilePtr; int i,j; double x; if((InFilePtr = fopen(fname, \"r\")) == NULL) return FAILURE; fscanf(InFilePtr, \"%d\从文件中读出数据对象的个数 fscanf(InFilePtr, \"%d\从文件中读出vector的维数 fscanf(InFilePtr, \"%d\从文件中读出要分的簇的个数 5 for (i=0; i printf(\"Input patterns:\\n\"); for (i=0; i printf(\"\\n--------------------\\n\"); fclose(InFilePtr); return SUCCESS; } void System::InitClusters()//簇中心初始化，随意为每个簇分配一个数据对象，这个程 序我们选择最前面的K个对象作为簇中心值 { int i,j; printf(\"Initial cluster centers:\\n\"); for (i=0; i } /* endfor */ printf(\"\\n\"); 6 } void System::RunKMeans(){//K-means的整个运行过程 int converged;//判断是否收敛 int pass;//迭代的次数 pass=1; converged=FALSE; while (converged==FALSE) {//若簇中心值不在发生变化，循环终止 printf(\"PASS=%d\\n\ DistributeSamples(); converged=CalcNewClustCenters(); ShowCenters(); } /* endwhile */ } double System::EucNorm(int p, int c){ // 计算数据集中的对象p和簇中心c之间的 欧几里得距离 double dist,x; int i; char zout[128]; char znum[40]; strcpy(zout,\"d=sqrt(\"); printf(\"The distance from pattern %d to cluster %d is calculated as:\\n\dist=0; for (i=0; i strcat(zout,\"+\"); dist+=(Cluster[c].Center[i]-Pattern[p][i])*(Cluster[c].Center[i]-Pattern[p][i]); 7 } /* endfor */ printf(\"%s)\\n\return dist; } int System::FindClosestCluster(int pat){//查找距离pat最近的簇的索 引值clustID int i, ClustID; double MinDist, d,e; MinDist =9.9e+99; ClustID=-1; for (i=0; i int i,pat,Clustid,MemberIndex; //清空当前所有簇的数据成员列表 for (i=0; i } for (pat=0; pat MemberIndex=Cluster[Clustid].NumMembers; Cluster[Clustid].Member[MemberIndex]=pat; Cluster[Clustid].NumMembers++; } /* endfor */ } int System::CalcNewClustCenters(){//更新簇中心值 int ConvFlag,VectID,i,j,k; double tmp[MAXVECTDIM]; char xs[255]; char ys[255]; char nc1[20]; char nc2[20]; char *pnc1; char *pnc2; pnc1=&nc1[0]; pnc2=&nc2[0]; ConvFlag=TRUE; printf(\"The new cluster centers are now calculated as:\\n\"); for (i=0; i pnc2中 strcpy(z,\"cluster\"); strcat(z,nc2); strcat(z,\"(\"); 9 strcpy(xs,\"Cluster Center\"); strcat(xs,nc2); strcat(xs,\"(1/\"); strcpy(ys,\"(1/\"); strcat(xs,nc1); strcat(ys,nc1); strcat(xs,\")(\"); strcat(ys,\")(\"); for (j=0; j } /* endfor */ for (j=0; j strcat(z,change(Pattern[VectID][k],3)); strcat(z,\ } else { strcat(ys,change(Pattern[VectID][k],3)); strcat(z,change(Pattern[VectID][k],3)); strcat(z,\")\"); } /* endif */ } /* endfor */ if(j } else { strcat(xs,\")\"); strcat(ys,\")\"); } } /* endfor */ for (k=0; k void System::ShowClusters(){ int cl; for (cl=0; cl cl,Cluster[cl].Center[0],Cluster[cl].Center[1]); } /* endfor */ } void System::SaveClusters(char *fname){ } void main(int argc, char *argv[]) {//主程序 System kmeans; if (argc<2) { 11 printf(\"USAGE: KMEANS PATTERN_FILE\\n\"); exit(0); } if (kmeans.LoadPatterns(argv[1])==FAILURE ){ printf(\"UNABLE TO READ PATTERN_FILE:%s\\n\ exit(0); } kmeans.InitClusters(); kmeans.RunKMeans(); kmeans.ShowClusters(); } 2、K-means算法输入测试数据，将这些数据存放在文本文件中，测试数据的格式如下： NPat -数据集中对象的个数（int） SizeVect - 对象的维数（int） NClust - 簇的个数（int） vect[1,1] ... vect[1,SizeVect] - vector 1 (real) vect[2,1] ... vect[2,SizeVect] - vector 2 (real) . . . . . . vect[NPat,1] ... vect[NPat,SizeVector] - vector N (real) 例如： 18 2 2 0.0 0.0 1.0 0.0 0.0 1.0 2.0 1.0 1.0 2.0 2.0 2.0 12 2.0 0.0 0.0 2.0 7.0 6.0 7.0 7.0 7.0 8.0 8.0 6.0 8.0 7.0 8.0 8.0 8.0 9.0 9.0 7.0 9.0 8.0 9.0 9.0 四、改进后的K-meams算法 K-means从不同的初始聚类中心出发会得到不同的聚类结果且准确率也不一样， 通常是从n个数据对象中随机选择K个对象作为初始聚类中心，然后进行迭代操作。这样就使得产生的聚类结果具有很大不确定性 ，如何选择初始聚类中心点成了影响最后聚类结果的重要因素。改进后的算法对随机选择初始聚类中心的方式进行了改进， 尽量使最初的初始聚类中心在空间分布上与数据实际的分布相一致。 为了减小聚类结果对初值的依赖性 ,提高聚类的稳定性 ,采用下面的方法可以获得较优的初始聚类中心。 改进后的算法仍然采用欧几里得距离计算一个对象与一个对象集之间的距离，假设数据集D中有n个样本 将其聚为K类,m的初值为1. 改进算法描述如下: (1)计算任意两个样本间的距离d(X,Y)，找到集合D中距离最近的两个点, 形成集合Am(1≤m≤k,从集合 D中删除这两个点. (2)在D中找到距离集合Am 最近的点 将其加入集合Am并从集合D中删除 (3)重复第(2)步直到集合中的样本点个数大于等于αn/k(0<α<1) (4)如果m 13 α的取值因实验数据不同而有所不同 . α的取值过小则可能使几个初始聚类中心点在同一区域得到. α的取值过大则可能使初始聚类中心点偏离密集区域 从实验的情况来看取0.75时效果是比较好的 五、 实验结果及分析 1、实验结果 2、性能分析 该算法中数据集对象的个数为NumPatterns,聚类数为 Numclusters, sizevector 是数据对象的维数,则一次迭代的时间耗费由三部分组成:将每一个数据对象归到离它最近的聚类中心所在的类(步骤二) ,需要时间 O(NumPatterns*Numclusters* sizevector)，新类产生以后计算新的聚类中心所需的时间 O (NumPatterns* sizevector),而迭代次数则由数据集大小、聚类数以及数据分布情况决定,算法总的时间复杂度为O(NumPatterns*Numclusters* sizevector)。 该算法试图确定最小化欧几里得距离函数的K个划分，当结果是紧凑的，并且簇与簇之间明显分离时，它的效果较好。对于处理大数据集，该算法是相对可伸缩的和有效率的。该算法经常终止于局部最优解。k-means算法只有当簇均值有定义的情况下才能使用，在某些应用中，例如当涉及具有分类属性的数据时，均值可能无定义。用户必须事先给出要生成的簇的数目K可以算是该方法的一个缺点。K-means方法不适合于发现非凸面形状的簇，或者大小差别很大的簇。此外，它对于噪声和离群点数据是敏感的，因为少量的这类数据能够对均值产生极大的影响。 14 实验表明 ,如果各簇之间区别明显且数据分布稠密 ,则该方法比较有效;但是如果各簇的形状和大小差别很大 ,为使欧几里得距离值达到最小 ,有可能出现将大的聚类簇分割的现象. 从实验的结果来看，随机选取样本点作为初始聚类中心聚类准确率不稳定，平均准确率较低 ，用于实际的数据聚类效果不会好。该算法改进后的K-means算法能够得到较高且稳定的准确率可以用于对实际数据的聚类。 六、 结论 K-means算法是一种常用的聚类方法,本文给出了一种动态聚类K-means算法的算法描述及实验结果， 但随机初始选取聚类中心的方式限制了K-means划分方法的的性能。然后对该算法进行了改进， 改进后方法根据数据的自然分布选取初始聚类中心 ，实验表明改进后的方法具有较高的聚类准确率。 参考文献 1．（加）jiawei Han,Micheline Kamber著；范明，孟小峰译.数据挖掘：概念与技术(第 2版).北京：机械工业出版社，2007.3 2. 钱能. C++程序设计教程. 清华大学出版社. 2005年9月 3. 谭浩强. C++程序设计清华大学出版社. 2004年7月 4. 林俊杰. 新一代Visual C++ 2005程序设计 .清华大学出版社.2006年11月 5. 张玉芳 ,毛嘉莉 ,熊忠阳. 一种改进的K-means算法. 计算机应用第23卷期第8期 . 2003.8 6． 何兴元. 用户兴趣实例模型与K-means算法的改进. 重庆师范大学学报第23卷第2期. 2006.6 7. 万小军; 杨建武; 陈晓鸥 . Web文档聚类中K-means算法的改进. 计算机工程. 2003年 02期 8. 袁方,孟增辉,于戈. 对k-means聚类算法的改进计算机工程与应用 . 2004年 36期 9. 吕强; 俞金寿; 基于混合遗传算法的K-Means最优聚类算法.华东理工大学学报. 2005年 02期 10． 谭勇, 荣秋生. 一个基于K-means的聚类算法的实现.湖北民族学院学报(自然科学版) 2004年 01期 11．尉景辉,何丕廉,孙越恒. 基于K-Means的文本层次聚类算法研究计算机应用. 2005年 10期 12． 杨芳,湛燕, 田学东, 郭宝兰. 使用遗传算法实现K-means聚类算法的K值选择. 15 微机发展. 2003年 01期 16 因篇幅问题不能全部显示，请点此查看更多更全内容