CATEGORY

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネル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$ としま...

変分法の可視化

Introduction English ver 今日は、変分法の可視化を実装しました。変分法は、汎関数を最小化させるために使われます。汎関数とは、関数の関数のようなものです。変分法については、 [1] , [2] , [3] , [5] , [6] などを参考にしてください。概要汎関数実装可視化汎関数今回は、次のような汎関数を使います。

$F(x) = \sqrt{1+(\frac{du}{dx}(x))^2}$

$l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx$ l(u)はu(x)という曲線の長さです。.

$u(0)=a$ and

$u(1)=b$ という制約のもと、

$l(u)$ を最小化したいといます。最適な

$l(u)$ は

$u(x) = (b-a)x+a$ となります。 (0,a) から (1,b)への直線になっているのがわかります。これは、

$l(u)$ は

$u$ の曲線の長さなので、これを最小化するためには直線が一番であることが直観的にわかります。変分法での導出は、 [5] を参考にしてください。実装変分法における最適な曲線とそうでない曲線の違いを可視化する実装をしました。

$u_A$ を

$u_A = (b-a)x+a + A sin(8t)$ とします。

$A sin(8t)$ は

$u$ から話す役割を持ちます。.

$A \in [0,0.5]$ であり、もし

$A=0$ であれば、

$u_A=u$ です。 github でcodeを公開しています。可視化上側の画像は

$u_A(x)$ を表しています。下側の画像は

$l(u_A)$ の値を表しています。

$u_A(x)$ が

$u$ に近づくほど、

$l(u_A)$ が小さくなることがわかります。 Reference [1] http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-4.pdf [2] http://hooktail.sub.jp/mathInPhys/brach...

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...

journey of Froakie (ケロマツの旅路)

このブログを検索

CATEGORY

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

変分法の可視化

ダイクストラ法