K均值聚類算法的MATLAB實現

　　K-means算法是最簡單的一種聚類算法。算法的目的是使各個樣本與所在類均值的誤差平方和達到最?。ㄟ@也是評價K-means算法最后聚類效果的評價標準）

　　K-means聚類算法的一般步驟：

　　初始化。輸入基因表達矩陣作為對象集X，輸入指定聚類類數N，并在X中隨機選取N個對象作為初始聚類中心。設定迭代中止條件，比如最大循環(huán)次數或者聚類中心收斂誤差容限。

　　進行迭代。根據相似度準則將數據對象分配到最接近的聚類中心，從而形成一類。初始化隸屬度矩陣。

　　更新聚類中心。然后以每一類的平均向量作為新的聚類中心，重新分配數據對象。

　　反復執(zhí)行第二步和第三步直至滿足中止條件。

　　K-均值聚類法的概述

　　之前在參加數學建模的過程中用到過這種聚類方法，但是當時只是簡單知道了在matlab中如何調用工具箱進行聚類，并不是特別清楚它的原理。最近因為在學模式識別，又重新接觸了這種聚類算法，所以便仔細地研究了一下它的原理。弄懂了之后就自己手工用matlab編程實現了，最后的結果還不錯，嘿嘿~~~

　　簡單來說，K-均值聚類就是在給定了一組樣本（x1， x2， 。。.xn） （xi， i = 1， 2， 。。。 n均是向量） 之后，假設要將其聚為 m（《n） 類，可以按照如下的步驟實現：

　　Step 1： 從 （x1， x2， 。。.xn） 中隨機選擇 m 個向量（y1，y2，。。.ym） 作為初始的聚類中心（可以隨意指定，不在n個向量中選擇也可以）;

　　Step 2： 計算 （x1， x2， 。。.xn） 到這 m 個聚類中心的距離（嚴格來說為 2階范數）;

　　Step 3： 對于每一個 xi（i = 1，2，。。.n）比較其到 （y1，y2，。。.ym） 距離，找出其中的最小值，若到 yj 的距離最小，則將 xi 歸為第j類;

　　Step 4： m 類分好之后， 計算每一類的均值向量作為每一類新的聚類中心;

　　Step 5： 比較新的聚類中心與老的聚類中心之間的距離，若大于設定的閾值，則跳到 Step2; 否則輸出分類結果和聚類中心，算法結束。

　　單介紹下kmeans算法流程：

　　假設要把樣本集分為c個類別，算法描述如下：

　　（1）適當選擇c個類的初始中心；

　　（2）在第k次迭代中，對任意一個樣本，求其到c各中心的距離，將該樣本歸到距離最短的中心所在的類；

　?。?）利用均值等方法更新該類的中心值；

　?。?）對于所有的c個聚類中心，如果利用（2）（3）的迭代法更新后，值保持不變，則迭代結束，否則繼續(xù)迭代。

　　該算法的最大優(yōu)勢在于簡潔和快速。算法的關鍵在于初始中心的選擇和距離公式。

　　matlab實現：

　　function ［ class count］=k_means（data，k）;

　　%clear

　　%load testdata.mat

　　%k=2;

　　sum=size（data，1）;

　　for i=1:k

　　centroid（i，：）=data（floor（sum/k）*（i-1）+1，：）;

　　end

　　tic

　　ck=0;

　　while 1

　　temp=zeros（1，2）;;

　　count=zeros（1，k）;

　　ck=ck+1

　　for i=1:sum

　　for j=1:k

　　dist（j）=norm（data（i，：）-centroid（j，：））;

　　end

　　［a min_dist］=min（dist）;

　　count（min_dist）=count（min_dist）+1;

　　class（min_dist，count（min_dist））=i;

　　end

　　%重新計算類中心

　　for i=1:k

　　for j=1:count（i）

　　temp=temp+data（class（i，j），：）;

　　end

　　temp_centroid（i，：）=temp/（count（i））;

　　temp（1，：）=0;

　　% temp_centroid（i，：）=re_calculate（class（i，：），count（i），tdata）;

　　end

　　%計算新的類中心和原類中心距離centr_dist;

　　for i=1:k

　　centr_dist（i）=norm（temp_centroid（i，：）-centroid（i，：））;

　　end

　　if max（centr_dist）《=0

　　break;

　　else

　　for i=1:k

　　centroid（i，：）=temp_centroid（i，：）;

　　%重新進行前倆不

　　end

　　end

　　end

　　toc