K-Means 算法 | 酷殼 - CoolShell.cn

K-Means 算法

2012年6月29日 陳皓 發(fā)表評(píng)論 閱讀評(píng)論 13,428 人閱讀 ? ?

最近在學(xué)習(xí)一些數(shù)據(jù)挖掘的算法，看到了這個(gè)算法，也許這個(gè)算法對(duì)你來說很簡(jiǎn)單，但對(duì)我來說，我是一個(gè)初學(xué)者，我在網(wǎng)上翻看了很多資料，發(fā)現(xiàn)中文社區(qū)沒有把這個(gè)問題講得很全面很清楚的文章，所以，把我的學(xué)習(xí)筆記記錄下來，分享給大家。

在數(shù)據(jù)挖掘中，? k -Means 算法 是一種? cluster analysis ?的算法，其主要是來計(jì)算數(shù)據(jù)聚集的算法，主要通過不斷地取離種子點(diǎn)最近均值的算法。

問題

K-Means算法主要解決的問題如下圖所示。我們可以看到，在圖的左邊有一些點(diǎn)，我們用肉眼可以看出來有四個(gè)點(diǎn)群，但是我們?cè)趺赐ㄟ^計(jì)算機(jī)程序找出這幾個(gè)點(diǎn)群來呢？于是就出現(xiàn)了我們的K-Means算法（ Wikipedia鏈接 ）

K-Means 要解決的問題

算法概要

這個(gè)算法其實(shí)很簡(jiǎn)單，如下圖所示：

?

K-Means 算法概要

從上圖中，我們可以看到， A, B, C, D, E 是五個(gè)在圖中點(diǎn)。而灰色的點(diǎn)是我們的種子點(diǎn)，也就是我們用來找點(diǎn)群的點(diǎn) 。有兩個(gè)種子點(diǎn)，所以K=2。

然后，K-Means的算法如下：

1. 隨機(jī)在圖中取K（這里K=2）個(gè)種子點(diǎn)。
2. 然后對(duì)圖中的所有點(diǎn)求到這K個(gè)種子點(diǎn)的距離，假如點(diǎn)Pi離種子點(diǎn)Si最近，那么Pi屬于Si點(diǎn)群。（上圖中，我們可以看到A,B屬于上面的種子點(diǎn)，C,D,E屬于下面中部的種子點(diǎn)）
3. 接下來，我們要移動(dòng)種子點(diǎn)到屬于他的“點(diǎn)群”的中心。（見圖上的第三步）
4. 然后重復(fù)第2）和第3）步，直到，種子點(diǎn)沒有移動(dòng)（我們可以看到圖中的第四步上面的種子點(diǎn)聚合了A,B,C，下面的種子點(diǎn)聚合了D，E）。

這個(gè)算法很簡(jiǎn)單，但是有些細(xì)節(jié)我要提一下，求距離的公式我不說了，大家有初中畢業(yè)水平的人都應(yīng)該知道怎么算的。我重點(diǎn)想說一下“求點(diǎn)群中心的算法”

求點(diǎn)群中心的算法

一般來說，求點(diǎn)群中心點(diǎn)的算法你可以很簡(jiǎn)的使用各個(gè)點(diǎn)的X/Y坐標(biāo)的平均值。不過，我這里想告訴大家另三個(gè)求中心點(diǎn)的的公式：

1）Minkowski Distance 公式 —— ?λ 可以隨意取值，可以是負(fù)數(shù)，也可以是正數(shù)，或是無窮大。

2）Euclidean Distance 公式 —— 也就是第一個(gè)公式?λ=2 的情況

3）CityBlock Distance 公式 ——?也就是第一個(gè)公式?λ=1 的情況

這三個(gè)公式的求中心點(diǎn)有一些不一樣的地方，我們看下圖（對(duì)于第一個(gè) λ 在 0-1之間）。

? ? ?

（1）Minkowski Distance ? ? （2） Euclidean Distance ? ?（3）? CityBlock Distance

上面這幾個(gè)圖的大意是他們是怎么個(gè)逼近中心的，第一個(gè)圖以星形的方式，第二個(gè)圖以同心圓的方式，第三個(gè)圖以菱形的方式。

K-Means的演示

如果你以” K Means Demo “為關(guān)鍵字到Google里查你可以查到很多演示。這里推薦一個(gè)演示

http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html

操作是，鼠標(biāo)左鍵是初始化點(diǎn)，右鍵初始化“種子點(diǎn)”，然后勾選“Show History”可以看到一步一步的迭代。

注：這個(gè)演示的鏈接也有一個(gè)不錯(cuò)的 K Means Tutorial 。

K-Means ++ 算法

K-Means主要有兩個(gè)最重大的缺陷——都和初始值有關(guān)：

• ?K 是事先給定的，這個(gè) K 值的選定是非常難以估計(jì)的。很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。（? ISODATA 算法 通過類的自動(dòng)合并和分裂，得到較為合理的類型數(shù)目 K）

• K-Means算法需要用初始隨機(jī)種子點(diǎn)來搞，這個(gè)隨機(jī)種子點(diǎn)太重要，不同的隨機(jī)種子點(diǎn)會(huì)有得到完全不同的結(jié)果。（ K-Means++算法 可以用來解決這個(gè)問題，其可以有效地選擇初始點(diǎn)）

我在這里重點(diǎn)說一下?K-Means++算法步驟：

1. 先從我們的數(shù)據(jù)庫隨機(jī)挑個(gè)隨機(jī)點(diǎn)當(dāng)“種子點(diǎn)”。
2. 對(duì)于每個(gè)點(diǎn)，我們都計(jì)算其和最近的一個(gè)“種子點(diǎn)”的距離D( x )并保存在一個(gè)數(shù)組里，然后把這些距離加起來得到Sum(D( x ))。
3. 然后，再取一個(gè)隨機(jī)值，用權(quán)重的方式來取計(jì)算下一個(gè)“種子點(diǎn)”。這個(gè)算法的實(shí)現(xiàn)是，先取一個(gè)能落在Sum(D( x ))中的隨機(jī)值Random，然后用Random?-=?D( x )，直到其<=0，此時(shí)的點(diǎn)就是下一個(gè)“種子點(diǎn)”。
4. 重復(fù)第（2）和第（3）步直到所有的K個(gè)種子點(diǎn)都被選出來。
5. 進(jìn)行K-Means算法。

相關(guān)的代碼你可以在這里找到“ implement the K-means++ algorithm ”(墻) 另， Apache 的通用數(shù)據(jù)學(xué)庫也實(shí)現(xiàn)了這一算法

K-Means 算法應(yīng)用

看到這里，你會(huì)說，K-Means算法看來很簡(jiǎn)單，而且好像就是在玩坐標(biāo)點(diǎn)，沒什么真實(shí)用處。而且，這個(gè)算法缺陷很多，還不如人工呢。是的，前面的例子只是玩二維坐標(biāo)點(diǎn)，的確沒什么意思。但是你想一下下面的幾個(gè)問題：

1）如果不是二維的，是多維的，如5維的，那么，就只能用計(jì)算機(jī)來計(jì)算了。

2）二維坐標(biāo)點(diǎn)的X, Y 坐標(biāo)，其實(shí)是一種向量，是一種數(shù)學(xué)抽象。現(xiàn)實(shí)世界中很多屬性是可以抽象成向量的，比如，我們的年齡，我們的喜好，我們的商品，等等，能抽象成向量的目的就是可以讓計(jì)算機(jī)知道某兩個(gè)屬性間的距離。如：我們認(rèn)為，18歲的人離24歲的人的距離要比離12歲的距離要近，鞋子這個(gè)商品離衣服這個(gè)商品的距離要比電腦要近，等等。

只要能把現(xiàn)實(shí)世界的物體的屬性抽象成向量，就可以用K-Means算法來歸類了 。

在 《 k均值聚類(K-means) 》?這篇文章中舉了一個(gè)很不錯(cuò)的應(yīng)用例子，作者用亞洲15支足球隊(duì)的2005年到1010年的戰(zhàn)績(jī)做了一個(gè)向量表，然后用K-Means把球隊(duì)歸類，得出了下面的結(jié)果，呵呵。

• 亞洲一流：日本，韓國，伊朗，沙特
• 亞洲二流：烏茲別克斯坦，巴林，朝鮮
• 亞洲三流：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼

其實(shí)，這樣的業(yè)務(wù)例子還有很多，比如，分析一個(gè)公司的客戶分類，這樣可以對(duì)不同的客戶使用不同的商業(yè)策略，或是電子商務(wù)中分析商品相似度，歸類商品，從而可以使用一些不同的銷售策略，等等。

最后給一個(gè)挺好的算法的幻燈片： http://www.cs.cmu.edu/~guestrin/Class/10701-S07/Slides/clustering.pdf

（全文完）

K-Means 算法 | 酷殼 - CoolShell.cn