K-means Clustering Algorithm 中文名也許叫“K均值聚類算法”，是統(tǒng)計學(xué)和數(shù)據(jù)挖掘領(lǐng)域中常用的一種算法。維基百科上是這樣介紹的：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個類，使得每一類中的觀察值與該類的均值最接近，與其他的類的均值較遠(yuǎn)）。

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

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

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

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

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

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

***要感謝一下數(shù)據(jù)挖掘老師  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/