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

カーネルk-meansの実装

Introduction  

今日はカーネル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  

今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。

一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。

二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。

 this pageにデータセットを作ったコードを載せています。

ちょっとだけ理論の説明
k-meansとは、k-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かなくなるまで続けます。

k-means  

初めに普通のk-meansを実装しました。テスト用として、一つ目のデータセットを使いました。
結果はうまくいっていると思います。


centroidとは重心ベクトルのことで、各クラスの平均ベクトルになります。

しかしながら、k-meansアルゴリズムには様々な弱点があります。その一つは以下の画像を見てもらえればすぐにわかると思います。



この画像は、二つ目のデータセットにk-menasアルゴリズムを適応した結果です。
普通のk-meansではデータ空間で平均ベクトルとデータ点とのユークリッド距離を求めるため、このようにうまくいきません。

Kernel k-means

先ほどの例により、k-meansアルゴリズムには、うまくいかない点がありました。しかし、これをカーネルトリックを用いることでうまく解決できます
その結果がこちらです。

このクラスタリングは完璧ですね。

CODE
こちらにkernel k-means含め、すべてのコードを載せています。

git_Kmeans_def.pyではk-meansに必要な様々な関数を書いています。
git_Kemans_main.pyではk-meansを実行するためのコードを書いています。いわゆるメインファイルです。当然 if __name__ == '__main__':が入っています。

git_kernel_Kmeans_def.pyではkernel k-meansに必要な様々な関数を書いています。
git_kernel_Kemans_main.pyではkernel k-meansを実行するためのコードを書いています。いわゆるメインファイルです。当然 if __name__ == '__main__':が入っています。

Reference  

http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf
https://sites.google.com/site/dataclusteringalgorithms/kernel-k-means-clustering-algorithm
Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネル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$としま...
コメントを投稿
続きを読む

Kullback-Leibler divergence

Introduction sorry, this page is Japanese only.   今日がダイバージェンスについて書いていきます。 ちなみにエントロピーの知識を使うのでエントロピーの記事も見てあげてください。 エントロピーの記事はこちら Kullback-Leibler Divergence 二つの確率分布の平均エントロピーの差を表す値をKLダイバージェンスといいます。 式では次のように定義されます。 $$KL(P||Q) = \int_{-\infty}^{\infty} P(X) log \frac{P(X)}{Q(X)}$$ 離散の場合は $$KL(P||Q) = \sum_{i} P(X_i) log \frac{P(X_i)}{Q(X)}$$ なぜ二つの分布間の距離をこのように定義できるのでしょうか。 式の解釈 真の分布P(X)が存在するとします。しかし、有限のデータから真の分布P(X)を求めるのは難しいです。そこで、有限のデータから推定して得られた確率分布をQ(X）とします。では真の分布P(X）と推定した分布Q(X)はどれだけ違っているのでしょうか。 ここで登場するのがエントロピーです。エントロピーはその分布の不確実性を示す値でした。 エントロピーが高いほど不確かなことが起こるとゆうことです。 P(X)のエントロピーとは$-\int_{-\infty}^{\infty} logP(X)$でした。 では推定した確率分布Q(X）は確率分布P(X)に対してどれだけ不確実性を持っているのでしょうか。エントロピーとは情報量の期待値でした。確率分布Q(X）が持つ情報量は$-logQ(X)$です。この情報量を確率P(X)で期待値をとります。 式は以下のようになります。 $$-\int_{-\infty}^{\infty} P(X) logQ(X)$$ この値と真の分布のエントロピーとの差を二つの分布間の差として定義します。式では以下のようになります。 $$-\int_{-\infty}^{\infty} P(X) logQ(X) - (--\int_{-\infty}^{\infty} P(X) logP(X)))$$ これを式変形すると $$-\int_{-\infty}^...
コメントを投稿
続きを読む

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む