K-means Clustering Algorithm 中文名也許叫“K均值聚類算法”，是統(tǒng)計(jì)學(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個(gè)觀察值分成k個(gè)類，使得每一類中的觀察值與該類的均值最接近，與其他的類的均值較遠(yuǎn)）。

先來看一個(gè)最簡單、最直觀的圖示。

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

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

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

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

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

***要感謝一下數(shù)據(jù)挖掘老師  Devert Alexandre，因?yàn)楸疚牡膱D片都是從他的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/