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-小改動大進化,終端的唯一選擇

Show 2 Comments

2 Comments

Comments are closed