(聚类)k平均算法实验报告

数据挖掘实验报告专业班级计算机2班实验地点邱天生202学生学号101304057指导教师郭淼霞学生姓名周杰实验时间实验项目实验2 K平均算法（Kmeans）实验类别操作性（） 验证性（） 设计性（） 综合性（ ） 其它（ ）实验目的及要求1.进一步熟悉高级语言编程;2掌握使用K平均算法的方法；成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律主动完成实验设计任务30分程序代码比较规范、基本正确功能达到实验要求30分实验报告及时递交、填写规范内容完整、体现收获40分说明： 评阅教师： 日 期： 2013 年 5 月 28 日实 验 内 容1. 算法思想（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心； （2） 循环（3）到（4）直到每个聚类不再发生变化为止； （3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； （4） 重新计算每个（有变化）聚类的均值（中心对象）。 k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。2 源程序使用的数据结构int N;/数据个数int K;/集合个数int * CenterIndex;/初始化质心数组的索引double * Center;/质心集合double * CenterCopy;/质心集合副本double * AllData;/数据集合double * Cluster;/簇的集合#includeint * Top;/集合中元素的个数，也会用作栈处理3.源程序#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 times,i); /测试用 for(int j=0;jK;j+) printf(%f ,Centerj);*/ Print();/输出结果 free(); getchar(); return 0;实 验 总 结在这