Introduction
今日はK-meansアルゴリズムの理論について書きます。
K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。
K-meansの実装の記事は
カーネルK-meansの実装
を御覧ください。
この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。
概要
K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。
ベクトル$r_n:1 \times K$ を
$$r_n := (0,0,..,1,..,0)$$
このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。
こののような表現の仕方を1 of K符号化法と呼びます。
プロトタイプ
K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。
歪み尺度
プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。
この時、k-meansの目的関数は次のようになります。
$$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$
ここで、 $r_{nk}$ は$r_n$のk番目の要素です。
この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、
$$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$
ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。
よって、
$$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ... + ||x_N - \mu_{x_N}||$$
では、この目的関数を最小化することを考えます。
初めに$J$を$r_n$について最小化することをかんがえます。
$||x_n-\mu_k||^2$ は$x_n$と$x_n$が属しているクラスのプロトタイプとの距離なので、,
$r_n$ は次のように決まります。
$$k = \arg \min_{j} || x_n - \mu_{j} || \implies r_{nk} = 1$$
$$else \implies r_{n_k} = 0$$
次に、$r_{n_k}$を固定したときに、$J$を$\mu_k$について最小化します。
偏微分は
$$2\sum_{n=1} ^{N} r_{n_k} (x_n-\mu_k) = 0$$
よって
$$2\sum_{n=1} ^{N} \{r_{n_k} x_n\} - \mu_k \sum_{n=1}^{N}r_{n_k} = 0 $$
$$\mu_k = \frac{\sum_{n} r_{n_k} x_n}{\sum_n r_{n_k}}$$
この値はkクラスの平均ベクトルとなっていることがわかります。
その結果、プロトタイプは平均ベクトルであることがわかります。
$r_n$を$\mu_k$について、最適化するわけですが、どちらにももう片方の変数が使われているため、どちらかを固定して交互に最適化する必要があります。
$r_n$を求める$\rightarrow$ $r_n$を固定して$\mu_k$を求める$\rightarrow$ $\mu_k$を固定して$r_n$を求める$\rightarrow$ .......
収束条件は平均ベクトルの変化量を用いることが多いです。平均ベクトルがほとんど動かなくなったら修了します。
もし、EMアルゴリズムをご存知であるならば、$J$を$r_n$について最小化するのはEステップにあたり、$J$を$\mu$について最小化することはMステップにあたります。
Reference
今日はK-meansアルゴリズムの理論について書きます。
K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。
K-meansの実装の記事は
カーネルK-meansの実装
を御覧ください。
この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。
概要
- 1 of K 符号化法
- プロトタイプ
- 歪み尺度
- 最適化
K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。
ベクトル$r_n:1 \times K$ を
$$r_n := (0,0,..,1,..,0)$$
このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。
こののような表現の仕方を1 of K符号化法と呼びます。
プロトタイプ
K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。
歪み尺度
プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。
この時、k-meansの目的関数は次のようになります。
$$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$
ここで、 $r_{nk}$ は$r_n$のk番目の要素です。
この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、
$$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$
ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。
よって、
$$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ... + ||x_N - \mu_{x_N}||$$
では、この目的関数を最小化することを考えます。
初めに$J$を$r_n$について最小化することをかんがえます。
$||x_n-\mu_k||^2$ は$x_n$と$x_n$が属しているクラスのプロトタイプとの距離なので、,
$r_n$ は次のように決まります。
$$k = \arg \min_{j} || x_n - \mu_{j} || \implies r_{nk} = 1$$
$$else \implies r_{n_k} = 0$$
次に、$r_{n_k}$を固定したときに、$J$を$\mu_k$について最小化します。
偏微分は
$$2\sum_{n=1} ^{N} r_{n_k} (x_n-\mu_k) = 0$$
よって
$$2\sum_{n=1} ^{N} \{r_{n_k} x_n\} - \mu_k \sum_{n=1}^{N}r_{n_k} = 0 $$
$$\mu_k = \frac{\sum_{n} r_{n_k} x_n}{\sum_n r_{n_k}}$$
この値はkクラスの平均ベクトルとなっていることがわかります。
その結果、プロトタイプは平均ベクトルであることがわかります。
$r_n$を求める$\rightarrow$ $r_n$を固定して$\mu_k$を求める$\rightarrow$ $\mu_k$を固定して$r_n$を求める$\rightarrow$ .......
収束条件は平均ベクトルの変化量を用いることが多いです。平均ベクトルがほとんど動かなくなったら修了します。
もし、EMアルゴリズムをご存知であるならば、$J$を$r_n$について最小化するのはEステップにあたり、$J$を$\mu$について最小化することはMステップにあたります。
Reference
コメント
コメントを投稿