K均值聚类算法加源码

模式识别导论K均值聚类算法实验报告一．实验功能本实验功能与目的是实现K—均值聚类算法，将“Iris.txt”文件中的数据用K—均值聚类的方法分为三类。分类结果用该数据的数据编号表示。二．子函数列表参数说明程序中使用到了三个子函数1.voidfileop(category*p)//文件打开读入结构体函数函数功能：将Iris.txt文件打开，把数据从文件中读出存入定义的结构体，每个向量的分量存入结构体的对应元素中，取值结束后将文件关闭函数参数：已定义的结构体category，结构体定义如下structcategory//待聚类数据结构体{intlabel;//标号floatx1;//四个分量floatx2;floatx3;floatx4;};2.floatmin(floatx,floaty,floatz)//最小值函数函数功能：求三个数的最小值并返回最小值数据函数参数：三个单精度浮点型数据3.voidK_averange(category*p,categorya,categoryb,categoryc)//k均值聚类函数函数功能：实现K—均值聚类算法函数参数：已定义的待聚类结构体，定义同上。聚类中心结构体a,b,c。存放每次迭代的聚类中心，初始聚类中心为文件中的前三个数据三．程序流程图YNYY开始打开文件是否成功聚类选择初始聚类中心修改聚类中心N输出结果结束聚类中心是否改变四．程序源代码#includeiostream#includefstreamusingnamespacestd;#defineMAX151//定义数据个数intCOUNT=1;//记录迭代次数inta1[MAX];//存放第i类的标号(i=1,2,3)inta2[MAX];inta3[MAX];intb1;//记录第i类元素的个数(i=1,2,3)intb2;intb3;structcategory//待聚类数据结构体{intlabel;//标号floatx1;//四个分量floatx2;floatx3;floatx4;};voidfileop(category*p)//文件打开读入结构体函数{inti;fstreamdataFile;dataFile.open(Iris.txt,ios::in);if(dataFile.fail()){cout打开文件失败endl;exit(0);}while(!dataFile.eof()){for(i=1;i151;i++){p[i].label=i;dataFilep[i].x1;dataFilep[i].x2;dataFilep[i].x3;dataFilep[i].x4;}}dataFile.close();}floatmin(floatx,floaty,floatz)//最小值函数{if(xy&&xz)returnx;elseif(yx&&yz)returny;elseif(zx&&zy)returnz;}voidK_averange(category*p,categorya,categoryb,categoryc)//k均值聚类函数{structcategorycom1,com2,com3;//用来比较聚类中心是否改变structcategorysum1,sum2,sum3;//求各类各分量的和进而计算新的聚类中心com1=a;com2=b;com3=c;sum1.x1=sum1.x2=sum1.x3=sum1.x4=0;sum2.x1=sum2.x2=sum2.x3=sum2.x4=0;sum3.x1=sum3.x2=sum3.x3=sum3.x4=0;inti;for(i=1;iMAX;i++){a1[i]=0;a2[i]=0;a3[i]=0;}floatf[3];floatflag;b1=0;b2=0;b3=0;for(i=1;iMAX;i++){f[0]=(p[i].x1-a.x1)*(p[i].x1-a.x1)+(p[i].x2-a.x2)*(p[i].x2-a.x2)+(p[i].x3-a.x3)*(p[i].x3-a.x3)+(p[i].x4-a.x4)*(p[i].x4-a.x4);f[1]=(p[i].x1-b.x1)*(p[i].x1-b.x1)+(p[i].x2-b.x2)*(p[i].x2-b.x2)+(p[i].x3-b.x3)*(p[i].x3-b.x3)+(p[i].x4-b.x4)*(p[i].x4-b.x4);f[2]=(p[i].x1-c.x1)*(p[i].x1-c.x1)+(p[i].x2-c.x2)*(p[i].x2-c.x2)+(p[i].x3-c.x3)*(p[i].x3-c.x3)+(p[i].x4-c.x4)*(p[i].x4-c.x4);//计算到三个聚类中心的距离值flag=min(f[0],f[1],f[2]);//取最小值if(f[0]==flag){a1[b1++]=p[i].label;sum1.x1+=p[i].x1;sum1.x2+=p[i].x2;sum1.x3+=p[i].x3;sum1.x4+=p[i].x4;}elseif(f[1]==flag){a2[b2++]=p[i].label;sum2.x1+=p[i].x1;sum2.x2+=p[i].x2;sum2.x3+=p[i].x3;sum2.x4+=p[i].x4;}elseif(f[2]==flag){a3[b3++]=p[i].label;sum3.x1+=p[i].x1;sum3.x2+=p[i].x2;sum3.x3+=p[i].x3;sum3.x4+=p[i].x4;}}//将每个元素加到距离最小值的类，并求和sum1.x1=sum1.x1/b1;sum1.x2=sum1.x2/b1;sum1.x3=sum1.x3/b1;sum1.x4=sum1.x4/b1;sum2.x1=sum2.x1/b2;sum2.x2=sum2.x2/b2;sum2.x3=sum2.x3/b2;sum2.x4=sum2.x4/b2;sum3.x1=sum3.x1/b3;sum3.x2=sum3.x2/b3;sum3.x3=sum3.x3/b3;sum3.x4=sum3.x4/b3;//求平均值//测试代码/*for(j=0;jb1;j++)couta1[j]endl;cout**************************endl;for(j=0;jb2;j++)couta2[j]endl;cout**************************endl;for(j=0;jb3;j++)couta3[j]endl;cout****************************endl;coutb1endl;coutb2endl;coutb3endl;coutsum1.x1sum1.x2sum1.x3sum1.x4endl;coutsum2.x1sum2.x2sum2.x3sum2.x4endl;coutsum3.x1sum3.x2sum3.x3sum3.x4endl;*/a=sum1;b=sum2;c=sum3;//新的聚类中心if(a.x1!=com1.x1||a.x2!=com1.x2||a.x3!=com1.x3||a.x4!=com1.x4||b.x1!=com2.x1||b.x2!=com2.x2||b.x3!=com2.x3||b.x4!=com2.x4||c.x1!=com3.x1||c.x2!=com3.x2||c.x3!=com3.x3||c.x4!=com3.x4){K_averange(p,a,b,c);COUNT++;}//如果聚类中心改变，递归调用k均值聚类函数，并增加迭代次数}intmain(){intj;cout已将文件的数据按行号编号endl;structcategory*p=newcategory[MAX];structcategorya,b,c;fileop(p);//文件操作a=p[1];b=p[2];c=p[3];//聚类中心初始值定义为前三个数据K_averange(p,a,b,c);//K均值聚类函数cout第一类分类结果为：endl;for(j=0;jb1;j++)couta1[j]endl;cout**************************endl;cout第二类分类结果为：endl;for(j=0;jb2;j++)couta2[j]endl;cout**************************endl;cout第三类分类结果为：endl;for(j=0;jb3;j++)couta3[j]endl;cout共迭代COUNT次endl;//测试代码//coutb1b2b3endl;//for(i=1;iMAX;i++)//coutp[i].labelp[i].x2endl;//coutendl;//couta.x1a.x2a.x3a.x4endl;//coutb.x1b.x2b.x3b.x4endl;//coutc.x1c.x2c.x3c.x4endl;delete[]p;return0;}五．输出结果已将文件的数据按行号编号第一类分类结果为：515378101103104105106108109110111112113116117118119121123125126129130131132133135136137138140141142144145146148149**************************第二类分类结果为：52545556575859606162636465666768697071727374757677798081828384858687888990919293949596979899100102107114115120122124127128134139143147150**************************第三类分类结果为：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950共迭代11次Pressanykeytocontinue（注：程序输出时为一行一个数据，报告中为了节省页面，更加直观，故一行多个数据。报告中的数据结果和程序输出时的分类结果一致）六．算法分析通过实验程序输出可以看出，选取文件中起始的三个数据作为聚类中心将150个数据分类共需要迭代11次。此外，我采用随机产生起始的聚类中心的方法下，迭代的次数出现了5次左右和12次左右的明显差异。从而我发现K-均值聚类算法的收敛性是和初值的选取有关。在实验中，程序中初始的聚类中心是1,2,3前三个数，而通过结果发现前三个数属于同一类，迭代的次数为11次。而将1,51,52分别属于三个类别的数据作为初始聚类中心，迭代次数为4次。由此可见，初始值选择同一类时K-均值算法的收敛速度较慢，初始值选择不同类别时K-均值算法的收敛速度较快。在起始不知道数据分类结果的情况下，初始聚类中心的选择是随机的。因此对于K-均值算法的收敛速度也是不确定的。但从随机选择数据做聚类中心的迭代次数可以看出，K-均值算法的收敛速度还是较慢的。时间复杂度也较高其次，在实验中我发现第51个数据在起始聚类中心不同的情况下，会被分为不同的类。从而起始聚类中心的选择与部分数