K-means Clustering Algorithm 中文名也許叫“K均值聚類算法”，是統計學和數據挖掘領域中常用的一種算法。維基百科上是這樣介紹的：k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean（將n個觀察值分成k個類，使得每一類中的觀察值與該類的均值最接近，與其他的類的均值較遠）。

先來看一個最簡單、最直觀的圖示。

上圖有很多點，現在想將他們分成3個cluster，怎么辦？ 作為人，一眼就看出來了，但是計算機就沒那么容易分類了，我們必須借助一些算法，而k-means就是其中的一種。K-means不僅可以處理二維空間的聚類，還可以擴展到n維向量空間，還可以處理字符、圖像、聲音等等。

以上圖為例，K-means算法的基本步驟如下：
輸入：一個要處理的數據集（例如上圖的點集），分成cluster的個數（比如3個），一個mean的計算方法（比如兩點之間的距離函數，）
Step1. 首先隨機的給每個點標上一種顏色，并計算同種顏色點坐標的算術平均值，表示出相 應的均值點。
Step2. 根據目前算出的均值點，將所有的點集分成3類，為每一類中的每個點，標上與離它最近的均值點相同的顏色。怎么分呢？這里要介紹一種“泰森多邊形法”，英文名叫“Voronoi diagram”（見文章***維基百科鏈接）。于是就有了下面這張圖。

Step3.重復step2，直到所有點的顏色不再變化為止。
算法結束，輸出如下結果。

上面的例子在簡單的二維空間里，如果放在三維空間那么mean的計算方法就要修改了。事實上在處理多維空間、字符、圖像等問題時，不同的問題有不同的計算公式，這時mean的意思可能就不是“均值”了，也許用“相似度”和“相異度”來衡量個體之間的關系會更好，詳見參考文章一。

按照慣例，下面應該貼上我自己寫的k-means算法代碼了，不過很遺憾的是我現在還在摸索用python的numpy庫和matplotlib庫畫圖的方法，在參考文章二中有一個python語言的代碼。

***要感謝一下數據挖掘老師  Devert Alexandre，因為本文的圖片都是從他的slides里截出來的。^_^

參考文章一
參考文章二
維基百科k-means鏈接
泰森多邊形法維基百科鏈接（Voronoi diagram）

原文鏈接：http://blog.nlogn.cn/%E6%95%B0%E6%8D%AE%E6%8C%96%E6%8E%98-k-means-%E7%AE%97%E6%B3%95/