機械学習のタスクの一つに、クラスタリングがあります。クラスタリングの目的は、データを正常異常の2種類に分類したり、3種類以上に分類して傾向を掴んだりと様々あります。
この記事では最も簡単な手法であるK-means 法を解説します。
管理人の趣味で、カーネルk-means法も紹介します。
参考文献は2冊です。
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 \)が属するクラスタと判断します。1\( \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} \)を決める事に対応します。2
一度に二つの量を最適化するのは難しいので、順々に最適化していくのが定石です。\( \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}$$
と書けることに注意しましょう。3
損失関数の一部を書き下すと、
$$\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}$$
を計算して求めます。
実際の計算の手順は以下のようになります。
- 使うカーネルを決める。
- データを適当にクラスタリングして\(N_k \)を決める。
- \(J_{ki}を計算し、\(( N_k \)を更新する
- \(N_k \)の要素が安定するまで3を繰り返す
お試しで使う場合は、RBFカーネルを使い、真面目に行いたい時は、色々なカーネルを足し合わせて使います。
Kの決め方
そもそも、クラスタの数Kをどうやって決めるかについても少し書いておきます。
一番簡単な方法は主成分分析をして、固有値を大きい順に並べた時、総和の値の8割を初めて超える数にする、という方法です。
詳しくは以下の記事を読んでみてください。
まとめ
- k-means 法を紹介した
- 具体的な計算の仕方を紹介した
- カーネルk-means の紹介した
- クラスタの数の決め方を紹介した