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

カーネルK-means 理論編

Introduction

今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常のK-means 理論編の記事を見ていただけるとよいのではないかと思います。

カーネルK-meansの実装編も併せてご覧ください。

概要

  • K-meansの弱点
  • カーネルトリック
  • カーネルK-means
  • アルゴリズム


K-meansの弱点
例えば、次のようなデータを用意します。

このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。

このようなデータではK-meansはうまくいきません。
K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。


カーネルK-meansはK-meansの弱点を補います。

カーネルトリック

初めに、カーネルトリックを説明します。
線形分離できないようなデータ$X$を例えば次のように線形分離できるように$\phi(x)$に送る写像$\phi$を考えます。


カーネルは次のように定義されます。
$$K(x,y) = \phi(x)^T \phi(y)$$

$\phi$を具体的に計算することは難しいですが、$K(x,y)$を計算することなら簡単です。
この手法をカーネルトリックと呼ばれます。

カーネルK means

K-meansの目的関数を復習しておきます。

$$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$

ここで、 プロトタイプは$\mu_i ~\forall k \in K$とします。
$r_n$は1 of K符号化法であり、$r_{nk}$は$r_n$のk番目の要素です。
この時、
$$\mu_k = \frac{\sum_{n} r_{n_k} x_n}{\sum_n r_{n_k}}$$
そして、
$$k = \arg \min_{j} || x_n - \mu_{j} || \implies r_{nk} = 1$$

$$else \implies r_{n_k} = 0$$


次のように目的関数を書き換えます。

$$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||\phi(x_n)-\mu_k||^2$$

その時、
$$\mu_k = \frac{\sum_{n} r_{n_k} \phi(x_n)}{\sum_n r_{n_k}}$$


それゆえ、$x_n$とプロトタイプ$\mu_k$の距離は
$$||\phi(x_n) - \frac{\sum_{m}^{N} r_{m_k} \phi(x_m)} {\sum_{m}^{N} r_{m_k}} ||^2$$
$$= \phi(x_n)^T \phi(x_n) - \frac{2 \sum_{m}^{N} r_{n_k} \phi(x_n)^T \phi(x_m)}{\sum_{m}^{N} r_{n_k}} + \frac{\sum_{m,l}^{N} r_{n_k} r_{n_k} \phi(x_m)^T \phi(x_l)}{ \{ \sum_{m}^{N} r_{n_k} \}^2 }$$

カーネルK-meansでは$\phi(x_n)^T \phi(x_m)$を$K(x_n,x_m)$として計算します。

Algorithm

  1. プロトタイプの初期値、K:クラスの数
  2. for iteration in iteration times.
  3. for $n \in N$ do 
  4. for $k \in K$ do
  5. $x_n$とクラスkのプロトタイプの距離を計算します。
  6. end for k
  7. $x_n$とクラスkのプロトタイプの距離の中で最小にさせるようなクラス$k_n$を選びます。
  8. $x_n$のクラスを$k_n$とします。
  9. end for n
  10. もし、プロトタイプベクトルにほとんど変化がない場合はカーネルK-meansを終了します。


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-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...
コメントを投稿
続きを読む

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　 実装例 以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。 予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...
コメントを投稿
続きを読む