K-means法

導入

$D$ 次元のデータ集合 $\{{\bf x}_1,\ldots,{\bf x}_N\}$ を $K$ 個のクラスターに分割することを考えます。

プロトタイプと呼ばれる $K$ 個の $D$ 次元ベクトル ${\boldsymbol\mu}_k$ を導入します。
各データに対し、対応する2値指示変数 $r_{nk}\in\{0,1\}$ を定めます。

$r_{nk},{\boldsymbol\mu}_k$ のイメージは下図です。( $K=3$ の場合)

f:id:olj611:20210502005139p:plain:w600

目的関数

目的関数 $J$ を以下のように定めます。

$\begin{eqnarray} J=\sum_{n=1}^N\sum_{k=1}^Kr_{nk}||{\bf x}_n-{\boldsymbol\mu}_k||^2\tag{1} \end{eqnarray}$

目的関数 $J$ は各データ点からそれらが割り当てられているベクトル ${\boldsymbol\mu}_k$ までの
二乗距離の総和を表しています。

この目的関数を以下の方法で最小化します。
1: ${\boldsymbol\mu}_k$ の初期値を選ぶ。(適当に決める)
2: ${\boldsymbol\mu}_k$ を固定しつつ $r_{nk}$ について $J$ を最小化する。
3: $r_{nk}$ を固定しつつ ${\boldsymbol\mu}_k$ について $J$ を最小化する。
4: $J$ が収束していれば、終了する。そうでなければ2へ戻る。

2: ${\boldsymbol\mu}_k$ を固定しつつ $r_{nk}$ について $J$ を最小化する

$n$ 番目のデータ点を中心にそれに最も近いクラスター中心に割り当てます。

$\newcommand{\argmin}{\mathop{\rm arg~min}\limits}\begin{eqnarray} r_{nk}= \left\{ \begin{array}{l} 1\hspace{20px}k=\argmin_j||{\bf x}_n-{\boldsymbol\mu}_j||^2\\ 0\hspace{20px}それ以外 \end{array}\tag{2} \right. \end{eqnarray}$

3: $r_{nk}$ を固定しつつ ${\boldsymbol\mu}_k$ について $J$ を最小化する

$J$ を ${\boldsymbol\mu}_k$ で微分して、 $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial{\boldsymbol\mu}_k}J={\bf 0}\\ &&\Leftrightarrow\frac{\partial}{\partial{\boldsymbol\mu}_k}\sum_{n=1}^N\sum_{j=1}^Kr_{nj}||{\bf x}_n-{\boldsymbol\mu}_j||^2={\bf 0}\\ &&\Leftrightarrow\frac{\partial}{\partial{\boldsymbol\mu}_k}\sum_{n=1}^N\sum_{j=1}^Kr_{nj}({\bf x}_n^\top{\bf x}_n-2{\boldsymbol\mu}_j^\top{\bf x}_n+{\boldsymbol\mu}_j^\top{\boldsymbol\mu}_j)={\bf 0}\\ &&\Leftrightarrow\sum_{n=1}^N\sum_{j=1}^Kr_{nj}\left(-2\frac{\partial}{\partial{\boldsymbol\mu}_k}^\top{\boldsymbol\mu}_j{\bf x}_n+\frac{\partial}{\partial{\boldsymbol\mu}_k}\right)={\bf 0}\\ &&\Leftrightarrow\sum_{n=1}^Nr_{nk}(-2{\bf x}_n+2{\boldsymbol\mu}_k)={\bf 0}\\ &&\Leftrightarrow{\boldsymbol\mu}_k\sum_{n=1}^Nr_{nk}=\sum_{n=1}^Nr_{nk}{\bf x}_n\\ &&\Leftrightarrow{\boldsymbol\mu}_k=\frac{\sum_{n=1}^Nr_{nk}{\bf x}_n}{\sum_{n=1}^Nr_{nk}}\tag{3} \end{eqnarray}$