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

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

コメント

コメントを投稿

このブログの人気の投稿

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...
コメントを投稿
続きを読む

カーネルSVMの実装

Introduction English ver 今日はカーネルSVMを実装しました。 最適化には内点法を実装しました。 この記事では実装のみ書いていますが、理論編もそのうちに書きたいと思います。書き次第、リンクを貼っておきます。 # 第一弾書きました。 SVMの理論 part 1 僕のcomputerはwindowsでOSもwindowsです。 実装はPython3で行います。 概要 カーネルとは データセットについて 実装の結果 カーネルとは カーネルとは非線形問題を解くための手法です。 直線で分類できないようなデータをある写像をもとで、直線で分類できるような分布に変形することです。次の画像を見たほうがわかりやすいかもしれません。 ⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓ このように変形することをカーネルトリックといいます。 変形されたデータは写像\(\phi\)によって\(\phi(x)\)と表現されます。 \[\phi:x -> \phi(x)\] しかし、SVMではカーネル関数は次のように表されることが多いです。 \[K(x,y)=\phi(x)^T \phi(y)\] なぜなら、SVMでは \(\phi(x)^T \phi\)のみを計算するからです。 最もよく使われているカーネルはRBFとpolynomialです。 RBF \[K(x,y) = \exp(-\gamma ||x-y||^2)\] polynomial \[K(x,y) = (x^Ty+c)^p\] \(K(x,y) = x^Ty\)とすればこれは線形SVMになります。 データセット 今日使うデータセットはnp.random.randnによって生成された正規分布に従う乱数です。 と このデータを作ったコードは ここ に置いてあります。 Implementation 今回はRBFカーネルを使いました。 \(\gamma = 0.5\) 正規化係数50とすると次のようになりました。 次に二つ目のデータセットに対して、RBF kernelを使いました。 \(\gamma = 0.5\) 正規化係数を100とすると、次のよ...
コメントを投稿
続きを読む

Graph theory in Python

Introduction 日本語 ver Today, I write the networkx module for graph theory in Python. I write about basis of Gragh theory. Please look at this page . This post is not written Graph theory, but I want to share module in Python for Graph theory. Networkx Python3 have Networkx module. If you have python2, you should install by pip pip install networkx Make Graph by Networkx first, import networkx module and make instance. import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() next, add node and edge G.add_node(1) # add Multiple nodes G.add_nodes_from([2,3,4]) G.add_edge(1,2) # add Multiple edges G.add_edges_from([(3,4),(1,2),(4,6)]) next, plot G nx.draw(G) plt.show() networkx have many function. I will write new learning about networkx in this post. Reference https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f http://akiniwa.hatenablog.jp/entry/2013/05/12/012459
コメントを投稿
続きを読む