知識星球（點選上方公眾號，可快速關註）
轉自：JerryLead
http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html
K-means也是聚類演演算法中最簡單的一種了，但是裡麵包含的思想卻是不一般。最早我使用並實現這個演演算法是在學習韓爺爺那本資料挖掘的書中，那本書比較註重應用。
看了Andrew Ng的這個講義後才有些明白K-means後麵包含的EM思想。
聚類屬於無監督學習，以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的，也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特徵x，比如假設宇宙中的星星可以表示成三維空間中的點集
。
聚類的目的是找到每個樣本x潛在的類別y，並將同類別y的樣本x放在一起。比如上面的星星，聚類後結果是一個個星團，星團裡面的點相互距離比較近，星團間的星星距離就比較遠了。
在聚類問題中，給我們的訓練樣本是
，每個
，沒有了y。
K-means演演算法是將樣本聚類成k個簇（cluster），具體演演算法描述如下：
|
1、 隨機選取k個聚類質心點（cluster centroids）為 2、 重覆下麵過程直到收斂 { 對於每一個樣例i，計算其應該屬於的類 對於每一個類j，重新計算該類的質心 } |
K是我們事先給定的聚類數，
代表樣例i與k個類中距離最近的那個類，的值是1到k中的一個。
質心
代表我們對屬於同一個類的樣本中心點的猜測，拿星團模型來解釋就是要將所有的星星聚成k個星團，首先隨機選取k個宇宙中的點（或者k個星星）作為k個星團的質心，然後第一步對於每一個星星計算其到k個質心中每一個的距離。
然後選取距離最近的那個星團作為，這樣經過第一步每一個星星都有了所屬的星團；第二步對於每一個星團，重新計算它的質心（對裡面所有的星星坐標求平均）。重覆迭代第一步和第二步直到質心不變或者變化很小。
下圖展示了對n個樣本點進行K-means聚類的效果，這裡k取2。
K-means面對的第一個問題是如何保證收斂，前面的演演算法中強調結束條件就是收斂，可以證明的是K-means完全可以保證收斂性。下麵我們定性的描述一下收斂性，我們定義畸變函式（distortion function）如下：
J函式表示每個樣本點到其質心的距離平方和。K-means是要將J調整到最小。假設當前J沒有達到最小值，那麼首先可以固定每個類的質心，調整每個樣例的所屬的類別來讓J函式減少，同樣，固定，調整每個類的質心也可以使J減小。
這兩個過程就是內迴圈中使J單調遞減的過程。當J遞減到最小時，
和c也同時收斂。（在理論上，可以有多組不同的和c值能夠使得J取得最小值，但這種現象實際上很少見）。
由於畸變函式J是非凸函式，意味著我們不能保證取得的最小值是全域性最小值，也就是說k-means對質心初始位置的選取比較感冒，但一般情況下k-means達到的區域性最優已經滿足需求。但如果你怕陷入區域性最優，那麼可以選取不同的初始值跑多遍k-means，然後取其中最小的J對應的和c輸出。
下麵累述一下K-means與EM的關係，首先回到初始問題，我們目的是將樣本分成k個類，其實說白了就是求每個樣例x的隱含類別y，然後利用隱含類別將x歸類。
由於我們事先不知道類別y，那麼我們首先可以對每個樣例假定一個y吧，但是怎麼知道假定的對不對呢？怎麼評價假定的好不好呢？我們使用樣本的極大似然估計來度量，這裡是就是x和y的聯合分佈P(x,y)了。如果找到的y能夠使P(x,y)最大，那麼我們找到的y就是樣例x的最佳類別了，x順手就聚類了。
但是我們第一次指定的y不一定會讓P(x,y)最大，而且P(x,y)還依賴於其他未知引數，當然在給定y的情況下，我們可以調整其他引數讓P(x,y)最大。但是調整完引數後，我們發現有更好的y可以指定，那麼我們重新指定y，然後再計算P(x,y)最大時的引數，反覆迭代直至沒有更好的y可以指定。
這個過程有幾個難點，第一怎麼假定y？是每個樣例硬指派一個y還是不同的y有不同的機率，機率如何度量。第二如何估計P(x,y)，P(x,y)還可能依賴很多其他引數，如何調整裡面的引數讓P(x,y)最大。這些問題在以後的篇章裡回答。
這裡只是指出EM的思想，E步就是估計隱含類別y的期望值，M步調整其他引數使得在給定類別y的情況下，極大似然估計P(x,y)能夠達到極大值。然後在其他引數確定的情況下，重新估計y，周而複始，直至收斂。
上面的闡述有點費解，對應於K-means來說就是我們一開始不知道每個樣例
對應隱含變數也就是最佳類別
。
最開始可以隨便指定一個給它，然後為了讓P(x,y)最大（這裡是要讓J最小），我們求出在給定c情況下，J最小時的（前面提到的其他未知引數），然而此時發現，可以有更好的（質心與樣例距離最小的類別）指定給樣例，那麼得到重新調整，上述過程就開始重覆了，直到沒有更好的指定。
這樣從K-means裡我們可以看出它其實就是EM的體現，E步是確定隱含類別變數
，M步更新其他引數來使J最小化。這裡的隱含類別變數指定方法比較特殊，屬於硬指定，從k個類別中硬選出一個給樣例，而不是對每個類別賦予不同的機率。
總體思想還是一個迭代最佳化過程，有標的函式，也有引數變數，只是多了個隱含變數，確定其他引數估計隱含變數，再確定隱含變數估計其他引數，直至標的函式最優。
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
淘口令：複製以下紅色內容，再開啟手淘即可購買
範品社，使用￥極客T恤￥搶先預覽（長按複製整段文案，開啟手機淘寶即可進入活動內容）
近期，北京地區正常發貨，但派件時間有所延長。
