しまてく

学んだ技術を書きためるブログ

ITエンジニアのための機械学習理論入門 6

第6章 k平均法: 教師なしモデルの基礎

  • k平均法は教師なし学習モデル。
  • 与えられたトレーニングセットをクラスタリングする方法。

  • いままでの教師あり学習では、トレーニングセットは目的変数$t_n$を持っていた。

  • そうしたデータを分析し、未知のデータに対して推測をしてきた。

  • 一方教師なし学習では目的変数を持たない。

  • そのため、分類をするための何らかの基準を決める必要がある。
  • この基準を「二重歪み」と呼び、これをなるべく最小化するようにする。

k平均法によるクラスタリング

  • トレーニングセット $ {(x_n, y_n)}_{n=1}^N $ が与えられたとする。
  • 感覚的に、このデータは二つに分類できそうな気がする。
  • そこで、k平均法を用いて、これらのデータを二つのクラスターに分類する。
    • 分類する数は事前に決める必要がある。

実際の分類の手順

  1. トレーニングセットに含まれるデータは ${\bf x}_n = (x_n, y_n)^T$と表記する。
  2. 適当な代表点 ${\mu_k}_{k=1}^2$ を決める。
  3. 各点と代表点との距離 $|{\bf x}_n - \mu_k|$ を計算して、距離が短い方の代表点に属するものとする。
  4. ここで、どちらの代表点に所属するかを表す変数$r_{nk}$を定義しておく。

$$ r_{nk} = \left\{ \begin{array}{l} 1 \ \ \ \ {\bf x}_n がk番目の代表点に属する場合 \\ 0 \ \ \ \ それ以外の場合 \end{array} \right . \tag{6.1} $$

  1. 次に、(3)で分類したクラスターの「重心」を新たな代表点とする。
  2. 重心の公式を使って式を立てると以下のようになる。
    • $N$は$k$番目の代表点に属する点の個数。
    • 分子の$\sum$は$k$番目の代表点に属する点についてのみ加える。

$$ \mu_k = \dfrac{\sum{\bf x}_n}{N_k} (k = 1,2) \tag{6.2} $$

  1. (6)を(6.1)を用いてスマートに表現すると、

$$ \mu_k = \dfrac{\sum_{n=1}^Nr_{nk}{\bf x}_n}{\sum_{n=1}^Nr_{nk}} \tag{6.3} $$

  1. (5)から(7)をクラスターに所属する点に変化がなくなるまで繰り返す。
  2. 最終的に得られた ${\mu_k}_{k=1}^2$ がそれぞれのクラスターの代表点となる。

画像データへの応用

  • ある画像から代表色を抽出するという問題を解く。
  • 最も簡単なのは、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つの点で問題がある。
    1. 新たなデータの分類に時間がかかる。
      • データが与えられた場合、すべてのデータについて参照して計算しなおす必要がある。
    2. 分析のモデルが明確ではない。
      • 与えられたデータからたまたまそのように分類できた、というだけ。
      • 仮説と実証ではなく、単純に事実からの判断でしかないため将来に生かせない。