# 分群 Clustering
###### tags: `Machine Learning`
本篇會提到以下分群演算法
* K-Means
* K-Means ++

## 前言
分群（集群），clustering，屬於非監督式學習方法。
非監督學習式機器學習的一種方法，沒有給定事先標記的資料（ground truth），會對自動對輸入的資料進行分類或分群。

## K-Means
### 介紹
* 源於訊號處理中的一種向量量化方法，現在則更多地作為一種群集分析方法，流行於資料探勘領域。
* 目的：把 n 個點劃分到 k 個群中，使得每個點都屬於離他最近的<font color='blue'>均值</font>（即<font color='blue'>群中心</font>）對應的群，以之作為群的標準。
* K-Means 跟 KNN（K-Nearest）沒有任何關聯ㄛ

更詳細的內容可以看[機器學習: 集群分析 K-means Clustering](https://chih-sheng-huang821.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E9%9B%86%E7%BE%A4%E5%88%86%E6%9E%90-k-means-clustering-e608a7fe1b43)以及[Machine Learning A-Z筆記17-K-means](https://zhuanlan.zhihu.com/p/97510390)。

### 步驟
1. 先設定好要分成多少（k）群。
2. 然後在feature space（資料是 d 維，則會組出 d 維空間）隨機給 k 個群心。
3. 每個資料都會所有 k 個群心算歐式距離（歐基里德距離 Euclidean distance，其實就是直線距離公式。當然也可以換成別種距離公式如馬式距離、漢明距離、餘弦距離等，但基本上都還是以歐式距離為主)。
4. 將每筆資料分類判給距離最近的那個群心。
5. 每個群心內都會有被分類過來的資料，用這些資料更新一次新的群心。
6. 一直重複 3–5，直到所有群心不再有太大的變動（收斂），結束。

### 選擇要分幾群 - WCSS（within-cluster sum of squares）
WCSS，組內平方和，公式如下：
若 WCSS 為0，則 K 必須等於總數據點個數，這樣的分類跟沒有是一樣的。
* Elbow method，手肘法
透過嘗試多種類別個數，並將相應的 WCSS 記錄下來並且畫出，理想上最佳的K值應該是最大轉折處。
以下圖為例，$K=3$ 就已經足夠，再大的 K 值其實已經無意義了。
但手肘法不是絕對的，它只是幫助你客觀判斷。實際上 K 應該等於多少是取決於你的研究所需。
## K-Means ++
### 簡介
在 K-Means 算法下，我們會在輸入的數據集中隨機選擇 k 個點作為 seeds，但是隨機選擇初始 seeds 可能會造成**群的結果和數據的實際分布相差很大**。而K-means++算法就是想解決該問題，其選擇初始seeds的基本思想就是：初始的群中心之間的相互距離要儘可能的遠。
更詳細的可以參考[機器學習：生動理解K-means進階算法——K-means++](https://kknews.cc/code/b4axoe6.html)。

### 步驟
1. 從輸入的資料點集合中，隨機選擇一個點作為第一個群中心。
2. 對於資料集中的每一個點 x，計算他與最近群中心（指<font color='blue'>已選擇的群中心</font>的距離，記作 $D(x)$。
3. 選擇一個新的資料點作為新的群中心。
* 選擇的原則：$D(x)$ 較大的點被選成群中心的**機率**較大。

4. 重複 2、3，直到 k 個群中心被選出來。
5. 利用這 k 個初始的群中心來運行標準的 K-Means 算法。