輕鬆聊之K-Means演算法

上次跟大家簡單介紹了一下KNN演算法，今天介紹一下很容易跟KNN搞混的K-means演算法，不過兩個其實差蠻多的，只有名字比較像而已。K-means主要講的就是「物以類聚」，只要中心思想是相近的，就可以歸在同一類。

K-means是一個分群(Clustering)的演算法，不需要有預先標記好的資料(unlabeled data)，屬於非監督式學習(Unsupervised learning)。主要是用來做常常被使用在資料分群，簡單的說就是把一堆資料根據你判斷相近的邏輯，把這一堆資料分成k群。

用比較數學(嚇人)的說法就是，追求各個群組內部的均方誤差總和最小。

$$arg min \sum_{i=1}^{k}\sum_{x_j \in S_i}||X_j - \mu_i||^2$$

$(x_1, x_2,x_3...,x_n)為給定的資料集合$

$S = {S_1, S_2, …, S_k}$, S為分割的群組集合

$\mu_i$是群組$S_i$內所有元素$x_j$的重心，或叫中心點。

下面這個圖是一個資料根據不同K所分群出來的結果，顏色只是提供辨識分群用。

圖片來源: Statistical Learning (Stanford Online Course )

運作流程

我們先來看一下它運作的流程。

1. 先決定K
   k就是最後要分成幾群，如果你希望最後資料分成 3群 ，k就是3。
2. 在你的資料中，隨機選擇k個點做為群中心(也可以直接從資料挑)。
3. 把每一筆資料標記上離它最近的群中心
4. 根據同一個標記的所有資料，重新計算出群中心。
5. 如果步驟4算出來的群中心跟原本步驟3不同，則重複步驟3

上面的步驟可以用下圖來表示，

圖片來源: Machine Learning (By Andrew NG, Coursera)

1. 我們要分成兩群(K=2),所以一開始先挑了兩個點(b)。

2. 將資料標記(著色)成距離最近的群中心(c)。

3. 同一個群中心(顏色)的資料重新計算新的中心位置(d)。

4. 同步驟2，做標記(著色的動作)。

5. 同步驟3，重新計算新的群中心的位置(f)。

6. 再重複步驟2,3 結果群中心位置不變，表示分群完畢。

注意須知

K-means一開始的亂數選擇群中心，會影響到最後分群的結果，下圖這個就使用K=3跑6次出來的結果，紅色235.8為產生出來的最佳的分群。

圖片來源: Statistical Learning (Stanford Online Course )

關於怎麼避免一開始的選擇影響最後分群品質，這個等我研究有心得再跟大家分享。

後記

K-means簡單快速的方法被廣泛的使用，但是實際運用上還是有一些問題需要被克服。正所謂萬事起頭難，K-means一開始會先要求你提供K，但是k到底要多少才合理？ 這個問題我們有空再來談。下次我們來分享一下不給定K的狀況下，我們要怎麼將資料分群。