最も簡単なクラスタリング手法 K-means

機械学習のタスクの一つに、クラスタリングがあります。クラスタリングの目的は、データを正常異常の2種類に分類したり、3種類以上に分類して傾向を掴んだりと様々あります。
この記事では最も簡単な手法であるK-means 法を解説します。
管理人の趣味で、カーネルk-means法も紹介します。
参考文献は2冊です。

Bitly

Bitly

K-means 法
K-means 法の計算
カーネルK-means
Kの決め方
まとめ

K-means 法

データのまとまりの事をクラスタと呼びます。例えば、性別や家電の種類などです。
n次元のデータが$ \{ x_1 , \cdots , x_N \} $のN個あり、データ全体をK個のクラスタに分類したいとします。
K-meansでは、データがどのクラスタに属するかを判断する関数$ r_{nk} $を得るのが目的です。$n$がデータの番号で、$k $がクラスタの番号です。
データ$x_n $がクラスタj に属する時、$ r_{nk} $はクロネッカーのデルタ関数を用いて
$$\begin{eqnarray}
r_{nk}= \delta _{nk}
\end{eqnarray}$$
と書けます。
$r_{nk} $を求める為に、クラスタ k の中心$ \mu _k $を考えます。
$ \mu _k $と、データ$x_n $との距離が最も近い$k $ をデータ$x_n $が属するクラスタと判断します。¹$ \mu _k $と、$r_{nk} $を作るのがK-means の手法です。
言い換えると、以下の集合を各クラスタについて決定する手法です。
$$\begin{eqnarray}
N_k = \{ x_i | x_i はクラスタ k に属する \}
\end{eqnarray}$$

K-means 法の計算

具体的には、損失関数を定義して、それを最小化するような$ \mu _k , r_{nk} $を求めます。
損失関数は以下のように定義します。
$$\begin{eqnarray}
J= \sum_{k=1}^K \sum_{n=1}^N r_{nk}\| x_n – \mu _k \| ^2
\end{eqnarray}$$
Jを最小化するのは、クラスタ事にデータが最も集まっている場所$\mu _k $を求める事、そのような$ \mu _k $を得られるように$ r_{nk} $を決める事に対応します。²
一度に二つの量を最適化するのは難しいので、順々に最適化していくのが定石です。$ \mu _k $に関して最小化するには、$ \mu _k $の勾配が0となるようにすれば良いです。
$$\begin{eqnarray}
\nabla _{\mu _k } J&=& 2 \sum_{n=1}^N r_{nk} ( x_n – \mu _k ) \\
\mu _k &=& \frac{\sum_{n=1}^N r_{nk} x_n }{\sum_{n=1}^N r_{nk}}
\end{eqnarray}$$

$r_{nk} $も含めたJの最小化は以下の手順で行われます。

$ \mu _k $を適当に与える
各nに対して $ \| x_n -\mu _k \| ^2 $を計算して、最小となる$k=k_n $を求める。
2で求めたjから$ r_{nk} = \delta _{nk_n } $とする。
Jを$ \mu _k$について最小化する。
Jを記録し、1回目の計算なら2に戻る
Jが収束していれば終了。収束していなければ2に戻る。

5.で2.に戻っていますが、一回目の計算は$ \mu _k $が適当なベクトルなので複数回計算を繰り返す必要があります。また、$ \mu _k $の値によって$r_{nk} $が変化するので、$ \mu _k $が安定するまで計算を繰り返す必要があります。
Jの最小化の言葉を用いると、クラスタの中心が分かっているとして、クラスタの集合は以下のように言えます。
$$\begin{eqnarray}
N_k = \{ x_i | k = {\rm arg \ min_{j } } \|x_i – \mu _j \| ^2 \}
\end{eqnarray}$$
クラスタの中心$ \mu _k $ も最適化すると思うと、
$$\begin{eqnarray}
N_k = \{ x_i | \mu_k = {\rm arg \ min_{\mu _j } } \|x_i – \mu _j \| ^2 \}
\end{eqnarray}$$
と書いても同じことです。

カーネルK-means

K-means のカーネル化を導きます。カーネル化については、以下の記事を参照してください。

カーネル化

既存手法をカーネル法で扱う術について解説します。この記事の中ではカーネル化と呼びます。使うカーネルを決めるだけで、モデルの表現力を向上させることが出来ます。いくつかの例で実践してみます。

K-means をカーネル化するために、損失関数を少し書き直します。クラスタの中心は、クラスタの集合$N_k $が分かっている時には、
$$\begin{eqnarray}
\mu _k = \frac{\sum_{n=1}^N r_{nk} x_n }{|N_k|}
\end{eqnarray}$$
と書けることに注意しましょう。³
損失関数の一部を書き下すと、
$$\begin{eqnarray}
\| x_i -\mu _k \| ^2 &=& \|x_i – \frac{1}{|N_k | }\sum r_{nk}x_n \|^2 \\
&=& x_i \cdot x_i – \frac{2}{N_k } \sum_{n}r_{nk} x_n \cdot x_i + \frac{1}{|N_k | ^2} r_{nk} r_{mk} \sum_m \sum _n x_n \cdot x_n
\end{eqnarray}$$
と書けます。カーネル化するには、データの内積をカーネルに置き換えればよかったので、
カーネル$ k(\cdot , \cdot ) $を使って、損失関数は
$$\begin{eqnarray}
J_{ik} &=& k(x_i , x_i )- \frac{2}{| N_k |} \sum_{n} r_{nk} k( x_i , x_n ) + \frac{1}{|N_k | ^2} r_{nk} r_{mk} \sum_m \sum _n k(x_m ,x_n ) \\
J &=& \sum_{k=1}^{K} \sum_{i=1} ^{N} J_{ik}
\end{eqnarray}$$
となります。
カーネル化すると、損失関数にクラスタの中心$ \mu _k $は出てきません。計算したい場合は、クラスタの集合$N_k $を決めて、
$$\begin{eqnarray}
\mu _k &=& \frac{\sum_{n=1}^N r_{nk} x_n }{|N_k|} \\
&=& \frac{\sum_{x_i \in N_k } x_i }{|N_k|}
\end{eqnarray}$$
とします。クラスタの集合$N_k $の要素は、$ \mu _k $を介さず、各データ$x_i $に対して
$$\begin{eqnarray}
{\rm arg \ min_{k } } J_{ik}
\end{eqnarray}$$
を計算して求めます。
実際の計算の手順は以下のようになります。