K-Means 算法 | 酷殼 - CoolShell.cn
K-Means 算法
最近在學習一些數據挖掘的算法，看到了這個算法，也許這個算法對你來說很簡單，但對我來說，我是一個初學者，我在網上翻看了很多資料，發現中文社區沒有把這個問題講得很全面很清楚的文章，所以，把我的學習筆記記錄下來，分享給大家。
在數據挖掘中，? k -Means 算法 是一種? cluster analysis ?的算法，其主要是來計算數據聚集的算法，主要通過不斷地取離種子點最近均值的算法。
問題
K-Means算法主要解決的問題如下圖所示。我們可以看到，在圖的左邊有一些點，我們用肉眼可以看出來有四個點群，但是我們怎么通過計算機程序找出這幾個點群來呢？于是就出現了我們的K-Means算法（ Wikipedia鏈接 ）
K-Means 要解決的問題
算法概要
這個算法其實很簡單，如下圖所示：
?
K-Means 算法概要
從上圖中，我們可以看到， A, B, C, D, E 是五個在圖中點。而灰色的點是我們的種子點，也就是我們用來找點群的點 。有兩個種子點，所以K=2。
然后，K-Means的算法如下：
- 隨機在圖中取K（這里K=2）個種子點。
- 然后對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那么Pi屬于Si點群。（上圖中，我們可以看到A,B屬于上面的種子點，C,D,E屬于下面中部的種子點）
- 接下來，我們要移動種子點到屬于他的“點群”的中心。（見圖上的第三步）
- 然后重復第2）和第3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A,B,C，下面的種子點聚合了D，E）。
這個算法很簡單，但是有些細節我要提一下，求距離的公式我不說了，大家有初中畢業水平的人都應該知道怎么算的。我重點想說一下“求點群中心的算法”
求點群中心的算法
一般來說，求點群中心點的算法你可以很簡的使用各個點的X/Y坐標的平均值。不過，我這里想告訴大家另三個求中心點的的公式：
1）Minkowski Distance 公式 —— ?λ 可以隨意取值，可以是負數，也可以是正數，或是無窮大。
2）Euclidean Distance 公式 —— 也就是第一個公式?λ=2 的情況
3）CityBlock Distance 公式 ——?也就是第一個公式?λ=1 的情況
這三個公式的求中心點有一些不一樣的地方，我們看下圖（對于第一個 λ 在 0-1之間）。
? ?
?
（1）Minkowski Distance ? ? （2） Euclidean Distance ? ?（3）? CityBlock Distance
上面這幾個圖的大意是他們是怎么個逼近中心的，第一個圖以星形的方式，第二個圖以同心圓的方式，第三個圖以菱形的方式。
K-Means的演示
如果你以” K Means Demo “為關鍵字到Google里查你可以查到很多演示。這里推薦一個演示
http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
操作是，鼠標左鍵是初始化點，右鍵初始化“種子點”，然后勾選“Show History”可以看到一步一步的迭代。
注：這個演示的鏈接也有一個不錯的 K Means Tutorial 。
K-Means ++ 算法
K-Means主要有兩個最重大的缺陷——都和初始值有關：
- ?K 是事先給定的，這個 K 值的選定是非常難以估計的。很多時候，事先并不知道給定的數據集應該分成多少個類別才最合適。（? ISODATA 算法 通過類的自動合并和分裂，得到較為合理的類型數目 K）
- K-Means算法需要用初始隨機種子點來搞，這個隨機種子點太重要，不同的隨機種子點會有得到完全不同的結果。（ K-Means++算法 可以用來解決這個問題，其可以有效地選擇初始點）
我在這里重點說一下?K-Means++算法步驟：
- 先從我們的數據庫隨機挑個隨機點當“種子點”。
- 對于每個點，我們都計算其和最近的一個“種子點”的距離D( x )并保存在一個數組里，然后把這些距離加起來得到Sum(D( x ))。
- 然后，再取一個隨機值，用權重的方式來取計算下一個“種子點”。這個算法的實現是，先取一個能落在Sum(D( x ))中的隨機值Random，然后用Random?-=?D( x )，直到其<=0，此時的點就是下一個“種子點”。
- 重復第（2）和第（3）步直到所有的K個種子點都被選出來。
- 進行K-Means算法。
相關的代碼你可以在這里找到“ implement the K-means++ algorithm ”(墻) 另， Apache 的通用數據學庫也實現了這一算法
K-Means 算法應用
看到這里，你會說，K-Means算法看來很簡單，而且好像就是在玩坐標點，沒什么真實用處。而且，這個算法缺陷很多，還不如人工呢。是的，前面的例子只是玩二維坐標點，的確沒什么意思。但是你想一下下面的幾個問題：
1）如果不是二維的，是多維的，如5維的，那么，就只能用計算機來計算了。
2）二維坐標點的X, Y 坐標，其實是一種向量，是一種數學抽象。現實世界中很多屬性是可以抽象成向量的，比如，我們的年齡，我們的喜好，我們的商品，等等，能抽象成向量的目的就是可以讓計算機知道某兩個屬性間的距離。如：我們認為，18歲的人離24歲的人的距離要比離12歲的距離要近，鞋子這個商品離衣服這個商品的距離要比電腦要近，等等。
只要能把現實世界的物體的屬性抽象成向量，就可以用K-Means算法來歸類了 。
在 《 k均值聚類(K-means) 》?這篇文章中舉了一個很不錯的應用例子，作者用亞洲15支足球隊的2005年到1010年的戰績做了一個向量表，然后用K-Means把球隊歸類，得出了下面的結果，呵呵。
- 亞洲一流：日本，韓國，伊朗，沙特
- 亞洲二流：烏茲別克斯坦，巴林，朝鮮
- 亞洲三流：中國，伊拉克，卡塔爾，阿聯酋，泰國，越南，阿曼，印尼
其實，這樣的業務例子還有很多，比如，分析一個公司的客戶分類，這樣可以對不同的客戶使用不同的商業策略，或是電子商務中分析商品相似度，歸類商品，從而可以使用一些不同的銷售策略，等等。
最后給一個挺好的算法的幻燈片： http://www.cs.cmu.edu/~guestrin/Class/10701-S07/Slides/clustering.pdf
（全文完）
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
