在監督學習中，有標簽信息協助機器學習同類樣本之間存在的共性，在預測時只需判定給定樣本與哪個類別的訓練樣本最相似即可。在非監督學習中，不再有標簽信息的指導，遇到一維或二維數據的劃分問題，人用肉眼就很容易完成，可機器就傻眼了，圖(1)描述得很形象。

但處理高維度的數據，人腦也無能為力了，最終還是得設計算法讓機器來完成。如何將所有樣本分成若干個類簇(cluster)，并且每個類簇中的樣本具有更高的相似度，這就是聚類分析算法的終極目標。這里以最經典的K-means算法為切入點進行說明。 K-means算法的目標是將mm個樣本組成的集合X={x(1),x(2),?,x(m)|x(i)∈Rn}X={x(1),x(2),?,x(m)|x(i)∈Rn}劃分成kk個類簇(k≤mk≤m)，其準則函數形式如下：

J(c,μ)=∑i=1m∥x(i)?μ(i)c∥2(1)(1)J(c,μ)=∑i=1m∥x(i)?μc(i)∥2 其中 cc為樣本的類簇分配情況， μμ為類簇中心點， μ(i)cμc(i)為樣本 x(i)x(i)對應的類簇中心。準則函數計算的是所有樣本點與其對應的類簇中心的距離平方和。使準則函數最小的類簇劃分極為最優的聚類。K-means算法描述請下圖。

?

算法的內層循環完成兩個工作：一是將每個樣本劃分到與其最近的類簇中心；二是將屬于同一個類簇的樣本均值作為新的類簇中心。算法的終止條件可以有三種：1)準則函數值的變化小于一個閾值；2)類簇中心在一定范圍內不再變化；3)達到指定的迭代次數TT。K-means的執行步驟如圖(2)所示：(a)隨機初始化的樣本點；(b)隨機設置類簇中心；(c)給樣本點分配與之最近的類簇中心；(d)類簇中心更新為類簇中所有樣本的均值；重復(c)和(d)直到收斂。

?

這里的準則函數不是凸函數，找到全局最優解是不可能的，但是能保證它收斂到局部最優解，分析如下：

更新樣本x(i)x(i)所屬的類簇時，總是選擇與其最近的類簇中心，所以∥x(i)?μ(i)c∥2∥x(i)?μc(i)∥2在每次迭代過程都是非遞增的，那么能保證準則函數JJ也是非遞增的；

類簇中心被更新為類簇中所有樣本的均值也能保證JJ非遞增。準則函數對類簇中心求偏導，并令偏導為0即可求得類簇中心的更新規則 ?J?μj=??μj∑mi=11{c(i)=j}∥x(i)?μ(i)c∥2=2∑mi=11{c(i)=j}(μ(i)c?x(i))=0?μj=∑mi=11{c(i)=j}x(i)∑mi=11{c(i)=j}(2)(2)?J?μj=??μj∑i=1m1{c(i)=j}∥x(i)?μc(i)∥2=2∑i=1m1{c(i)=j}(μc(i)?x(i))=0?μj=∑i=1m1{c(i)=j}x(i)∑i=1m1{c(i)=j}

圖(3)左側是在隨機生成的四組服從高斯分布的數據上跑完K-means后的聚類結果；右側則為每次迭代過程中準則函數值的變化曲線圖，經過16次迭代后算法就收斂了，這也從實驗角度驗證了算法的收斂性。因為給定的不同類簇的數據間分得比較開，最后的聚類分析結果堪稱完美。由于這次隨機初始化的類簇中心情況很糟糕，算法經過16次迭代后才收斂，一般在8次以內就穩定了。 ?

如果樣本有多個屬性，而且屬性不在同一個定義域內，則有必要對樣本數據進行預處理，防止某些值很大的屬性在計算距離時占主導優勢。最常用的就是標準化處理，使得每個屬性均值為0，方差為1。 K-means算法對類簇中心的初始化非常敏感，如圖(4)所示，我在圖中示意性標出了6個可能的初始點，算法會收斂到對應的6個局部最優解，然而只有第2個才是全局最優解。為了避免陷入很差的局部最優解(如第1個局部最優解)，常用的策略就是多跑幾次K-means，每次都將類簇中心隨機初始化，最后選取使準則函數最小的聚類情況。 ?

聚類的最終目的是使同一個類簇中的數據盡可能相似，而不同類簇間的樣本彼此離得越遠越好。如果我們在初始化類簇中心的時候就遵循這條原則，則可以大大減少收斂所需的迭代次數。下面給出了類簇中心初始化的算法(2)描述，該算法的時間復雜度為O(m2+km)O(m2+km)。我們可以想象到，該初始化算法實際上是從樣本分布的最邊緣開始選取類簇中心的，以避免類簇中心被初始化到數據較為密集的地方，大大降低算法收斂需要的迭代次數。有收獲必然也要付出代價，這是永恒的真理，這么做是否值還得視情況而定。 ?

在標準的K-means算法中，每個樣本點都要和更新后的類簇中心計算距離歐氏距離，如果樣本維度較高的話，算法的時間復雜度會非常高。有些大牛們提出用三角不等式或樹形結構等對K-means進行加速的算法，以減少不必要的距離計算。建議參考2003年Elkan發表在ICML上的論文《Using the triangle inequality to accelerate k-means》，以及《A generalized optimization of the k-d tree for fast nearest neighbour search》。開源項目VLFeat中就使用了k-d樹加速K-means。 在批量版本K-means算法中，我們用所有數據一次性更新類簇中心。但遇到需要在線處理的應用時，處理時間是關鍵，另外一個挑戰就是數據的動態輸入，因此有必要為K-means設計一個在線算法。在時間允許的范圍內，我們可以一次值處理一條數據，也可以等收集到幾條數據后一起處理。在前面證明K-means算法的收斂性過程中，我們求出了準則函數對類簇中心μjμj的偏導，我們很容易將其改造成利用隨機梯度下降的online版本算法(3)，其中學習率參數αα應該隨處理數據的增多而逐漸減小。 ?

K-means算法的一大特點是每個樣本只能被硬性分配(hard assignment)到一個類簇中，這種方法不一定是最合理的。但聚類本身就是一個具有不確定性的問題，如圖(5)所示，實際情況中的類簇很可能存在重疊的情況，那么重疊的部分的歸屬就頗具爭議了；給定一個新樣本，正好它與所有類簇中心的聚類是相等的，我們又該怎么辦？如果我們采用概率的方法，像高斯混合模型(Gauss Mixture Model,GMM)那樣給出樣本屬于每個類簇的概率值，能從一定程度上反映聚類的不確定性就更合理了。 ?

下面介紹K-means算法的兩個簡單應用：圖像分割和數據壓縮。圖像分割的目標是將圖像劃分成若個區域，每個區域內有相似的視覺效果。K-means用于圖像分割，實際上就是將圖像中的所有像素點當成樣本點，將相似的像素點盡可能劃分到同一個類簇中，最后就形成了kk個區域，在展示分割情況時以類簇中心代替該類簇中的所有樣本。如圖(6)所示，我選擇了經典的Lena圖像和一只小鳥圖像進行分割，每次聚類的中心數目kk從左到右依次為3,6,123,6,12，最右側圍原圖。Lena圖像的顏色種類較少，所有k=3k=3時的效果也還行；但是小鳥圖像顏色復雜很多，直到k=12k=12時圖像的分割效果才略微令人滿意。圖像分割其實是個相當有難度的問題，K-means算法在這個領域還是太弱了...

數據壓縮分為無損壓縮和有損壓縮兩大類，無損壓縮要求數據還原后要和元素數據一模一樣，而有損壓縮可以容忍重構數據與元素數據存在一定程度的偏差。K-means算法用于數據壓縮只能是有損壓縮了，kk越小數據失真越厲害。主要思想是在NN個樣本集合中用于K-means算法得到kk個類簇中心和NN個類簇的分配情況，最終我們只需存儲類簇中心和每個樣本的類簇分配情況即可。假設每個樣本的存儲空間為aa字節，則kk各類簇中心需要的存儲空間為kaka字節，類簇分配情況耗費存儲空間為N?log2k?N?log2?k?字節，壓縮比為Na/(ka+N?log2k?)Na/(ka+N?log2?k?)。

? ?

整個K-means實驗的Matlab代碼在這里下載！

from:?http://www.cnblogs.com/jeromeblog/p/3425919.html

總結

以上是生活随笔為你收集整理的K-means Algorithm 聚类算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。