K-Means聚類演算法（一）：演算法思路

01-27

專欄剛剛成立，就有五十多人關注，讓我這個小屌絲誠惶誠恐，仔細思索該為諸位讀者大大們奉上怎樣的文章。一番思索、最後決定先從K-Means寫起，原因是，這個演算法的思路好懂，不需要知道背後的數學背景也能玩的起來，實現簡單（哪怕只要是能#include<math.h>的C語言都可以不是很複雜的構建起來），在工作中經常會用到（用來精簡和壓縮數據等等）。

最重要的一點是：經常有人用錯地方，不能使用歐氏距離作為相似度指標的地方也敢用！然後效果怎樣我就不說了！

如果您還不理解或者不知道K-Means：

我希望諸位讀完（一）以後，我的文章能讓諸位了解K-Means的原理，適用範圍和參數整定方法，掌握Matlab的能使用Matlab的kmeans工具進行實驗。

我希望（二）以後的時候每個掌握基礎編程的人都有用自己熟悉的語言開發一個基礎的K-Means的能力。

我希望在寫到（三）的時候每個掌握其變形使用方法，能優化演算法，並且添加自己的思路進去（比如數據權重）。

我希望寫完（四）以後，大家會了解它的數學背景。

PS1：雖說是「做每個人都能懂的筆記」，但是讓任何人都懂覺得還是難以做到，所以昨天在創建專欄的時候最後寫成了「做大部分人都能讀懂的數據科學筆記」

PS2：如果有任何不明白的地方歡迎討論，如果您具有相應的基礎知識（見下），但是覺得我寫的您看不懂，請一定告訴我！

PS3：如果覺得不錯，請點個贊，你們的贊是我寫這些文章和代碼的動力，我還有很多細心回答的答案，如果您覺得好也請點個贊。如果寫的不好……不要走，我會改的，我真的會改的TAT

正文開始：

以下是讀完這一文章需要的基礎知識：

n維歐氏空間 ${R}^{n}$ ， ${L}^{2}$ 距離，Matlab編程基礎知識。

我會遵循如下的順序介紹K-Means：

1、演算法概述概覽（本文）；

2、是演算法思路；

3、代碼實現和改進；

4、數學原理。

需要注意的是，數學原理並不是工作的過程或者演算法的實現，這個實現起來很簡單的演算法有著不是那麼單純的背景，PRML一書中將其歸類到「混合模型與EM」一章中去。而且，就算不知道原理我們也能把這個演算法擼的很爽，所以在最後才會介紹。

我會在（二）中提供我們自己實現的K-Means的演算法的源代碼，但是沒有接觸過這一類演算法的筒子們最好自己動手試一下，這演算法簡單，可以不依賴一些矩陣計算數學庫就較為輕鬆的實現，我這裡採用Matlab，主要是因為畫圖演示方便，自己實現的時候可以使用C，Python，C++，Java，VB，C#等任何支持數組，且你熟悉的語言完成。

所謂聚類演算法是指將一堆沒有標籤的數據自動劃分成幾類的方法，這個方法要保證同一類的數據有相似的特徵，如下圖所示：

K-Means演算法的特點是類別的個數是人為給定的，如果讓機器自己去找類別的個數，我們有AP聚類演算法，先不說，說了就跑題了。

K-Means的一個重要的假設是：數據之間的相似度可以使用歐氏距離度量，如果不能使用歐氏距離度量，要先把數據轉換到能用歐氏距離度量，這一點很重要。

（註：可以使用歐氏距離度量的意思就是歐氏距離越小，兩個數據相似度越高）

我們來看個反例：

圖中是一個瑞士卷形狀的流形，這個時候我們表示相似度應該用測地距離。什麼叫測地距離呢？就是在曲面上從A點走到B點（不允許離開曲面）的最短距離。

但是很明顯：測地距離很遠的兩個點有的時候會分在同一類（圖中同一種顏色），說明這個時候用歐氏距離就失效了。

這種情況怎麼處理呢？以後在講ISOMAP和LLE的時候提到如何使用KNN和最短路徑演算法等工具實現非歐空間到歐氏空間轉化，先不說，說了就跑題了。

K-Means演算法有個很著名的解釋，就是牧師-村民模型（這個故事是誰和我說的我忘了，以下是我的複述，有知道原作者的提醒我一下）：

有四個牧師去郊區佈道，一開始牧師們隨意選了幾個佈道點，並且把這幾個佈道點的情況公告給了郊區所有的居民，於是每個居民到離自己家最近的佈道點去聽課。
聽課之後，大家覺得距離太遠了，於是每個牧師統計了一下自己的課上所有的居民的地址，搬到了所有地址的中心地帶，並且在海報上更新了自己的佈道點的位置。
牧師每一次移動不可能離所有人都更近，有的人發現A牧師移動以後自己還不如去B牧師處聽課更近，於是每個居民又去了離自己最近的佈道點……
就這樣，牧師每個禮拜更新自己的位置，居民根據自己的情況選擇佈道點，最終穩定了下來。

以上就是K-Means演算法的一個過程。

我們考慮能用歐氏距離度量的情況：

那麼這樣一個在歐氏空間中用來聚類的演算法是怎麼工作的呢，那就具體說一下演算法：

首先我們得到了 ${R}^{n}$ 空間中的一堆點，這裡取2維空間（方便查看），可以是醬嬸的：

隨機生成k個聚類中心點（真心隨機生成，因為無所謂~但是盡量不要生成在一起）：

而後分別計算每一個數據點對這些中心的距離，把距離最短的那個當成自己的類別，或者中心點。

就好比你去買菜，家門口有菜場的，我不會穿個城到另外一條街去買，對吧~

這樣每個點都會有一個中心點了，這是隨機生成的中心點的結果，可以看到聚類的並不準確：

這個時候，身為中心點，覺得自己不能離群眾這麼遙遠，他要到群眾中去，這樣可以收復那些綠顏色的點，像這樣：

那麼他怎麼知道移動到哪裡呢？

當然是往群眾的中心移動啦！所有的屬於藍色類的點的中心，或者說坐標的平均值，就是藍色小圓圈要去的地方，於是他收穫了更多的群眾：

綠色的點也往群眾的中心移動，但是卻少了一批數據跟隨他，不過沒關係，反正這些變藍的點和現在自己所在的綠色大本營的格調（歐氏坐標）格格不入（距離太遠）。

於是僅僅2步，情況就成了這樣：

藍色的中心點又試著微調了幾次，綠色和紅色的也一樣，微調之後發現自己不需要動了，自己的群眾基礎已經穩定了，亂動可能脫離群眾，眾叛親離，所以這個時候演算法就收斂了。

如果用偽代碼描述，那麼過程是這樣的：

function K-Means(輸入數據，中心點個數K)n 獲取輸入數據的維度Dim和個數Nn 隨機生成K個Dim維的點n while(演算法未收斂)n 對N個點：計算每個點屬於哪一類。n 對於K個中心點：n 1，找出所有屬於自己這一類的所有數據點n 2，把自己的坐標修改為這些數據點的中心點坐標n endn 輸出結果：nendn

很多人已經急著想試一下了，那麼，在正式編程開始之前，我們不妨先使用Matlab提供的內置的K-Means感受一下（代碼在GitHub上自己下載，你的Matlab要支持K-Means哦，我的版本是r2015a）

DataScienceNote/TryKMeans.m at master · TsingJyujing/DataScienceNote · GitHub

實際編程的時候，我們會遇到如下問題：

1，怎麼初始化才能更快收斂不震蕩？

2，如果有一中心點初始化的時候離得遠了，或者被其它中心點包圍了，導致每個數據點都不肯找他怎麼辦？

3，如何評價演算法是否收斂？

4，演算法不收斂怎麼辦？

5，能不能給每個點設置權重？

……

還有這些奇奇怪怪的優化問題：

1，如何高效的使用Matlab計算歐氏距離？

2，如何快速計算出每一個點屬於哪一類？

3，如何保存和輸出結果？怎麼設計數據結構？

……

這些在K-Means聚類演算法的思路、實現、改進及原理（二）：演算法的實現里詳細討論。