スキップしてメイン コンテンツに移動

K-means 理論編

Introduction


今日はK-meansアルゴリズムの理論について書きます。
K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。

K-meansの実装の記事は
カーネルK-meansの実装
を御覧ください。
この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。

概要

  • 1 of K 符号化法
  • プロトタイプ
  • 歪み尺度
  • 最適化
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$を$\mu_k$について、最適化するわけですが、どちらにももう片方の変数が使われているため、どちらかを固定して交互に最適化する必要があります。

$r_n$を求める$\rightarrow$ $r_n$を固定して$\mu_k$を求める$\rightarrow$ $\mu_k$を固定して$r_n$を求める$\rightarrow$ .......

収束条件は平均ベクトルの変化量を用いることが多いです。平均ベクトルがほとんど動かなくなったら修了します。


もし、EMアルゴリズムをご存知であるならば、$J$を$r_n$について最小化するのはEステップにあたり、$J$を$\mu$について最小化することはMステップにあたります。

Reference

Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネルk-meansの実装

Introduction   English ver 今日はカーネルk-meansの実装をしました。k-menasアルゴリズムはクラスタリングのためのアルゴリズムです。僕がカーネルk-meansを実装しようと思ったのには一つ理由があります。それは僕の友人がk-meansのプレゼンを、僕がカーネルのプレゼンをしていた時に、k-meansにカーネルを適応できないかと思ったからです。そこで、カーネルk-meansについての論文を探しました。 ここのpdf を主に参考にさせていただきました。うまくカーネルk-meansを実装できたと思います。ここでは、普通のk-meansとカーネルを用いた,kernel k-meansについての実装の結果を紹介します。 また、この記事では実装結果のみ書きますが、理論のほうも別の記事で書くつもりです。書き終えたらリンクをこの記事にも貼っておきます。 #  理論編書きました。K-means 理論編 概要 dataset   ちょっとだけ理論の説明  k-means    kernel k-means   Dataset   English ver 今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。 一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。 二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。   this page にデータセットを作ったコードを載せています。 ちょっとだけ理論の説明 k-meansとは、k-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...
コメントを投稿
続きを読む

Bayes' theorem

Introduction sorry, this page is Japanese only.   今回はベイズの定理について書こうと思います。 ベイズの定理とは、イギリスのトーマス・ベイズによって発見された、条件付き確率に関する定理です。現在のベイズ推定で用いられる重要な定理です。どのような定理かを解説していこうと思います。 ベイズの定理 ベイズの定理とは 確率P(B|A):事象Aが起こった後での事象Bの確率（事後確率） 確率P(B):事象Aが起こる前の事象Bの確率（事前確率） とするとき以下が成り立つことを示しています。 $$P(B|A) = \frac{P(A|B) P(B)}{P(A)}$$ 例 例えば、次のように事象A、事象Bwo定義します。 事象A:あるYoutuberが動画を投稿したとき、再生回数が100万回を超える 事象B:あるYoutuberがお金を50万円以上使う動画を投稿する この時確率P(A|B)、つまり50万円以上を使った動画が再生回数100万回を超える確率は、youtube内の50万円以上使っている動画を根こそぎ集め、その再生回数を得ることによって推定できそうです。では確率P(A|B)がわかった時、確率P(B|A)もわかる。これがベイズの定理の強みです。（当然確率P(A)とP(B)がわかっている必要はあります。） 確率P(B|A)とはあるYoutuberの動画が再生回数100万回を超えたとき、その同がで50万円以上使っている確率となります。これがわかれば、100万回動画が再生される原因は本当に50万円以上お金を使うことなのかがわかります。 確率P(A|B)が低い時を考えてみましょう。 つまり、50万円以上使った動画は再生回数100万回を超える確率は高い。しかし、100万回再生回数を突破したとき、その動画が50万円以上使っている可能性は低い。この状況はベイズの定理の式を考えいると理解しやすいです。 ベイズの定理の式を見てみると、P(B|A)は低く、P(A|B)が高いということは、確率P(A)が著しく高い。もしくは、P(B)が著しく低い。この二つがあげられます。 つまり、あるYouruberが100万回再生を突破する確率がかなり、高い。もしくは、あるYoutuber...
コメントを投稿
続きを読む