K-均值聚類算法報告

1、K-均值聚類算法報告算法思想K-均值算法也稱C-均值算法，是根據(jù)函數(shù)準則進行分類的聚類算法，基于使聚類準則函數(shù)最小化。K-均值算法的主要思想是先在需要分類的數(shù)據(jù)中尋找K組數(shù)據(jù)作為初始聚類中心，然后計算其他數(shù)據(jù)距離這三個聚類中心的距離，將數(shù)據(jù)歸入與其距離最近的聚類中心，之后再對這K個聚類的數(shù)據(jù)計算均值，作為新的聚類中心，繼續(xù)以上步驟，直到新的聚類中心與上一次的聚類中心值相等時結(jié)束算法。準則函數(shù)：聚類集中每一樣本點到該類中心的距離平方和。對于第j個聚類集，準則函數(shù)定義為：Z=刃X,XeSjNiijji二1Sj：第j個聚類集(域)聚類中心為Zj；Nj：第j個聚類集Sj中所包含的樣本個數(shù)。對所有K個模

2、式類有：J=菖卩11X-ZIl2,XeSijijj=1i=1K-均值算法的聚類準則：聚類中心的選擇應使準則函數(shù)J極小，即使Jj的值極小。即有：丄乞IIx-zii2=_L5L（x-z）t（x-z）=0宓ji=1#ijcZ1j1jji=1可解得：J=才11X-ZI|2,XeSjijiji=1上式表明，Sj類的聚類中心應選為該類樣本的均值算法描述任選K個初始聚類中心：Zl(l),Z2(l),，ZK(1)括號內(nèi)序號：迭代運算的次序號。按最小距離原則將其余樣品分配到K個聚類中心中的某一個，即：min|XZ(k)|,i=1,2,K丄XZ(k)=D(k)ijj則XeS(k)計算各個聚類中心的新向量值:Z(k

3、+1)j=1,2,KjNj：Z(k+1)=j第j類的樣本數(shù)。工XXeSj（k）j=12，K如果Z(k+1)豐Z(k)j=1,2,K則回到(2),將模式樣本逐個重新分類，重復迭代計算。j如果Z(k+1)=Z(k)j=1,2,K，則算法收斂，計算完畢。算法討論結(jié)果受到所選聚類中心的個數(shù)和其初始位置，以及模式樣本的幾何性質(zhì)及讀入次序等的影響。實際應用中需要試探不同的K值和選擇不同的聚類中心起始值，一般可選擇樣本集中前K個樣本作為初始聚類中心。計算流程本次程序計算過程嚴格按照算法描述，通過選取初始聚類中心、計算距離、計算新的聚類中心、判斷結(jié)果的收斂性等迭代過程，最終得出聚類結(jié)果和聚類中心。具體流程如下

4、圖：分類結(jié)果讀取前50個數(shù)據(jù)時的兩類聚類中心矢量Z1和Z2,以及對應的兩類數(shù)據(jù)集合G1和G2聚類結(jié)果如下：讀取前100個數(shù)據(jù)時的兩類聚類中心矢量Z1和Z2,以及對應的兩類數(shù)據(jù)集合G1和G2聚類結(jié)果如下：讀取全部數(shù)據(jù)時的兩類聚類中心矢量Z1和Z2,以及對應的兩類數(shù)據(jù)集合G1和G2聚類結(jié)果如下：附：源代碼#include#include#include#include#defineCOUNT150/數(shù)據(jù)個數(shù)structdatafloatdx;floatdy;floatdz;floatdm;intsymbol;/標號data150,Zdata2,Cz2;inttime=0;/記錄迭代次數(shù)intjud

5、ge(floati,floatj)/判斷數(shù)據(jù)屬于哪個分類if(i=j)return1;elsereturn2;voidmain()intz1=0,z2=0;/存放每個聚類的元素個數(shù)floata=0,b=0,c=0,d=0,e2,t8;floatsum=0;intcount;fstreamoutputFile;outputFile.open(IrisData.txt,ios:in);/打開文件if(!outputFile)coutCantopentheFile!endl;exit(0);for(count=0;countdatacount.dx;outputFiledatacount.dy;ou

6、tputFiledatacount.dz;outputFiledatacount.dm;datacount.symbol=0;outputFile.close();for(count=0;count2;count+)/初始化聚類Zdatacount.dx=datacount.dx;Zdatacount.dy=datacount.dy;Zdatacount.dz=datacount.dz;Zdatacount.dm=datacount.dm;Zdatacount.symbol=datacount.symbol;do/初始化Cz0.dx=0;Cz0.dy=0;Cz0.dz=0;Cz0.dm=0;C

7、z1.dx=0;Cz1.dy=0;Cz1.dz=0;Cz1.dm=0;for(count=0;countCOUNT;count+)/判斷每個元素屬于哪個聚類a=(Zdata0.dx-datacount.dx);b=(Zdata0.dy-datacount.dy);c=(Zdata0.dz-datacount.dz);d=(Zdata0.dm-datacount.dm);e0=sqrt(a*a+b*b+c*c+d*d);/計算歐氏距離a=(Zdata1.dx-datacount.dx);b=(Zdata1.dy-datacount.dy);c=(Zdata1.dz-datacount.dz);d

8、=(Zdata1.dm-datacount.dm);e1=sqrt(a*a+b*b+c*c+d*d);datacount.symbol=judge(e0,e1);/比較到兩個聚類中心的距離z1=0;z2=0;for(count=0;countvCOUNT;count+)計算每個聚類的兀素個數(shù)if(datacount.symbol=1)Cz0.dx+=datacount.dx;Cz0.dy+=datacount.dy;Cz0.dz+=datacount.dz;Cz0.dm+=datacount.dm;z1+;elseif(datacount.symbol=2)Cz1.dx+=datacount.

9、dx;Cz1.dy+=datacount.dy;Cz1.dz+=datacount.dz;Cz1.dm+=datacount.dm;z2+;Cz0.dx=Cz0.dx/z1;/計算新的聚類中心Cz0.dy=Cz0.dy/z1;Cz0.dz=Cz0.dz/z1;Cz0.dm=Cz0.dm/z1;Cz1.dx=Cz1.dx/z2;Cz1.dy=Cz1.dy/z2;Cz1.dz=Cz1.dz/z2;Cz1.dm=Cz1.dm/z2;+time;sum=0;t0=(Zdata0.dx-Cz0.dx)*(Zdata0.dx-Cz0.dx);/新的聚類中心與前一次中心比較t1=(Zdata0.dy-Cz0

10、.dy)*(Zdata0.dy-Cz0.dy);t2=(Zdata0.dz-Cz0.dz)*(Zdata0.dz-Cz0.dz);t3=(Zdata0.dm-Cz0.dm)*(Zdata0.dm-Cz0.dm);t4=(Zdata1.dx-Cz1.dx)*(Zdata1.dx-Cz1.dx);t5=(Zdata1.dy-Cz1.dy)*(Zdata1.dy-Cz1.dy);t6=(Zdata1.dz-Cz1.dz)*(Zdata1.dz-Cz1.dz);t7=(Zdata1.dm-Cz1.dm)*(Zdata1.dm-Cz1.dm);for(count=0;count8;count+)sum+

11、=tcount;Zdata0.dx=Cz0.dx;Zdata0.dy=Cz0.dy;Zdata0.dz=Cz0.dz;Zdata0.dm=Cz0.dm;Zdata1.dx=Cz1.dx;Zdata1.dy=Cz1.dy;Zdata1.dz=Cz1.dz;Zdata1.dm=Cz1.dm;while(sum!=0);/分類結(jié)果與前一次迭代結(jié)果不同，繼續(xù)迭代coutvv下標從1到150分類成功！vvendl;coutvvendlvv第一類數(shù)據(jù)集合G1下標號為：vvendl;輸出第一類結(jié)果for(count=0;countvCOUNT;count+)if(datacount.symbol=1)coutvvcount+1vv;coutvvendlvv共vvzlvv個元素vvendl;coutvv中心矢量Z1是：(vvZdata0.dxvvvvZdata0.dyvvvvZdata0.dzvvvvZdata0.dmvv)vvendl;coutvvendlvv第二類數(shù)據(jù)集合G2下標號為：vvendl;輸出第二類結(jié)果for(count=0;countvCOUNT;count+)if(d