数据挖掘实验报告-聚类分析

1数据挖掘实验报告（三）聚类分析姓名：李圣杰班级：计算机1304学号：13116106022一、实验目的1、掌握k-means聚类方法；2、通过自行编程，对三维空间内的点用k-means方法聚类。二、实验设备PC一台，dev-c++5.11三、实验内容1.问题描述：立体空间三维点的聚类.说明：数据放在数据文件中(不得放在程序中)，第一行是数据的个数，以后各行是各个点的x,y,z坐标。2.设计要求读取文本文件数据，并用K-means方法输出聚类中心3.需求分析k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：21kiiiECpmp(1)其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。四、实验步骤Step1.读取数据组，从N个数据对象任意选择k个对象作为初始聚类中心；Step2.循环Step3到Step4直到每个聚类不再发生变化为止；Step3.根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；Step4.重新计算每个（有变化）聚类的均值（中心对象）。代码#includestdlib.h#includestdio.h#includemath.h#includetime.hintK,Vectordim,datasize,seed=1;3float**data,**kmatrix;float*max_column,*min_column;/*创建维数可指定的二维动态数组array[m][n]*/float**array(intm,intn){float**p;inti;p=(float**)malloc(m*sizeof(float*));p[0]=(float*)malloc(m*n*sizeof(float));for(i=1;im;++i)p[i]=p[i-1]+n;returnp;}/*释放二维数组所占用的内存*/voidfreearray(float**p){free(*p);free(p);}voidloaddata(){FILE*fp;inti,j;if((fp=fopen(data.txt,r))==NULL){printf(Cannotopenfile!\n);exit(0);}if(feof(fp)){printf(data.txtisaemptyfile!\n);fclose(fp);exit(0);}if(fscanf(fp,K=%d,Vectordim=%d,datasize=%d\n,&K,&Vectordim,&datasize)!=3){printf(loaderror!\n);fclose(fp);exit(0);}data=array(datasize,Vectordim+1);for(i=0;idatasize;i++){data[i][Vectordim]=0;for(j=0;jVectordim;j++){if(j==(Vectordim-1))fscanf(fp,%f\n,&data[i][j]);elsefscanf(fp,%f,&data[i][j]);/*printf(%f,data[i][j]);*/}}}doubleeuclid_distance(floata[],floatb[],intdim){inti;doublesum=0;for(i=0;idim;i++)sum+=pow(a[i]-b[i],2);returnsqrt(sum);}voidgetmaxmin(float**a){inti,j;max_column=(float*)malloc(sizeof(float)*Vectordim);min_column=(float4*)malloc(sizeof(float)*Vectordim);for(i=0;iVectordim;i++){max_column[i]=a[0][i];min_column[i]=a[0][i];}for(i=0;iVectordim;i++){for(j=1;jdatasize;j++){if(a[j][i]max_column[i])max_column[i]=a[j][i];if(a[j][i]min_column[i])min_column[i]=a[j][i];/*printf(max_column[%d]=%f,min_column[%d]=%f\n,i,max_column[i],i,min_column[i]);*/}}}voidinitializerandom(){seed++;srand((unsigned)time(NULL)+seed);}floatrandomreal(floatLow,floatHigh){return((float)rand()/RAND_MAX)*(High-Low)+Low;}voidK_locations_random(){inti,j;kmatrix=array(K,Vectordim+1);printf(RandomlytheK-locationsareinitializedasfollows:\n);for(i=0;iK;i++){initializerandom();kmatrix[i][Vectordim]=(float)(i+1);printf(location---%d:,i+1);for(j=0;jVectordim;j++){kmatrix[i][j]=randomreal(min_column[i],max_column[i]);printf(%f,,kmatrix[i][j]);}printf(\n);}}intexistemptyclass(){int*empty,i,j,ef;empty=(int*)malloc(sizeof(int)*K);for(i=0;iK;i++)empty[i]=0;for(i=0;idatasize;i++){for(j=1;j=K;j++){if(j==(int)data[i][Vectordim])empty[j-1]++;}}for(i=0,ef=0;iK;i++)if(0==empty[i])ef=1;returnef;}intcluster(){inti,j,flag,eflag=1;doubleclosest,d;for(i=0;idatasize;i++){5closest=euclid_distance(data[i],kmatrix[0],Vectordim);flag=1;for(j=1;jK;j++){d=euclid_distance(data[i],kmatrix[j],Vectordim);if(dclosest){closest=d;flag=j+1;}}if(data[i][Vectordim]!=(float)flag){eflag=0;}data[i][Vectordim]=(float)flag;}returneflag;}voidupdate_k_location(){inti,j,number,m;float*temp;temp=(float*)malloc(sizeof(float)*(Vectordim));for(m=0;mVectordim;m++)temp[m]=0;for(number=0,i=1;i=K;i++){for(m=0;mVectordim;m++)temp[m]=0;for(j=0;jdatasize;j++){if(data[j][Vectordim]==i){number++;for(m=0;mVectordim;m++){temp[m]+=data[j][m];}}}for(m=0;mVectordim;m++){kmatrix[i-1][m]=temp[m]/number;/*printf(%f\n,kmatrix[i-1][m]);*/}}free(temp);}voidoutput(){inti,j,m;/*for(m=0;mdatasize;m++)*//*printf(data[%d][Vectordim]=%f\n,m,data[m][Vectordim]);*/for(i=1;i=K;i++){printf(ThefollowingdataareclusterdasCLASS%d:\n,i);for(j=0;jdatasize;j++){if(data[j][Vectordim]==(float)i){for(m=0;mVectordim;m++)printf(%f,data[j][m]);printf(\n);}}}}voidfreememory(){freearray(kmatrix);freearray(data);free(max_column);free(min_column);}6main(){intend_flag,empty_flag=0;longinttime;loaddata();getmaxmin(data);while(1){K_locations_random();end_flag=cluster();if(existemptyclass()){printf(Thereisaemptyclass!\nSorestart!\n);continue;}time=0;while(!end_flag){if(time1000)break;time++;update_k_location();end_flag=cluster();}empty_flag=existemptyclass();if(empty_flag){printf(Thereisaemptyclass!\nSorestart!\n);continue;}elsebreak;}printf(\nAfter%ldtimescalculation\n,time);output();freememory();}实验数据文件：data.txt用空格分开K=3,Vectordim=3,datasize=15-2522.2-35.3431.2-14.42332.02-2324.44-25.3536.3-33.34-20.227.333-28.22-15.6617.33-23.3326.3-31.3416.3-22.54416.2-32.2212.2-15.2222.11-41.24125.232-35.338-22.2245.2223.55-34.2250.1430.9815.23-30.1120.987-32.515.3-25.22-38.9720.1133.22五、结果截图7