matlab實(shí)現(xiàn)Kmeans聚類算法簡(jiǎn)介：Kmeans和應(yīng)用于混合高斯模型的受限EM算法是一致的。高斯混合模型廣泛用于數(shù)據(jù)挖掘、模式識(shí)別、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)分析。Kmeans的迭代步驟可以看成E步和M步，E：固定參數(shù)類別中心向量重新標(biāo)記樣本，M：固定均值只考慮（估計(jì)）了均值，而沒(méi)有估計(jì)類別的方差，所以聚類的結(jié)構(gòu)比較適合于特征協(xié)方差相等的類別。Kmeans在某種程度也可以看成Meanshitf的特殊版本，Meanshift是所以Meanshift可以用于尋找數(shù)據(jù)的多個(gè)模態(tài)（類別），利用的是梯度上升法。在06年的一篇CVPR文章上，證明了Meanshift方法是牛頓拉夫遜算法的變種。Kmeans和EM算法相似是指混合密度的形式已知（參數(shù)形式已知）情況下，利用迭代方法，在參數(shù)空間中搜索解。而Kmeans和Meanshift相似是指都是一種概率密度梯度估計(jì)的方法，不過(guò)是Kmean選用的是特殊的核函數(shù)（uniformkernel），而與混合概率密度形式是否已知無(wú)關(guān)，是一種梯度求解方式。k-means是一種聚類算法，這種算法是依賴于點(diǎn)的鄰域來(lái)決定哪些點(diǎn)應(yīng)該分在點(diǎn)，也可以對(duì)高維的空間（3維，4維，等等）的點(diǎn)進(jìn)行聚類，任意高維的空間都可以。

上圖中的彩色部分是一些二維空間點(diǎn)。上圖中已經(jīng)把這些點(diǎn)分組了，并使用了不同的顏色對(duì)各組進(jìn)行了標(biāo)記。這就是聚類算法要做的事情。

這個(gè)算法的輸入是：

1：點(diǎn)的數(shù)據(jù)（這里并不一定指的是坐標(biāo)，其實(shí)可以說(shuō)是向量）

2：K，聚類中心的個(gè)數(shù)（即要把這一堆數(shù)據(jù)分成幾組）

所以，在處理之前，你先要決定將要把這一堆數(shù)據(jù)分成幾組，即聚成幾類。但并不是在所有情況下，你都事先就能知道需要把數(shù)據(jù)聚成幾類的。意味著使用k-means就不能處理這種情況，下文中會(huì)有講解。

把相應(yīng)的輸入數(shù)據(jù)，傳入k-means算法后，當(dāng)k-means算法運(yùn)行完后，該算法的輸出是：

1：標(biāo)簽（每一個(gè)點(diǎn)都有一個(gè)標(biāo)簽，因?yàn)樽罱K任何一個(gè)點(diǎn)，總會(huì)被分到某個(gè)類，類的id號(hào)就是標(biāo)簽）

2：每個(gè)類的中心點(diǎn)。

標(biāo)簽，是表示某個(gè)點(diǎn)是被分到哪個(gè)類了。例如，在上圖中，實(shí)際上有4中“標(biāo)簽”，每個(gè)“標(biāo)簽”使用不同的顏色來(lái)表示。所有黃色點(diǎn)我們可以用標(biāo)簽以看出，有3個(gè)類離的比較遠(yuǎn)，有兩個(gè)類離得比較近，幾乎要混合在一起了。

當(dāng)然，數(shù)據(jù)集不一定是坐標(biāo)，假如你要對(duì)彩色圖像進(jìn)行聚類，那么你的向量就可以是(b,g,r)，如果使用的是hsv顏色空間，那還可以使用(h,s,v),當(dāng)然肯定可以有不同的組合例如(b*b,g*r,r*b)，(h*b,s*g,v*v)等等。

在本文中，初始的類的中心點(diǎn)是隨機(jī)產(chǎn)生的。如上圖的紅色點(diǎn)所示，是本文隨機(jī)產(chǎn)生的初始點(diǎn)。注意觀察那兩個(gè)離得比較近的類，它們幾乎要混合在一起，看看算法是如何將它們分開(kāi)的。

類的初始中心點(diǎn)是隨機(jī)產(chǎn)生的。算法會(huì)不斷迭代來(lái)矯正這些中心點(diǎn)，并最終得到比較靠5個(gè)中心點(diǎn)的距離,選出一個(gè)距離最小的(例如該點(diǎn)與第2個(gè)中心點(diǎn)的距離是5個(gè)距離中最小的),那么該點(diǎn)就歸屬于該類.上圖是點(diǎn)的歸類結(jié)果示意圖.

經(jīng)過(guò)步驟3后,每一個(gè)中心center(i)點(diǎn)都有它的”管轄范圍”,由于這個(gè)中心點(diǎn)不一定是這個(gè)管轄范圍的真正中心點(diǎn),所以要重新計(jì)算中心點(diǎn),計(jì)算的方法有很多種,最簡(jiǎn)單的一種是,直接計(jì)算該管轄范圍內(nèi)所有點(diǎn)的均值,做為心的中心點(diǎn)new_center(i).

如果重新計(jì)算的中心點(diǎn)new_center(i)與原來(lái)的中心點(diǎn)center(i)的距離大于一定的閾值（該閾值可以設(shè)定），那么認(rèn)為算法尚未收斂，使用new_center(i)代替center(i)（如圖，中心點(diǎn)從紅色點(diǎn)轉(zhuǎn)移到綠色點(diǎn)），轉(zhuǎn)步驟3；否則，認(rèn)為算法已經(jīng)收斂，則new_center(i)就是最終的中心點(diǎn)。

現(xiàn)在，所有的中心都不再移動(dòng)，即算法已經(jīng)收斂。當(dāng)然，也許這些中心點(diǎn)還沒(méi)有達(dá)。

可以從K=1開(kāi)始，并且k值不斷的增加，通常，隨著k的增加，類中的方差會(huì)急劇的下降，當(dāng)k達(dá)到一定大的時(shí)候，方差的下降會(huì)明顯減慢（至于慢道何種程度，可以設(shè)閾值），此時(shí)，就選取到了最佳的k值。

如果初始值沒(méi)設(shè)置好，肯定也不能獲得理想的聚類效果。

針對(duì)這種情況，這里提供兩種方法：

隨機(jī)的選取多組中心點(diǎn)，在每一組中心點(diǎn)上，都把kmeans算法運(yùn)行一次。最后，在選取類間方差最小的一組。

通過(guò)設(shè)定的選初始值方法（這里提供一種，當(dāng)然自己也可以去構(gòu)想其他的方法）1.在數(shù)據(jù)集上隨機(jī)選擇一個(gè)點(diǎn)，做為第一個(gè)中心點(diǎn)；

2：在數(shù)據(jù)集上，選取離第一個(gè)中心點(diǎn)最遠(yuǎn)的一個(gè)點(diǎn)做為第二個(gè)中心點(diǎn)。

3：在數(shù)據(jù)集上，選取離第一個(gè)和第二個(gè)中心最遠(yuǎn)的點(diǎn)，做為第三個(gè)中心。

4：依此計(jì)算后續(xù)的中心點(diǎn)

數(shù)據(jù)來(lái)源描述本次數(shù)據(jù)挖掘?qū)嶒?yàn)的數(shù)據(jù)源來(lái)自加州大學(xué)計(jì)算機(jī)與信息院，是用于合成控制圖時(shí)間序列聚類分析的一組數(shù)據(jù)。數(shù)據(jù)集中一共包含600組數(shù)據(jù)，每一組數(shù)據(jù)都有60個(gè)分量，也就是數(shù)據(jù)是60維的。數(shù)據(jù)一共可以分成6個(gè)聚類，分別是：數(shù)據(jù)預(yù)處理由于本數(shù)據(jù)集的數(shù)據(jù)維數(shù)較多，所以本實(shí)驗(yàn)采用了結(jié)構(gòu)體來(lái)存儲(chǔ)60維的數(shù)據(jù)，并使用指針來(lái)進(jìn)行對(duì)數(shù)據(jù)的操作，以提高速度。在數(shù)據(jù)預(yù)處理過(guò)程中，首先將數(shù)據(jù)從data文件中讀出，后依次存入結(jié)構(gòu)體數(shù)組dataset[600]中。k-means聚類算法k-means算法接受參數(shù)k；然后將事先輸入的n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較小。聚類相似度是利用各聚類中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”（引力中心）來(lái)進(jìn)行計(jì)算的。K-means算法是最為經(jīng)典的基于劃分的聚類方法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一。K-means算法的基本思想是：以空間中k個(gè)點(diǎn)為中心進(jìn)行聚類，對(duì)最靠近他們的對(duì)象歸類。通過(guò)迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。（1）算法思路：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類中心；而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對(duì)象的均值）；不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開(kāi)始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù).k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開(kāi)。該算法的最大優(yōu)勢(shì)在于簡(jiǎn)潔和快速。算法的關(guān)鍵在于初始中心的選擇和距離公式。（2）算法步驟：step.1---初始化距離K個(gè)聚類的質(zhì)心（隨機(jī)產(chǎn)生）step.2---計(jì)算所有數(shù)據(jù)樣本與每個(gè)質(zhì)心的歐氏距離，將數(shù)據(jù)樣本加入與其歐氏距離最短的那個(gè)質(zhì)心的簇中（記錄其數(shù)據(jù)樣本的編號(hào)）step.3---計(jì)算現(xiàn)在每個(gè)簇的質(zhì)心，進(jìn)行更新，判斷新質(zhì)心是否與原質(zhì)心相等，若相等，則迭代結(jié)束，若不相等，回到step2繼續(xù)迭代。Matlab代碼：算法流程圖開(kāi)始開(kāi)始讀入要分類的數(shù)據(jù)設(shè)置初始聚類中心計(jì)算數(shù)據(jù)到C個(gè)聚類中心的距離將數(shù)據(jù)分入與其距離最小的聚類計(jì)算新的聚類中心聚類中心是否收斂？否輸出C個(gè)分類好的聚類結(jié)束是實(shí)驗(yàn)源代碼1、主程序clearallclc[FHFW]=textread('C:\Users\lenvo\Desktop\D??¨???t?D\FEMALE.txt','%f%f');[MHMW]=textread('C:\Users\lenvo\Desktop\D??¨???t?D\MALE.txt','%f%f');Data(1:50,1)=FH;Data(51:100,1)=MH;Data(1:50,2)=FW;Data(51:100,2)=MW;C=input('ê?è?C￡o')[U,P,Dist,Cluster_Res,Obj_Fcn,iter]=fuzzycm(Data,C)plot(Data(:,1),Data(:,2),'o');holdon;maxU=max(U);index1=find(U(1,:)==maxU);index2=find(U(2,:)==maxU);line(Data(index1,1),Data(index1,2),'marker','*','color','g');line(Data(index2,1),Data(index2,2),'marker','*','color','r');plot([P([12],1)],[P([12],2)],'*','color','k')holdoff;2、子程序function[U,P,Dist,Cluster_Res,Obj_Fcn,iter]=fuzzycm(Data,C,plotflag,M,epsm)ifnargin<5epsm=1.0e-6;endifnargin<4M=2;endifnargin<3plotflag=0;end[N,S]=size(Data);m=2/(M-1);iter=0;Dist(C,N)=0;U(C,N)=0;P(C,S)=0;U0=rand(C,N);U0=U0./(ones(C,1)*sum(U0));¨whiletrueiter=iter+1;Um=U0.^M;P=Um*Data./(ones(S,1)*sum(Um'))';fori=1:Cforj=1:NDist(i,j)=fuzzydist(P(i,:),Data(j,:));endendU=1./(Dist.^m.*(ones(C,1)*sum(Dist.^(-m))));ifnargout>4|plotflagObj_Fcn(iter)=sum(sum(Um.*Dist.^2));endifnorm(U-U0,Inf)<epsmbreakendU0=U;endifnargout>3res=maxrowf(U);forc=1:Cv=find(res==c);Cluster_Res(c,1:length(v))=v;endendifplotflagfcmplot(Data,U,P,Obj_Fcn);endfunction[U,P,Dist,Cluster_Res,Obj_Fcn,iter]=fuzzycm2(Data,P0,plotflag,M,epsm)ifnargin<5epsm=1.0e-6;endifnargin<4M=2;endifnargin<3plotflag=0;end[N,S]=size(Data);m=2/(M-1);iter=0;C=size(P0,1);Dist(C,N)=0;U(C,N)=0;P(C,S)=0;whiletrueiter=iter+1;fori=1:Cforj=1:NDist(i,j)=fuzzydist(P0(i,:),Data(j,:));endendU=1./(Dist.^m.*(ones(C,1)*sum(Dist.^(-m))));Um=U.^M;P=Um*Data./(ones(S,1)*sum(Um'))';ifnargout>4|plotflagObj_Fcn(iter)=sum(sum(Um.*Dist.^2));endifnorm(P-P0,Inf)<epsmbreakendP0=P;endifnargout>3res=maxrowf(U);forc=1:Cv=find(res==c);Cluster_Res(c,1:length(v))=v;endendifplotflagfcmplot(Data,U,P,Obj_Fcn);endfunctionf=addr(a,strsort)ifnargin==1strsort='ascend';endsa=sort(a);ca=a;la=length(a);f(la)=0;fori=1:laf(i)=find(ca==sa(i),1);ca(f(i))=NaN;endifstrcmp(strsort,'descend')f=fliplr(f);endfunctionellipse(a,b,center,style,c_3d)ifnargin<4style='b';endifnargin<3|isempty(center)center=[0,0];endt=1:360;x=a/2*cosd(t)+center(1);y=b/2*sind(t)+center(2);ifnargin>4plot3(x,y,ones(1,360)*c_3d,style)elseplot(x,y,style)endfunctionfcmplot(Data,U,P,Obj_Fcn)[C,S]=size(P);res=maxrowf(U);str='po*x+d^v><.h';figure(1),plot(Obj_Fcn)title('??±êoˉêy?μ±??ˉ?ú??','fontsize',8)ifS==2figure(2),plot(P(:,1),P(:,2),'rs'),holdonfori=1:Cv=Data(find(res==i),:);plot(v(:,1),v(:,2),str(rem(i,12)+1))ellipse(max(v(:,1))-min(v(:,1)),...max(v(:,2))-min(v(:,2)),...[max(v(:,1))+min(v(:,1)),...max(v(:,2))+min(v(:,2))]/2,'r:')endgridon,title('2D??àà?á1?í?','fontsize',8),holdoffendifS>2figure(2),plot3(P(:,1),P(:,2),P(:,3),'rs'),holdonfori=1:Cv=Data(find(res==i),:);plot3(v(:,1),v(:,2),v(:,3),str(rem(i,12)+1))ellipse(max(v(:,1))-min(v(:,1)),...max(v(:,2))-min(v(:,2)),...[max(v(:,1))+min(v(:,1)),...max(v(:,2))+min(v(:,2))]/2,...'r:',(max(v(:,3))+min(v(:,3)))/2)endgridon,title('3D??àà?á1?í?','fontsize',8),holdoffendfunctionD=fuzzydist(A,B)D=norm(A-B);functionmr=maxrowf(U,c)ifnargin<2c=1;endN=size(U,2);mr(1,N)=0;forj=1:Naj=addr(U(:,j),'descend');mr(j)=aj(c);end實(shí)驗(yàn)結(jié)果1、FEMALE和MALE(1)C=2,Z1(1)=(173,53)T,Z2(1)=(168,57)T。聚類中心為（163.322052.5232），（175.256567.6907）迭代次數(shù)為28（2）C=2,Z1(1)=(173,53)T,Z2(1)=(160,58)T。聚類中心為（163.322052.5232），（175.256567.6907）迭代次數(shù)為28（3）C=3,Z1(1)=(173,53)T,Z2(1)=(168,57)TZ3(1)=(160,58)T聚類中心為（168.413957.3300）（176.335169.4859）（160.176749.1940）迭代次數(shù)為41（4）C=3,Z1(1)=(173,53)T,Z2(1)=(168,57)TZ3(1)=(161,45)T聚類中心為（168.413957.3300）（176.335169.4859）（160.176749.1940）迭代次數(shù)為41 2、test2(1)C=2,Z1(1)=(173,53)T,Z2(1)=(168,57)T