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
コメント
コメントを投稿