ITエンジニアのための機械学習理論入門 6
第6章 k平均法: 教師なしモデルの基礎
- k平均法は教師なし学習モデル。
与えられたトレーニングセットをクラスタリングする方法。
いままでの教師あり学習では、トレーニングセットは目的変数$t_n$を持っていた。
そうしたデータを分析し、未知のデータに対して推測をしてきた。
一方教師なし学習では目的変数を持たない。
- そのため、分類をするための何らかの基準を決める必要がある。
- この基準を「二重歪み」と呼び、これをなるべく最小化するようにする。
k平均法によるクラスタリング
- トレーニングセット $ {(x_n, y_n)}_{n=1}^N $ が与えられたとする。
- 感覚的に、このデータは二つに分類できそうな気がする。
- そこで、k平均法を用いて、これらのデータを二つのクラスターに分類する。
- 分類する数は事前に決める必要がある。
実際の分類の手順
- トレーニングセットに含まれるデータは ${\bf x}_n = (x_n, y_n)^T$と表記する。
- 適当な代表点 ${\mu_k}_{k=1}^2$ を決める。
- 各点と代表点との距離 $|{\bf x}_n - \mu_k|$ を計算して、距離が短い方の代表点に属するものとする。
- ここで、どちらの代表点に所属するかを表す変数$r_{nk}$を定義しておく。
$$ r_{nk} = \left\{ \begin{array}{l} 1 \ \ \ \ {\bf x}_n がk番目の代表点に属する場合 \\ 0 \ \ \ \ それ以外の場合 \end{array} \right . \tag{6.1} $$
- 次に、(3)で分類したクラスターの「重心」を新たな代表点とする。
- 重心の公式を使って式を立てると以下のようになる。
- $N$は$k$番目の代表点に属する点の個数。
- 分子の$\sum$は$k$番目の代表点に属する点についてのみ加える。
$$ \mu_k = \dfrac{\sum{\bf x}_n}{N_k} (k = 1,2) \tag{6.2} $$
- (6)を(6.1)を用いてスマートに表現すると、
$$ \mu_k = \dfrac{\sum_{n=1}^Nr_{nk}{\bf x}_n}{\sum_{n=1}^Nr_{nk}} \tag{6.3} $$
画像データへの応用
- ある画像から代表色を抽出するという問題を解く。
- 最も簡単なのは、RGBの各値を3次元空間の点とみなす方法。
- 画像のすべてのピクセルを3次元空間にマッピングすると色の分布を可視化できる。
- すべてのデータに対してクラスタリングをすることで代表色を決められる。
- 各ピクセルを代表色で置き換えることで、画像の減色処理が実現できる。
k平均法の数学的根拠
- k平均法では「二乗歪み」というグループ分けの基準を用いている。
$$ J = \sum_{n=1}^N\sum_{k=1}^Kr_{nk}|{\bf x}_n - \mu_k|^2 \tag{6.4} $$
- $r_{nk}$の定義(6.1)を考えると、これは『「自分の属するクラスターの代表点からの距離の2乗」の合計』になっている。
- つまり、$J$を小さくするということは、「代表点のなるべく近くにデータが集まるように分類する」ということ。
- 以下は、k平均法の手続きによって、この「二乗歪み」が最終的に極小値に達することを証明する。
証明
- トレーニングセットは、任意の特定次元ベクトルの集合 ${{\bf x}_n}_{n=1}^N$とする。
- K個のクラスターに分類するとして、代表点を${\mu_k}_{k=1}^K$とする。
各データが属するクラスタ-を以下のように表す。 $$ r_{nk} = \left\{ \begin{array}{l} 1 \ \ \ {\bf x}_n がk番目の代表点に属する場合 \\ 0 \ \ \ それ以外の場合 \end{array} \right. \tag{6.5} $$
現在の分類における「二乗歪み」は以下の式で表せる。
$$ J = \sum_{n=1}^N\sum_{k=1}^Kr_{nk}|{\bf x}_n - \mu_k|^2 \tag{6.6} $$
以下では、k平均法の手続きに従って $r_{nk}$ と $\mu_k$ を修正していくと$J$の値は減少し、極小値に達することを示す。
- まず、各データが属するクラスターを選択しなおす。
- この時、各データ${\bf x}_n$について、代表点からの距離$|{\bf x}_n - \mu_k|$が最も小さいクラスターを選択する。
- Jの意味を考えれば、この操作でJの値が大きくなることはない。
- この操作は、$r_{nk}$を以下の条件で再定義していることになる。
$$ r_{nk} = \left\{ \begin{array}{l} 1 \ \ \ k = \mathop{\rm arg\,min}\limits_{k'}|{\bf x}_n - \mu_{k'}| \\ 0 \ \ \ それ以外の場合 \end{array} \right. \tag{6.7} $$
- ($\mathop{\rm arg\,min}\limits_{x}f_x$は、$f_x$を最小にする$x$の値)
- 次に、現在の分類状態において、各クラスターの代表点を取り直す。
- (6.6)を最小にするという条件で、 $\mu_k$を選択する。
- (6.6)を$\mu_k$について見ると、下に凸な二次関数となっている。
- これは偏微分係数が0になるという条件で最小化するということ。
- $J$を成分表記すると以下のようになる。($[x_n]_i$という記号はベクトル${\bf x}_n$の$i$成分を表す)
$$ J = \sum_{n=1}^N \sum_{k=1}^K \left\{r_{nk}\sum_i([{\bf x}_n]i - [\mu_k]i)^2 \right\} \tag{6.8} $$
- これを特定の成分$[\mu_k]_i$で偏微分する。
- $k$と$i$が特定の成分なので、$k = k'$, $i = i'$として、$J$を以下のように変形する。
$$ \begin{eqnarray} J' &=& \sum_{n=1}^Nr_{nk'}([{\bf x}_n]i' - [\mu_{k'}]i')^2 \nonumber \\ &=& \sum_{n=1}^Nr_{nk'}([{\bf x}_n]i'^2 -2[{\bf x}_n]i' [\mu_{k'}]i' + [\mu_{k'}]i'^2) \nonumber \end{eqnarray} $$
- これを$[\mu_{k'}]_{i'}$で偏微分する。
$$ \dfrac{\partial J}{\partial [\mu_{k'}]_{i'}} = -2 \sum_{n=1}^Nr_{nk'}([{\bf x}_n]_{i'} - [\mu_{k'}]_{i'}) $$
- 元々は特定の成分$[\mu_k]_i$なので、書き直すと以下になる。
$$ \dfrac{\partial J}{\partial [\mu_k]_i} = -2 \sum_{n=1}^Nr_{nk}([{\bf x}_n]_i - [\mu_k]_i) \tag{6.9} $$
- これが0になるという条件から、$[\mu_k]_i$は以下のように決まる。
$$ \begin{eqnarray} -2 \sum_{n=1}^Nr_{nk}([{\bf x}_n]_i - [\mu_k]_i) &=& 0 \nonumber \\ -2 \sum_{n=1}^Nr_{nk}[{\bf x}_n]_i + 2 \sum_{n=1}^Nr_{nk}[\mu_k]_i &=& 0 \nonumber \\ \sum_{n=1}^Nr_{nk}[\mu_k]_i &=& \sum_{n=1}^Nr_{nk}[{\bf x}_n]_i \nonumber \\ [\mu_k]_i &=& \dfrac{\sum_{n=1}^Nr_{nk}[{\bf x}_n]_i}{\sum_{n=1}^Nr_{nk}} \tag{6.10} \end{eqnarray} $$
- 成分表記からベクトル表記に戻すと、以下の結果が得られる。
$$ \begin{eqnarray} \mu_k &=& \dfrac{\sum_{n=1}^Nr_{nk}{\bf x}_n}{\sum_{n=1}^Nr_{nk}} \tag{6.11} \end{eqnarray} $$
- これは各クラスターの重心を新たな代表点に取る(6.3)と同じものになっている。
- 従って(6.3)の手続きによっても$J$が大きくなることはない。
- 以上により、k平均法の操作を繰り返すと、Jの値は必ず小さくなるか、それ以上変化しない極小値に達する。
ただし、二乗歪み$J$は有限回の操作で極小値に達するが、完全に値が変化しなくなるまでには計算に時間がかかるため、$J$の減少分が0.1%未満になるなどで計算を打ち切る。
- この例では3次元空間の点$x$だったので、通常のユークリッド距離$|{\bf x}_n - \mu_k|$で計算をした。
- ただし、これ以外の距離を用いてもk平均法の手続きを実施することはできる。
- 例えば、「文書」のカテゴリー分けで、「文書間の距離」を定義すれば利用可能。
- 何らかの方法で類似度を計算し、類似度が高いほど距離が近くなるようにする。
- 単語の出現頻度などで判断する。
怠惰学習モデルとしてk近傍法
- k近傍法は教師あり学習に分類される。
- しかし一般的な目的変数とはことなり、近傍データによって自分の目的変数を推測する。
- 近い方からK個分のデータを見て推測するとして、
- K=1の場合はトレーニングセットのデータにオーバーフィッティングする。
- K=3などの場合はよりなめらかに分類できる。
- しかし、k近傍法は2つの点で問題がある。
- 新たなデータの分類に時間がかかる。
- データが与えられた場合、すべてのデータについて参照して計算しなおす必要がある。
- 分析のモデルが明確ではない。
- 与えられたデータからたまたまそのように分類できた、というだけ。
- 仮説と実証ではなく、単純に事実からの判断でしかないため将来に生かせない。
- 新たなデータの分類に時間がかかる。