聚类k平均算法实验报告.pdf

《聚类k平均算法实验报告.pdf》由会员分享，可在线阅读，更多相关《聚类k平均算法实验报告.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据挖掘实验报告数据挖掘实验报告专业班级学生学号学生实验项目实验类别计算机 2 班101304057周杰实验地点指导教师实验时间邱天生 202郭淼霞郭淼霞实验实验2 2K K平均算法（平均算法（K Kmeansmeans）操作性（）验证性（）设计性（）综合性（）其它（）1.进一步熟悉高级语言编程;2掌握使用 K平均算法的方法；实验目的及要求成 绩 评 定 表类别评 分 标 准积极出勤、遵守纪律主动完上机表现成实验设计任务比较规、基本正确功能达到程序代码实验要求及时递交、填写规实验报告容完整、体现收获说明：说明：Word资料分值得分合计3030 分3030 分4040 分.-评阅教师：评阅教师：

2、日日 期：期：20132013 年年5 5 月月2828 日日实 验容1.算法思想算法思想（1）从 n 个数据对象任意选择 k 个对象作为初始聚类中心；（2）循环（3）到（4）直到每个聚类不再发生变化为止；（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（4）重新计算每个（有变化）聚类的均值（中心对象）。k-means 算法接受输入量 k；然后将 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）

3、来进行计算的。k-means 算法的工作过程说明如下：首先从 n 个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。2 2源程序使用的数据结构源程序使用的数据结构int N;/数据个数int K;/集合个数int*CenterIndex;/初始化质心数组的索引doub

4、le*Center;/质心集合double*CenterCopy;/质心集合副本double*AllData;/数据集合double*Cluster;/簇的集合#includeint*Top;/集合中元素的个数，也会用作栈处理.可修编-.-3.3.源程序源程序#include#include#include int N;/数据个数int K;/集合个数int*CenterIndex;/初始化质心数组的索引double*Center;/质心集合double*CenterCopy;/质心集合副本double*AllData;/数据集合double*Cluster;/簇的集合#includeint*

5、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;elsei-;/如果重复，本次重新随机生成/返回距离最小的质心的序号int GetIndex(double value,double*center)int i=0;int in

6、dex=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,Cen

7、terIndex);/产生随机的 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 置 0for(i

8、=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*cente

9、r1,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;/为质

10、心集合副本申请空间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()/释放申

11、请的空间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)/开始迭代Upda

12、teCluster();/更新各个聚类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;实 验 总 结在这次实验中的难点是：数据结构设置和对算法的理解。初始的聚类中心的不同，对聚类结果没有很大的影响，而对迭代次数有显著的影响。数据的输入顺序不同，同样影响迭代次数，而对聚类结果没有太大的影响。四、实验结果在运行上述源程序使输入数据个数15 和输入族个数 3 及输入的 15 个数据 23、23、45、21、56、71、24、43、47、38、29、59、42、72、93 后得出了如下实验结果：.可修编-