k-means算法

聚類分析是數據分析中，非常重要的一類課題。他的作用是將大量的無標簽數據通過計算，自動為其標注標簽。眾所周知，這一點是區別于數據分類技術的。而現實的場景中，無標簽的數據顯然多于有標簽數據，因此，我在這里也是先說聚類，后面的博文，再說分類。

聚類的目的，是要將數據歸為不同的類，基本原則是要相近的數據盡量歸為一類，而不同類之間的數據則要盡量有比較大的差別。

說到聚類，當然最先想到的就是k-means算法。它不僅是最簡單的聚類算法，也是最普及且最常用的。k-means算法是一種基于形心的劃分數據的方法。我們給定一個數據集D$D$，以及要劃分的簇數k$k$，就能通過該算法將數據集劃分為k$k$個簇。一般來說，每個數據項只能屬于其中一個簇。具體方法可以這樣描述：

下面，通過一個例子，展示k-means的細節。

我們來處理一個簡單的二維平面上的聚類問題。數據集為：A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4,9)，如圖Fig.1:

現在，我們選擇：A1, B1, C1三個點作為初始的簇心，將這個數據集分成三類。

第一步，令所有數據點選擇距離他們最近的簇心，并且執行歸類：歸類的結果如圖Fig.1中虛線所圈出來的那樣：

第二步，更新簇心，重新計算距離，再次執行歸類，結果如圖Fig.2所示，圖中,我用紅色*號表示簇心：

第三步，重復進行前兩步，直到簇心不在變更為止，最終，得到Fig.3中所示的聚類結果，圖中,我用紅色*號表示簇心：

可見，整個算法就是一個迭代的過程。需要注意的是，初始簇心的選擇有時候會影響最終的聚類結果，所以，實際操作中，我們一般會選用不同的數據作為初始簇心，多次執行k-means算法。

由于篇幅限制，詳細的實現代碼我在我的github主頁中給出：kmeans，這里省略。

最后，我們對k-means算法作簡要分析：

k-means++算法

k-means++是k-means的變形，通過小心選擇初始簇心，來獲得較快的收斂速度以及聚類結果的質量，本文中，我們將簡單介紹k-means++. 首先，一定要先理解k-means++的原理。

它是這樣去做的：先隨機選擇一個數據項作為第一個初始的簇心（當然，最終我們要選擇k$k$個），根據這1個簇心，我們通過一系列計算，獲得第2個簇心，再根據這2個簇心，通過計算獲得第3個簇心。。。以此類推，最終，獲得全部的k$k$個簇心，然后，再按照上面k-means的做法，做聚類分析。其中，至于下一個簇心的選擇需要經過怎樣的計算，我們放到后面再說?，F在需要明白的是，通過增加合理計算的方式，我們不再是隨機選取k$k$個簇心作為初始值，而是通過一種迭代算法，合理選擇簇心。

那么究竟怎樣的選擇就是合理的選擇呢？在此我們有這樣一個原則：假設現在已經選擇了r$r$個簇心，要接著選取第r+1$r+1$個簇心。那么當然是應該選擇距離其簇心較遠的數據點當新的簇心?？梢阅X補這樣一個場景：r$r$個簇心，每個數據點都對應著且只對應著一個簇心，這個簇心當然是相對于其他r?1$r-1$個簇心來說，是距離這個數據點最近的。于是每個點，都與其簇心有條連線，連線的長度就是這個數據點到簇心的距離，我們現在要做的，就是選擇距離其簇心距離較大的那個數據點。

你可能會說，這個道理很簡單，但是應該是選擇距離“最大”的才對，為什么選擇距離“較大”的呢？那是因為這里面可能會存在數據噪聲的問題，也可能由于我們至少第一個簇心的選擇還是隨機的緣故，導致如果這樣每次都“精確”選擇，反而最終的聚類效果不佳。所以，一種比較合理的做法是選擇“較大”，而非“最大”。當然，從這一點，我們也能看出，k-means++即使比傳統的k-means更好，卻依然是一種啟發式的算法，不能說這種做法最終的結果就一定是最優的。

現在的問題就全部集中在如何選擇離簇心距離“較大”的數據點了。假設，現在將所有的數據點與其對應簇心連接，那么會構成n$n$條連線（n$n$是數據項的個數，自己與自己連接的情況，可以看做是構成了一條長度為0的線），我們記這n$n$條連線的長度為Dis1,Dis2,…Disn$Dis_1, Dis_2, /dots Dis_n$，然后把這n$n$條連線按隨機的順序，首尾相連，構成一條長度為∑Disi$/sum{Dis_i}$的連線，然后現在隨機拋出一點，落在這條“總線”上，那么顯然，落在距離較長的線上的概率更高一些，如Fig.4所示，假設D1,D2,D3$D_1, D_2, D_3$距離其對應簇心的長度分別是1, 2, 3，那當然是落在Dis3$Dis_3$上的概率最高了。選擇下一簇心的具體方法操作如下：

綜上，k-means++算法步驟如下：

k-means++雖然在初始簇心的選擇上比k-means更優，但是依然也有缺陷，比如，下一個簇心的選擇總是依賴于已有的簇心，后來k-means||算法，改進了這一缺點，這里就不再做過多介紹了。

k-means++算法和前面k-means算法的全部代碼以及測試數據我都放在了github上：kmeans，歡迎參考指正。