k-means Clustering－基礎分群的推導及介紹

前言

在資料前處理或是資料視覺化時，我們常常需要將資料點分群(clustering)，注意分群和分類的不同在於，分類問題的資料除了有特徵值之外還有附帶類別，例如在圖片分類中，有貓、狗的圖片以及相對應的類別，即貓或狗，但是分群的問題中資料點只有多維特徵，但是沒有對應的類別，因此我們需要依靠演算法幫助我們利用特徵的相似性或是距離，將相近的資料分為一群，不相近的資料分為另一群。

假設我們有 $N$ 筆資料 $ \{\mathbf{x}_1, …, \mathbf{x}_N\} $，其中 $ \mathbf{x}_n $，我們的目標是將這些資料分成 $K$ 群。這裡我們引入一個變數 $r_{nk} \in \{0, 1\}$ 對應到每筆資料 $x_n$，當 $ r_{nk} = 1$ 時代表 $x_n$ 這筆資料屬於第 $k$ 群，並且 $r_{nj} = 0$ for $j \neq k$，代表每筆資料只能屬於某一群。這種 $r_{nk}$ 的表示方式稱做 1-of-K coding。我們為每個群引入另外一個變數 $\mathbf{\mu}_k, \text{for } k \in \{1,…,K\}$，這個向量可以視為代表第 $k$ 群的向量，實際上在後續推導 $\mathbf{\mu}_k$ 為各群之 mean：$$
\mathbf{\mu}_k = \frac{\sum_{n = 1}^{N} r_{nk} x_n}{\sum_{n = 1}^{N} r_{nk}}
$$ 我們的目標是找出所有 $r_{nk}$ 和 $\mu_k$，並且希望這兩個參數能夠讓群類的資料點距離越近越好。

首先我們先定義出目標函數如下：$$
J = \sum_{n=1}^N \sum_{k=1}^K r_{nk} ||\mathbf{x}_n – \mu_{k}||^2
$$ 簡單來說 $J$ 代表每筆資料點和對應的群平均值 $\mathbf{\mu}_k$ 之距離總和。我們的目標就是讓 $J$ 越小越好，因為直觀來說最佳的狀態就是群內資料點之間的距離越小越好，代表該群越緊密、相似性越高，理應被分配到同一群。

想要找出 $J$ 的最小值可以利用迭代式的最佳化方法，先固定 $\mathbf{\mu}_{k}$ 找出最佳的 $r_{nk}$，固定 $r_{nk}$ 後再求出最佳 $\mathbf{\mu}_{k}$，以上述順序依序迭代更新兩個參數 $r^1_{nk} \rightarrow \mathbf{\mu}^1_{k} \rightarrow r^2_{nk} \rightarrow …$，這種依序迭代更新的方式稱為 Expectation and Maximization (EM) algorithm。

Update $r_{nk}$

首先，我們先固定 $\mathbf{\mu}_{k}$，以 $r_{nk}$ 的角度最佳化函數 $J$，我們可以看到函數 $J$ 對於 $r_{nk}$ 是一個線性函數，若我們想要降低 $J$ 值則我們會希望當 $r_{nk} = 1$ 時，對應的 $||\mathbf{x}_n – \mu_{k}||^2$ 越小越好，要達成這個目的的方式就是計算 $\mathbf{x}_n$ 和所有 $\mathbf{\mu}_k, k \in \{1,…,K\}$ 距離 $||\mathbf{x}_n – \mu_{k}||^2$，找出最小距離的群 $k$ 後將對應的 $r_{nk}$ 設為 $1$ 其它為 $0$，數學式表達如下：
$$
\begin{equation}
r_{nk} =
\begin{cases}
1 & \text{if } k = \arg\min_j ||\mathbf{x}_n – \mu_{j}||^2 \\
0 & \text{otherwise}
\end{cases}
\end{equation}
$$

需要注意的是想要求出 $r_{nk}$ 必須有初始值 $\mathbf{\mu}_k, \text{for } k \in \{1,…,K\}$，我們可以給予 $\mathbf{\mu}_{k}$ 一個隨機值再開始更新，因為函數 $J$ 為一 convex function，因此必定會收斂至最佳解。我們也可以從隨機挑選幾筆資料並將他們的平均值作為起始 $\mathbf{\mu}_{k}$ 避免隨機挑選的起始值離資料點過於遙遠，從較佳的起始值開始更新可以有效減少迭代次數。

Update $\mathbf{\mu}_{k}$

依上述方式找出 $r_{nk}$ 後，我們針對 $\mathbf{\mu}_{k}$ 最佳化 $J$，$J$ 對於 $\mathbf{\mu}_{k}$ 是一個 convex function，要找到最佳解可以利用偏微分並設為 $0$，以此求得 $\mathbf{\mu}_{k}$：
$$
\begin{aligned}
&\frac{\partial J}{\partial \mathbf{\mu}_{k}} = 2 \sum_{n=1}^N r_{nk} (\mathbf{x}_n – \mathbf{\mu}_k) = 0 \\
\Rightarrow \hspace{0.5cm} &\mathbf{\mu}_k = \frac{\sum_{n = 1}^{N} r_{nk} x_n}{\sum_{n = 1}^{N} r_{nk}}
\end{aligned}
$$

至此我們已經將 $r_{nk}$ 和 $\mathbf{\mu}_{k}$ 更新方式介紹完畢，剩下只要持續的依序更新 $r_{nk}$ 和 $\mathbf{\mu}_{k}$ 直到兩者的值不再改變，就完成分群了。

結論

縱使推導略為冗長，實際上 k-means 實做起來非常簡單，第一步是對於每個 $\mathbf{\mu}_1,…,\mathbf{\mu}_K$ 找出最接近的所有資料 $\mathbf{x}_n$，再利用這些資料算出新的平均值賦予對應的 $\mathbf{\mu}_k$。以下圖片為 k-means 演算法之示意圖，我們擁有身高、體重的資料點，但是我們並不清楚對應的生理性別，因此可以利用分群的方式試圖將資料點分群。

參考資料

BISHOP, Christopher M. Pattern recognition and machine learning. springer, 2006.

其他文章

機器學習系列文章總整理
EM Algorithm 詳盡介紹: 利用簡單例子輕鬆讀懂 EM 的原理及概念
Gaussian Mixture Model (GMM) －混合高斯模型的介紹以及完整數學式推導
[MobileNet 系列] MobileNetV1－為終端而生
[MobileNet 系列] MobileNetV2－小改動大進化，終端的唯一選擇