k均值聚类报告

K-均值聚类算法报告摘要K-均值是聚类方法中长用的一种划分方法，有很多优点，本文主要对K-均值是聚类方法的产生，工作原理，一般步骤，以及它的源码进行简单的介绍，了解K-均值是聚类！！！（一）课题名称：K-均值聚类(K-meansclustering)（二）课题分析：J.B.MacQueen在1967年提出的K-means算法[22]到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为：K-means算法的特点——采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配：①指定聚类，即指定数据到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。②修改聚类中心。优点：本算法确定的K个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N是数据对象的数目，t是迭代的次数。一般来说，KN，tN。动态聚类方法是模式识别中一种普遍采用的方法，它具有以下3个要点：1：选定某种距离度量作为样本间的相似性度量2：确定某个评价聚类结果质量的准则函数3：给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好的聚类结果处理流程：（1）从n个数据对象任意选择k个对象作为初始聚类中心；（2）循环（3）到（4）直到每个聚类不再发生变化为止；（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（4）重新计算每个（有变化）聚类的均值（中心对象）k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。（三）总体检索思路：利用goole，百度，搜狗等搜索引擎及校内的一些数据库进行相关内容的检索。主要检索内容为K-均值聚类算法的工作原理，一般步骤，源码。（四）检索过程记录：关键词：K-均值聚类算法搜索引擎：百度检索内容：①K-均值聚类算法工作原理②K-均值聚类算法的一般步骤③K-均值聚类算法的源码中文数据库检索：中国知网（）维普网（）万方（）学科范围：信息技术检索词：K-均值聚类算法（五）检索结果分析：1.K-均值聚类算法的工作原理：K-means算法的工作原理：算法首先随机从数据集中选取K个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变化，这标志着已经收敛，因此算法结束。2.K-means聚类算法的一般步骤：处理流程：（1）从n个数据对象任意选择k个对象作为初始聚类中心；（2）循环（3）到（4）直到每个聚类不再发生变化为止；（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（4）重新计算每个（有变化）聚类的均值（中心对象）3.K-均值聚类算法代码#includestdio.h#includemath.h#defineTRUE1#defineFALSE0intN;//数据个数intK;//集合个数int*CenterIndex;//初始化质心数组的索引double*Center;//质心集合double*CenterCopy;//质心集合副本double*AllData;//数据集合double**Cluster;//簇的集合int*Top;//集合中元素的个数，也会用作栈处理//随机生成k个数x(0=x=n-1)作为起始的质心集合voidCreateRandomArray(intn,intk,int*center){inti=0;intj=0;srand((unsigned)time(NULL));for(i=0;ik;++i)//随机生成k个数{inta=rand()%n;//判重for(j=0;ji;j++){if(center[j]==a)//重复{break;}}if(j=i)//如果不重复，加入{center[i]=a;}else{i--;//如果重复，本次重新随机生成}}}//返回距离最小的质心的序号intGetIndex(doublevalue,double*center){inti=0;intindex=i;//最小的质心序号doublemin=fabs(value-center[i]);//距质心最小距离for(i=0;iK;i++){if(fabs(value-center[i])min)//如果比当前距离还小，更新最小的质心序号和距离值{index=i;min=fabs(value-center[i]);}}returnindex;}//拷贝质心数组到副本voidCopyCenter(){inti=0;for(i=0;iK;i++){CenterCopy[i]=Center[i];}}//初始化质心，随机生成法voidInitCenter(){inti=0;CreateRandomArray(N,K,CenterIndex);//产生随机的K个N的不同的序列for(i=0;iK;i++){Center[i]=AllData[CenterIndex[i]];//将对应数据赋值给质心数组}CopyCenter();//拷贝到质心副本}//加入一个数据到一个Cluster[index]集合voidAddToCluster(intindex,doublevalue){Cluster[index][Top[index]++]=value;//这里同进栈操作}//重新计算簇集合voidUpdateCluster(){inti=0;inttindex;//将所有的集合清空，即将TOP置0for(i=0;iK;i++){Top[i]=0;}for(i=0;iN;i++){tindex=GetIndex(AllData[i],Center);//得到与当前数据最小的质心索引AddToCluster(tindex,AllData[i]);//加入到相应的集合中}}//重新计算质心集合，对每一簇集合中的元素加总求平均即可voidUpdateCenter()inti=0;intj=0;doublesum=0;for(i=0;iK;i++){sum=0;//计算簇i的元素和for(j=0;jTop[i];j++){sum+=Cluster[i][j];}if(Top[i]0)//如果该簇元素不为空{Center[i]=sum/Top[i];//求其平均值}}}//判断2数组元素是否相等intIsEqual(double*center1,double*center2){inti;for(i=0;iK;i++){if(fabs(center1[i]!=center2[i])){returnFALSE;}}returnTRUE;}//打印聚合结果voidPrint(){inti,j;printf(--------------------------------------);for(i=0;iK;i++){printf(第%d组:质心（%f）,i,Center[i]);for(j=0;jTop[i];j++){printf(%f,Cluster[i][j]);}}//初始化聚类的各种数据voidInitData(){inti=0;inta;printf(输入数据个数：);scanf(%d,&N);printf(输入簇个数：);scanf(%d,&K);if(KN){exit(0);}Center=(double*)malloc(sizeof(double)*K);//为质心集合申请空间CenterIndex=(int*)malloc(sizeof(int)*K);//为质心集合索引申请空间CenterCopy=(double*)malloc(sizeof(double)*K);//为质心集合副本申请空间Top=(int*)malloc(sizeof(int)*K);AllData=(double*)malloc(sizeof(double)*N);//为数据集合申请空间Cluster=(double**)malloc(sizeof(double*)*K);//为簇集合申请空间//初始化K个簇集合for(i=0;iK;i++){Cluster[i]=(double*)malloc(sizeof(double)*N);Top[i]=0;}printf(输入%d数据：,N);for(i=0;iN;i++){scanf(%d,&(a));AllData[i]=a;}InitCenter();//初始化质心集合UpdateCluster();//初始化K个簇集合}/*算法描述：K均值算法：给定类的个数K，将N个对象分到K个类中去，使得类内对象之间的相似性最大，而类之间的相似性最小。*/main()intFlag=1;//迭代标志，若为false,则迭代结束inti=0;InitData();//初始化数据while(Flag)//开始迭代{UpdateCluster();//更新各个聚类UpdateCenter();//更新质心数组if(IsEqual(Center,CenterCopy))//如果本次迭代与前次的质心聚合相等，即已收敛，结束退出{Flag=0;}else//否则将质心副本置为本次迭代得到的的质心集合{CopyCenter();//将质心副本置为本次迭代得到的的质心集合}}Print();//输出结果getchar();getchar();}（六）评价：本专业开设信息检索课程有利于我们更快更好的获取相关的学术资料，为我们节省了大量时间，可以让我们了解最新的学术动态，更快更好更准确的找到自己需要的资源。本专业还介绍了许多搜索方法，让我们知道在网上可以怎样快速便捷的搜索！！！【附录】附录A《科技信息检索》科学出版社附录Bk-均值聚类算法分类：百度搜索引擎附录Ck均值聚类算法（C语言版）附录Dk均值聚类算法步骤附录F基于K-均值的聚类分析