C均值聚类实验报告

C均值聚类实验报告一、C均值聚类的算法原理聚类分析是指事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）聚类准则函数在样本相似性度量的基础上，聚类分析还需要一定的准则函数，才能把真正属于同一类的样本聚合成一个类的子集，而把不同类的样本分离开来。如果聚类准则函数选得好，聚类质量就会高。同时，聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以优化结果。在重复优化中，可以改变相似性度量，也可以选用新的聚类准则。误差平方和准则（最常用的）假定有混合样本集，采用某种相似性度量被聚合成c个分离开的子集，每个子集是一个类，它们分别包含个样本。为了衡量聚类的质量，采用误差平方和聚类准则函数式中为类中样本的均值：是c个子集合的中心，可以用来代表c个类。误差平方和聚类准则函数是样本与集合中心的函数。在样本集X给定的情况下，其取值取决于c个集合“中心”。它描述n个试验样本聚合成c个类时，所产生的总误差平方和越小越好。误差平方和准则适用于各类样本比较密集且样本数目悬殊不大的样本分布。C-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标数最小化，从而使生成的簇尽可能地紧凑和独立。首先，随机选取k个对象作为初始的k个簇的质心；然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。12{,,...,}nXxxxXcXXX,.....,,21cnnn,......,,21cJcjnkjkcjmxJ112||||jmjnjjjjxnm11cj,....,2,1jmcJcJ这个迭代重定位过程不断重复，直到目标函数最小化为止。C－均值聚类算法使用的聚类准则函数是误差平方和准则：为了使聚类结果优化，应该使准则最小化。二、C均值聚类的实现步骤C－均值算法步骤：①给出n个混合样本，令，表示迭代运算次数，选取c个初始聚合中心②计算每个样本与聚合中心的距离:若则③令计算新的集合中心：计算误差平方和值：④对每个聚合中的每个样本，计算：表示减少的部分。表示增加的部分：若，则把样本移到聚合中心中，并修改聚合中心和值。⑤判断：若则，返回④。否则，算法结束。cJcJ1I(1),1,2,...,;jZjc(,()),1,2,...,;1,2,...,.kjDxZIknjc1,2,...,(,())min{(,()),1,2,...,},kikjjcDxZIDxZIkn;kix12,II()11(2),1,2,...,;jnjjkkjZxjcncJcjnkiikcjZxJ112)(||)2(||)2(()2||()||,1,2,...1iiiikiinxZIicniicJ()2||()||,1,2,...,1jiijkjjnxZIjcjinijcJ}{minijijiliiil)(ikxlcJ])([11)()1()(ikiiiixIZnIZIZ])([11)()1()(iklljlxIZnIZIZ)()()1(iliiccIJIJ(1)(),ccJIJI1II三.编写的程序：#includecfloat#includeiostream#includeiomanip#includefstream#includectime#includecmathusingnamespacestd;doubledistance(doublea[4],doubleb[4]){//TODO:改马氏距离doubled0=a[0]-b[0];doubled1=a[1]-b[1];doubled2=a[2]-b[2];doubled3=a[3]-b[3];returnsqrt(d0*d0+d1*d1+d2*d2+d3*d3);}intmain(){//读取数据doubledata[150][4];ifstreamf(data.txt);for(inti=0;i150;i++)fdata[i][0]data[i][1]data[i][2]data[i][3];f.close();//归一化doublem[4]={DBL_MAX,DBL_MAX,DBL_MAX,DBL_MAX};doubleM[4]={-DBL_MAX,-DBL_MAX,-DBL_MAX,-DBL_MAX};for(i=0;i150;i++)for(intj=0;j4;j++){if(data[i][j]m[j])m[j]=data[i][j];if(data[i][j]M[j])M[j]=data[i][j];}for(i=0;i150;i++)for(intj=0;j4;j++)data[i][j]=(data[i][j]-m[j])/(M[j]-m[j]);//打乱//TODO:使用随机排序intrightLabels[150];for(i=0;i50;i++)rightLabels[i]=0;for(i=50;i100;i++)rightLabels[i]=1;for(i=100;i150;i++)rightLabels[i]=2;srand(time(NULL));for(i=0;i150;i++){intj=rand()%150;doubletmp;tmp=data[i][0];data[i][0]=data[j][0];data[j][0]=tmp;tmp=data[i][1];data[i][1]=data[j][1];data[j][1]=tmp;tmp=data[i][2];data[i][2]=data[j][2];data[j][2]=tmp;tmp=data[i][3];data[i][3]=data[j][3];data[j][3]=tmp;inttmp2;tmp2=rightLabels[i];rightLabels[i]=rightLabels[j];rightLabels[j]=tmp2;}//分类intlabels[150];doubleZ[3][4]={data[0][0],data[0][1],data[0][2],data[0][3],data[1][0],data[1][1],data[1][2],data[1][3],data[2][0],data[2][1],data[2][2],data[2][3]};intiterations=0;while(true){//coutsetw(10)Z[0][0]setw(10)Z[0][1]setw(10)Z[0][2]setw(10)Z[0][3]endl//setw(10)Z[1][0]setw(10)Z[1][1]setw(10)Z[1][2]setw(10)Z[1][3]endl//setw(10)Z[2][0]setw(10)Z[2][1]setw(10)Z[2][2]setw(10)Z[2][3]endl//endl;//cin.get();iterations++;//最小距离分类到labelfor(inti=0;i150;i++){doubled0=distance(Z[0],data[i]);doubled1=distance(Z[1],data[i]);doubled2=distance(Z[2],data[i]);if((d0d1)&&(d0d2))labels[i]=0;elseif(d1d2)labels[i]=1;elselabels[i]=2;}//计算均值为新聚类中心到Zdoublesum[3][4]={0.0};intcount[3]={0};for(i=0;i150;i++){intlabel=labels[i];sum[label][0]+=data[i][0];sum[label][1]+=data[i][1];sum[label][2]+=data[i][2];sum[label][3]+=data[i][3];count[label]++;}boolchanged=false;for(i=0;i3;i++)for(intj=0;j4;j++){if(Z[i][j]!=sum[i][j]/count[i])//可以加入e比较{Z[i][j]=sum[i][j]/count[i];changed=true;}}//聚类中心没改变则退出if(!changed)break;}//输出intcount[3]={0};for(i=0;i150;i++){coutdata[i][0]\tdata[i][1]\tdata[i][2]\tdata[i][3]\tlabels[i]\t(char)(rightLabels[i]+'A')endl;count[labels[i]]++;}coutendliterations:iterationsendllabel0count:count[0]endllabel1count:count[1]endllabel2count:count[2]endl;cin.get();return0;}四.运行结果:0.1666670.1666670.3898310.3750B0.1388890.4166670.06779701A0.4722220.0833330.6779660.5833330C0.5833330.3333330.7796610.8752C0.250.8750.08474601A0.19444400.4237290.3750B0.1944440.5833330.0847460.0416671A0.50.3750.6271190.5416670B0.4166670.2916670.5254240.3750B0.750.50.6271190.5416672B0.1388890.4583330.1016950.0416671A0.250.2916670.4915250.5416670B0.3333330.6250.0508480.0416671A0.6666670.4166670.6779660.6666672B0.4444440.4166670.5423730.5833330B0.1944440.5416670.0677970.0416671A0.3611110.2916670.5423730.50B0.6666670.5416670.7966112C0.1944440.6250.1016950.2083331A0.250.5833330.0677970.0416671A0.3611110.3333330.6610170.7916670C0.8055560.4166670.8135590.6252C0.4166670.2916670.6949150.750C0.3888890.3750.5423730.50B0.3611110.4166670.5254240.50B0.3611110.2083330.4915250.4166670B0.6111110.3333330.6101690.5833330B0.6944440.50.8305080.9166672C0.5833330.50.593220.5833332B0.3888890.3333330.593220.50B0.5277780.5833330.7457630.9166672C0.3611110.4166670.593220.5833330B0.5555560.5416670.6271190.6252B0.50.3333330.6271190.4583330B0.1666670.6666670.0