K-Means 分群演算法

人工智慧

前言

簡介

知識表達

知識學習

理論方法

搜尋優化

邏輯推論

神經網路

機率統計

實務應用

專家系統

自然語言

分群分類

程式語言

Prolog

javascript

程式實作

邏輯推論

爬山算法

基因算法

機率學習

交談程式

數字辨識

訊息

相關網站

參考文獻

最新修改

簡體版

English

K-Means 是 J. B. MacQueen 於1967年所提出的分群演算法,必須事前設定群集的數量 k,然後找尋下列公式的極大值,以達到分群的最佳化之目的。

(1)
\begin{align} argmin \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \big\| \mathbf x_j - \boldsymbol\mu_i \big\|^2 \end{align}

其中的 $\mu_i$ 是 Si 群體的平均。

演算法

  • 1. 隨機指派群集中心:(圖一)
    • 在訓練組資料中「隨機」找出K筆紀錄來作為初始種子(初始群集的中心)
  • 2. 產生初始群集:(圖二)
    • 計算每一筆紀錄到各個隨機種子之間的距離,然後比較該筆紀錄究竟離哪一個隨機種子最近,然後這筆紀錄就會被指派到最接近的那個群集中心,此時就會形成一個群集邊界,產生了初始群集的成員集合
  • 3. 產生新的質量中心:(圖三)
    • 根據邊界內的每一個案例重新計算出該群集的質量中心,利用新的質量中心取代之前的隨機種子,來做為該群的中心
(2)
\begin{align} S_i^{(t)} = \left\{ \mathbf x_j : \big\| \mathbf x_j - \mathbf m^{(t)}_i \big\| \leq \big\| \mathbf x_j - \mathbf m^{(t)}_{i^*} \big\| \text{ for all }i^*=1,\ldots,k \right\} \end{align}
  • 4. 變動群集邊界:(圖四)
    • 指定完新的質量中心之後,再一次比較每一筆紀錄與新的群集中心之間的距離,然後根據距離,再度重新分配每一個案例所屬的群集
(3)
\begin{align} \mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf x_j \in S^{(t)}_i} \mathbf x_j \end{align}
  • 5. 持續反覆 3, 4 的步驟,一直執行到群集成員不再變動為止
K-MeanEx1.jpg

圖一、隨機指派群集中心

K-MeanEx2.jpg

圖二、產生初始群集

K-MeanEx3.jpg

圖三、產生新的質量中心

K-MeanEx4.jpg

圖四、變動群集邊界

參考文獻

  1. J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations", Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297
  2. J. A. Hartigan (1975) "Clustering Algorithms". Wiley.
  3. J. A. Hartigan and M. A. Wong (1979) "A K-Means Clustering Algorithm", Applied Statistics, Vol. 28, No. 1, p100-108.
  4. D. ArthurS. Vassilvitskii (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
  5. http://en.wikipedia.org/wiki/K-means_clustering
  6. http://zh.wikipedia.org/wiki/K平均演算法
  7. http://140.118.9.173/salo/data%20mining/Ch5 群集演算法.pdf
  8. 漫谈 Clustering (1): k-means — http://blog.pluskid.org/?p=17

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License