k平均算法实验报告

1、数据挖掘实验报告专业班级计算机2班实验地点邱天生202学生学号101304057指导教师郭淼霞学生姓名周杰实验时间实验项目实验2 k 平均算法（K means ）实验类别操作性（） 验证性（）设计性（）综合性（“）其它（）实 验 目 的 及 要 求1.进步熟悉高级语言编程；2掌握使用K平均算法的方法；成绩评定表类另y评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成实验设计任务30分程序代码比较规范、基本正确 功能达到实验要求30分实验报告及时递交、填写规范 内容完整、体现收获40分说明：评阅教师：日期：2013年5 月28 日实验内容1.算法思想（1） 从n个数据对象任意选择k个对象作为

2、初始聚类中心；（2）循环（3）到（4）直到每个聚类不再发生变化为止；（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根 据最小距离重新对相应对象进行划分；（4） 重新计算每个（有变化）聚类的均值（中心对象）。k-means算法接受输入量k ;然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度 是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。k-means算法的工作过程说明如下：首先从 n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与

3、这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所 有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作 为标准测度函数 k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能 的分开。2 源程序使用的数据结构int N;数据个数int K;集合个数int * Centerin dex;初始化质心数组的索引double * Ce nter;/ 质心集合double * Cen terCopy;/质心集合副本double * AllData;/ 数据集合double * Clus

4、ter;/ 簇的集合 #include<time.h>int * Top;/集合中元素的个数，也会用作栈处理3源程序#in clude<stdlib.h>#i nclude <stdio.h> #i nclude <math.h> int N;/ 数据个数 int K;/ 集合个数 int * Centerin dex;/初始化质心数组的索引double * Ce nter;/ 质心集合 double * Cen terCopy;/质心集合副本double * AllData;/ 数据集合 double * Cluster;/ 簇的集合 #inc

5、lude<time.h>int * Top;/集合中元素的个数，也会用作栈处理随机生成k个数x（0<=x<=n-1）作为起始的质心集合Void CreateRa ndomArray（i nt n, int k,i nt * cen ter）int i=0; int j=0;srand( (un sig ned)time( NULL );for( i=O;i<k;+i)随机生成k个数int a=ra nd()% n;判重重复for(j=0;j<i;j+) if(cen terj=a) break;if(j>=i)cen teri=a; elsei-;如果

6、不重复，加入如果重复，本次重新随机生成返回距离最小的质心的序号* cen ter)int i=0;int in dex=i;最小的质心序号double mi n=fabs(value-ce nteri);for(i=0;i<K;i+)if(fabs(value-ce nteri)<mi n) 距质心最小距离如果比当前距离还小，更新最小的质心序号和距离值in dex=i; min=fabs(value-ce nteri);retur n in dex;/oid CopyCe nter()拷贝质心数组到副本int i=0;for(i=0;i<K;i+)Ce nterCopyi=C

7、e nteri;/oid In itCe nter()初始化质心，随机生成法int i=0;CreateRandomArray(N,K,Centerlndex);/产生随机的 K个<N 的不同的序列for(i=0;i<K;i+)Ce nteri=AIIDataCe nterl ndexi; / prin tf("%f ",Ce nteri); / CopyCe nter();拷贝到质心副本/void AddToCluster(i nt in dex,double value)/ICluster in dexTopi ndex+=value;重新计算簇集合void

8、 UpdateCluster()int i=0;int tin dex;/将所有的集合清空，即将TOP置0for(i=0;i<K;i+)Topi=0;for(i=0;i<N;i+)ti ndex=GetI ndex(AIIDatai,Ce nter);/ AddToCluster(ti ndex,AIIDatai);将对应数据赋值给质心数组 测试用加入一个数据到一个Cluster" ndex这里同进栈操作集合/得到与当前数据最小的质心索引加入到相应的集合中簇集合中的元素加总求平均即可void UpdateCe nter()重新计算质心集合，对每int i=0;int j=

9、0;double sum=0;for(i=0;i<K;i+)sum=0; /计算簇i的元素和for(j=0;j<Topi;j+) sum+=CIusterij;if(Topi>0)如果该簇元素不为空Cen teri=sum/Topi;求其平均值bool lsEqual(double * centerl ,double * center2)判断 2 数组元素是否相等int i;for(i=0;i<K;i+)if(fabs(ce nter1i!=ce nter2i)return false;return true;void Prin t()打印聚合结果int i,j;pri

10、ntf("n");for(i=0;i<K;i+)printf("n第 %d:质心(%f) :n",i+1,Centeri);for(j=0;j<Topi;j+)prin tf("%f ",Clusterij);void In itData()初始化聚类的各种数据int i=0;int a;prin tf("输入数据个数：");scan f("%d",&N);printf("输入簇个数：");scan f("%d",&K);if(

11、K>N)exit(0);为质心集合申请空间为质心集合索引申请空间为质心集合副本申请空间Cen ter= new doubleK; /Cen terI ndex=new in tK;Cen terCopy=new doubleK; /Top=new in tK;AllData=new doubleN; / 为数据集合申请空间为簇集合申请空间Cluster=(double *)malloc(sizeof(double *)*K);/ 初始化K个簇集合 for(i=0;i<K;i+)Clusteri=(double *)malloc(sizeof(double)*N);Topi=0;pr

12、intf("输入 d数据：",N);for(i=0;i<N;i+)sea nf("%d",&(a);AIIDatai=a;In itCe nter();初始化质心集合UpdateCluster();初始化K个簇集合void free()释放申请的空间delete Cen ter;delete Cen terI ndex;delete Cen terCopy;delete Top;delete AllData; free(Cluster);算法描述：K均值算法：给定类的个数 K,将N个对象分到K个类中去，使得类内对象之间的相似性最大，而类之间

13、的相似性最小。*/int mai n()int Flag=1; 迭代标志，若为false,则迭代结束int i=0;In itData();初始化数据/* for(i nt j=O;j<K;j+)测试用prin tf("%f ",Ce nterj);*/while(Flag)/开始迭代UpdateCluster();更新各个聚类UpdateCe nter();更新质心数组if(lsEqual(Ce nter,Ce nterCopy)/如果本次迭代与前次的质心聚合相等，即已收敛，结束退出Flag=0;else/否则将质心副本置为本次迭代得到的的质心集合CopyCe nt

14、er();将质心副本置为本次迭代得到的的质心集合/*i+;prin tf("n%d times",i); /测试用for(i nt j=0;j<K;j+)prin tf("%f ",Ce nterj);*/Prin t();输出结果free();getchar();return 0;实验总结在这次实验中的难点是：数据结构设置和对算法的理解。 初始的聚类中心的 不同，对聚类结果没有很大的影响，而对迭代次数有显著的影响。数据的输入顺 序不同，同样影响迭代次数，而对聚类结果没有太大的影响。四、实验结果在运行上述源程序使输入数据个数15和输入族个数3及输入的15个数据23、23、45、21、56、71、24、43、47、38、29、59、42、72、93 后得出了如下实验结果：ctw ' E:程序语言0曲旳1_即均值旻类期敖诒言版占畑"输入iE数扌居： 23 23 45 21 56 75 24 4347 38 29 59 42 72 93第1组=