K-means法について勉強したのでまとめました。

k-means法の位置づけ

教師無し学習の内の一つにクラスタリングがある。

クラスタリングとは、あるデータ集合をデータ間の類似度を基準に複数のクラスタに分類すること。

クラスタリングは以下の二つに大別できる。

階層的クラスタリング
非階層的クラスタリング

このうち、K-means法は非階層的クラスタリングに属する。

K-means法の目的

K-means法の目的は、$D$次元のベクトル$N$個で構成されるデータ集合$\boldsymbol{x_1}, \boldsymbol{x_2}\dots,\boldsymbol{x_N}$を$K$個のクラスタに分類すること。

K-means法の流れ

前準備

各クラスタの代表ベクトルを$\boldsymbol{\mu_1},\boldsymbol{\mu_2}, \dots, \boldsymbol{\mu_K}$とする。
$k$番目の代表ベクトルが支配するクラスタを$M(\boldsymbol{\mu_k})$とする。

$i$番目のデータが、$k$番目のクラスタに属するか否かを表す変数を$q_{ik}$を以下に定義する。

q_{ik} = \left\{
\begin{array}{ll}
1 & \boldsymbol{x_i} \in M(\boldsymbol{\mu_k})\\
0 & otherwize
\end{array}
\right.

$q_{ik}$を定義することで目的関数の記述が楽になる。

目的関数

K-means法の目的関数を以下により定義する。

J(q_{ik}, \boldsymbol{\mu_k})= \sum_{i=1}^{N}\sum_{k=1}^{K}q_{ik}||\boldsymbol{x_i}-\boldsymbol{\mu_k}||^2

これは、$1 \leq i\leq N$とする時、各データ$x_i$と、$x_i$が属しているクラスタの代表ベクトル$\mu_k$との距離の二乗を計算し、データの数$N$だけサメンションしている。
$q_{ik}$を使うことで、データ自身が属していないクラスタの代表べクトルとの距離は0になるように設計されている。

この目的関数$J$を最小化していく。すなわち、各データと自身が分類される各クラスタの代表ベクトルとの距離の二乗和を小さくしていきたいということ。

目的関数の最小化

$J(q_{ik}, \boldsymbol{\mu_k})$は$q_{ik}, \boldsymbol{\mu_k}$を持つ関数である。
同時に最小化するのは難解なので、各変数について他方を固定して逐次的に最小化する。

最小化のアルゴリズムは以下のようになる。

アルゴリズム

初期化：各データをランダムにクラスタに割り当てる。割り当てた各データの平均を代表ベクトル$\boldsymbol{\mu_k}(k=1, 2, \dots, K)$とする。

$q_{ik}$についての最小化：求めた$\boldsymbol{\mu_k}$を固定し、$q_{ik}$について$J$を最小化する。
$\boldsymbol{\mu_{ik}}$についての最小化：2.で求めた$q_{ik}$を固定し、$\boldsymbol{\mu_k}$について$J$を最小化する。
上記2. 3.を収束するまで繰り返す。

最小化アルゴリズムの説明

2.について

以下のように、各データとクラスタ$j$の代表ベクトルとの距離を計算する。
各データ$i$に対して、一番距離が小さくなるクラスタを選んで、その時の$q_{ik}$を１とする。

q_{ik} = \left\{
\begin{array}{ll}
1 & k = argmin_j ||\boldsymbol{x_i}-\boldsymbol{\mu_j}||^2\\
0 & otherwize
\end{array}
\right.

3.について

$J$は$\mu_k$についての二次関数であるので、目的関数$J$を偏微分して勾配を計算する。

\frac{\partial J(q_{ik}, \boldsymbol{\mu_k})}{\partial \boldsymbol{\mu_k}}=2\sum_{i=1}^Nq{ik}(x_i-\mu_k)=0\\
⇒\mu_k=\frac{\sum_{i=1}^Nq_{ik}\boldsymbol{x_i}}{\sum_{i=1}^Nq_{ik}}

求めた$\mu_k$は、クラスタ$k$に属するデータの平均になっている。

以下サイトの図解がアルゴリズムを理解するのに役立った。
K-means 法を D3.js でビジュアライズしてみた

K-means法の注意点

最小化アルゴリズムによる収束先は最初に設定した初期値に依存するので、最適な解になるとは限らない。
最適な値に近づけるには、初期値に設定する値を変更し、何度かK-means法を行う。

参考文献

森北出版「はじめてのパターン認識第10章」
K-means 法を D3.js でビジュアライズしてみた