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

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

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

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

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

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

　　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個類的初始中心；

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

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

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

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

　　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

　　數據點是鼠標插進去的，通過界面可以很清晰的看到分類過程，功能截圖如下：

　　下面來看看K-means是如何工作的：

　　圖中圓形為聚類中心，方塊為待聚類數據，步驟如下：

　　（a）選取聚類中心，可以任意選取，也可以通過直方圖進行選取。我們選擇三個聚類中心，并將數據樣本聚到離它最近的中心；

　　（b）數據中心移動到它所在類別的中心；

　?。╟）數據點根據最鄰近規則重新聚到聚類中心；

　?。╠）再次更新聚類中心；不斷重復上述過程直到評價標準不再變化

　　評價標準：

　　假設有M個數據源，C個聚類中心。μc為聚類中心。該公式的意思也就是將每個類中的數據與每個聚類中心做差的平方和，J最小，意味著分割的效果最好。

　　K-means面臨的問題以及解決辦法：

　　1.它不能保證找到定位聚類中心的最佳方案，但是它能保證能收斂到某個解決方案（不會無限迭代）。

　　解決方法：多運行幾次K-means，每次初始聚類中心點不同，最后選擇方差最小的結果。

　　2.它無法指出使用多少個類別。在同一個數據集中，例如上圖例，選擇不同初始類別數獲得的最終結果是不同的。

　　解決方法：首先設類別數為1，然后逐步提高類別數，在每一個類別數都用上述方法，一般情況下，總方差會很快下降，直到到達一個拐點；這意味著再增加一個聚類中心不會顯著減少方差，保存此時的聚類數。

　　MATLAB函數Kmeans

　　使用方法：

　　Idx=Kmeans（X，K）

　?。跧dx，C］=Kmeans（X，K）

　?。跧dx，C，sumD］=Kmeans（X，K）

　　［Idx，C，sumD，D］=Kmeans（X，K）

　?。邸?Kmeans（…，’Param1’，Val1，’Param2’，Val2，…）

　　各輸入輸出參數介紹：

　　X： N*P的數據矩陣，N為數據個數，P為單個數據維度

　　K： 表示將X劃分為幾類，為整數

　　Idx： N*1的向量，存儲的是每個點的聚類標號

　　C： K*P的矩陣，存儲的是K個聚類質心位置

　　sumD： 1*K的和向量，存儲的是類間所有點與該類質心點距離之和

　　D： N*K的矩陣，存儲的是每個點與所有質心的距離

　?。邸?Kmeans（…，‘Param1’，Val1，‘Param2’，Val2，…）

　　這其中的參數Param1、Param2等，主要可以設置為如下：

　　1. ‘Distance’（距離測度）

　　‘sqEuclidean’ 歐式距離（默認時，采用此距離方式）

　　‘cityblock’ 絕度誤差和，又稱：L1

　　‘cosine’ 針對向量

　　‘correlation’ 針對有時序關系的值

　　‘Hamming’ 只針對二進制數據

　　2. ‘Start’（初始質心位置選擇方法）

　　‘sample’ 從X中隨機選取K個質心點

　　‘uniform’ 根據X的分布范圍均勻的隨機生成K個質心

　　‘cluster’ 初始聚類階段隨機選擇10%的X的子樣本（此方法初始使用’sample’方法）

　　matrix 提供一K*P的矩陣，作為初始質心位置集合

　　3. ‘Replicates’（聚類重復次數） 整數

　　使用案例：

　　data=

　　5.0 3.5 1.3 0.3 -1

　　5.5 2.6 4.4 1.2 0

　　6.7 3.1 5.6 2.4 1

　　5.0 3.3 1.4 0.2 -1

　　5.9 3.0 5.1 1.8 1

　　5.8 2.6 4.0 1.2 0

　　［Idx，C，sumD，D］=Kmeans（data，3，‘dist’，‘sqEuclidean’，‘rep’，4）

　　運行結果：

　　Idx =

　　1

　　2

　　3

　　1

　　3

　　2

　　C =

　　5.0000 3.4000 1.3500 0.2500 -1.0000

　　5.6500 2.6000 4.2000 1.2000 0

　　6.3000 3.0500 5.3500 2.1000 1.0000

　　sumD =

　　0.0300

　　0.1250

　　0.6300

　　D =

　　0.0150 11.4525 25.5350

　　12.0950 0.0625 3.5550

　　29.6650 5.7525 0.3150

　　0.0150 10.7525 24.9650

　　21.4350 2.3925 0.3150

　　10.2050 0.0625 4.0850