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

カーネル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:

コメント

コメントを投稿

このブログの人気の投稿

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

Visualization of Variational method

Introduction Today, I will implement visualization of Variational method. Variational method is used when we want to minimize functional. functional is function of function. Please look at  [1] , [2] , [3] , [5]  and  [6] . Overview formula  Implementation Visualization Formula I used following formula. $$F(x) = \sqrt{1+(\frac{du}{dx}(x))^2}$$ $$l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx$$ l(u) is the length of the u(x).  I want to minimize l(u) subject to $u(0)=a$ and $u(1)=b$. u minimizing I(u) is  $$u(x) = (b-a)x+a$$ This u is line from (0,a) to (1,b). Because l(u) is the length of the u(x), We found out that u minimizing l(u) is line. Please look  [5]  to calculate of variational method. Implementation I implement visualization of variational method to check difference of optimize curve and other curve.  Let $u_A$ is  $$u_A = (b-a)x+a + A sin(8t)$$ $A sin(8t)$ increase the di...
コメントを投稿
続きを読む