k均值算法实验报告.doc

课题名称：k均值算法1.前言1.1研究的目的意义及内容在自然科学和社会科学中，存在着大量的分类问题。所谓类，通俗地说，就是指相似元素的集合。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析起源于分类学，在古老的分类学中，人们主要依靠经验和专业知识来实现分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学中，形成了数值分类学，之后又将多元分析的技术引入到数值分类学形成了聚类分析。k-means 算法是接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。1.2检索策略与检索结果1.2.1检索系统(1)维普咨询网(2)百度文库(3)超星图书馆(4)万方知识平台(5)中国知网1.2.2检索词（1）聚类算法；（2）k均值算法；（3）k均值算法原理；（4）k均值算法的源程序；（5）k均值算法处理流程1.2检索结果（1）维普咨询网检索到64条相关信息（2） 万方知识平台检索到72条相关信息2.k均值算法处理流程（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心； （2） 循环（3）到（4）直到每个聚类不再发生变化为止；（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； （4） 重新计算每个（有变化）聚类的均值（中心对象）。 k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 3.k均值算法源程序#include#include #include int N;/数据个数int K;/集合个数int * CenterIndex;/初始化质心数组的索引double * Center;/质心集合double * CenterCopy;/质心集合副本double * AllData;/数据集合double * Cluster;/簇的集合#includeint * Top;/集合中元素的个数，也会用作栈处理/随机生成k个数x(0=x=n-1)作为起始的质心集合void CreateRandomArray(int n, int k,int * center) int i=0; int j=0; srand( (unsigned)time( NULL ) ); for( i=0;ik;+i)/随机生成k个数 int a=rand()%n;/判重 for(j=0;j=i)/如果不重复，加入 centeri=a; else i-;/如果重复，本次重新随机生成 /返回距离最小的质心的序号int GetIndex(double value,double * center) int i=0; int index=i;/最小的质心序号 double min=fabs(value-centeri);/距质心最小距离 for(i=0;iK;i+) if(fabs(value-centeri)min)/如果比当前距离还小，更新最小的质心序号和距离值 index=i; min=fabs(value-centeri); return index; void CopyCenter()/拷贝质心数组到副本 int i=0; for(i=0;iK;i+) CenterCopyi=Centeri;void InitCenter()/初始化质心，随机生成法 int i=0; CreateRandomArray(N,K,CenterIndex);/产生随机的K个N的不同的序列 for(i=0;iK;i+) Centeri=AllDataCenterIndexi;/将对应数据赋值给质心数组/ printf(%f ,Centeri); /测试用 CopyCenter();/拷贝到质心副本void AddToCluster(int index,double value)/加入一个数据到一个Clusterindex集合 ClusterindexTopindex+=value;/这里同进栈操作 /重新计算簇集合void UpdateCluster() int i=0; int tindex; /将所有的集合清空，即将TOP置0 for(i=0;iK;i+) Topi=0; for(i=0;iN;i+) tindex=GetIndex(AllDatai,Center);/得到与当前数据最小的质心索引 AddToCluster(tindex,AllDatai); /加入到相应的集合中 void UpdateCenter()/重新计算质心集合，对每一簇集合中的元素加总求平均即可 int i=0; int j=0; double sum=0; for(i=0;iK;i+) sum=0; /计算簇i的元素和 for(j=0;j0)/如果该簇元素不为空 Centeri=sum/Topi;/求其平均值 bool IsEqual(double * center1 ,double * center2)/判断2数组元素是否相等 int i; for(i=0;iK;i+) if(fabs(center1i!=center2i) return false; return true;void Print()/打印聚合结果 int i,j; printf(n- ); for(i=0;iK;i+) printf(n第%d组: 质心（%f） :n,i+1,Centeri); for(j=0;jN) exit(0); Center=new doubleK; /为质心集合申请空间 CenterIndex=new intK;/为质心集合索引申请空间 CenterCopy=new doubleK; /为质心集合副本申请空间 Top=new intK; AllData=new doubleN; /为数据集合申请空间 Cluster=(double *)malloc(sizeof(double *)*K);/为簇集合申请空间 /初始化K个簇集合 for(i=0;iK;i+) Clusteri=(double *)malloc(sizeof(double)*N); Topi=0; printf(输入%d数据： ,N); for(i=0;iN;i+) scanf(%d,&(a); AllDatai=a; InitCenter();/初始化质心集合 UpdateCluster();/初始化K个簇集合 void free()/释放申请的空间delete Center;delete CenterIndex;delete CenterCopy;delete Top;delete AllData;free(Cluster);/*算法描述：K均值算法： 给定类的个数K，将N个对象分到K个类中去， 使得类内对象之间的相似性最大，而类之间的相似性最小。*/int main() int Flag=1;/迭代标志，若为false,则迭代结束 int i=0; InitData();/初始化数据 /* for(int j=0;jK;j+)/测试用 printf(%f ,Centerj);*/ while(Flag)/开始迭代 UpdateCluster();/更新各个聚类 UpdateCenter();/更新质心数组 if(IsEqual(Center,CenterCopy)/如果本次迭代与前次的质心聚合相等，即已收敛，结束退出 Flag=0; else/否则将质心副本置为本次迭代得到的的质心集合 CopyCenter();/将质心副本置为本次迭代得到的的质心集合 /* i+; printf(n%d ti