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

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

コメント

コメントを投稿

このブログの人気の投稿

Entropy

Introduction sorry, this page is Japanese only.   今日はエントロピーについて書こうと思います。これは確率論や統計学で死ぬほど大事なKLダイバージェンスといものを理解するために必要な知識です。 この記事ではエントロピーについてしか書きませんが、今度KLダイバージェンスについても書こうと思います。 KLダイバージェンスの記事はこちら Entropy 直観的な話 ある事象、「例えば明日大学の講義にX分遅刻する」という事象を考えます。 この事象に対する確率がP(X)が与えられているとしましょう。P(1)は一分遅刻する確率です。この時確率分布P(X）が持つ情報量はどれだけのものかとうことを考えたいとします。 明日の講義はテストを受けるとします。そのテストを受けないと単位を落としてしまします。しかし、テスト前日はすごく寝不足としましょう。遅刻する確率が99パーセントとわかった時、ほとんどどうあがいても遅刻するのであれば単位を落とすのはほぼ確実といえます。 よって前日に徹夜で勉強するよりも、睡眠不足を解消するために寝る方がよっぽど効率的であることがわかります。しかし、遅刻をする確率が50パーセントとわかった時、前日にテスト勉強をすればよいのか、せずに睡眠をとればよいのかわかりません。このように、確率が偏っているほど何が起こるか予測しやすく、対策を立てやすいのです。遅刻する確率が99パーセントとわかる時は遅刻する確率が50パーセントとわかった時に比べて圧倒的に多いはずです。 確率P(X)に対してこの情報量のことをP(X)の 自己エントロピー といいます。 そして、自己エントロピーの期待値のことを 平均エントロピー といいます。 立式 性質 ではこの情報量を数式で表していきましょう。まず自己エントロピーには大事な性質が二つあります。それが 互いに独立な確率変数の自己エントロピーはそれぞれの情報量の和で表される。 自己エントロピーは減少関数である。 の二つです。 自己エントロピーの加法性 互いに独立な確率変数の情報慮はそれぞれの情報量の和でなければいけません。例えば「明日の講義がY分早く終わる」という事象を考えます。この確率変数Yはあなたが何分講義に遅刻...
コメントを投稿
続きを読む

MAP推定

Introduction English ver 今日はMAP推定（事後確率最大化法）について書きました。MAP推定ではベイズの定理を使います。データが少ないとき、最尤推定の結果をあまり信用できない話は、最尤推定の時に書きました。この時、MAP推定では自分の事前に持っている情報を取り入れることができます。 概要 ベイズの定理 MAP推定 共役分布 MAP推定の例 ベイズの定理 ベイズの定理は $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ です。 ただし、 $P(A|B)$ はBが起こった時のAの起こる確率です。 詳しくは  http://takutori.blogspot.com/2018/04/bayes-theorem.html  を見てください。 Map推定 MAP推定ではベイズの定理を使います。MAP推定は事後確率が最大になるようなパラメータを選びます。 いま、$x_1,x_2,...,x_n$というデータを$\theta$というパラメータを持つ分布から得られたとする。この時$P(\theta|x_1,x_2,...,x_n)$を求めたい。 ここで、ベイズの定理を使う。 $$P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}$$ ここで、$P(\theta)$は$\theta$の事前分布である。 $x_1,x_2,...,x_n$はそれぞれ独立であるので、 $$P(x_1,x_2,...,x_n | \theta ) = \Pi_{i=1}^n P(x_i|\theta)$$. よって、マップ推定は $$\theta^{\star} = \arg \max_{\theta} \frac{\Pi_{i=1}^n P(x_i|\theta) P(\theta)}{P(x_1,x_2,...,x_n)}$$ となる。 $P(x_1,x_2,...,x_n)$という値は$\theta$には依存しない。よって、定数であり、最適化に定数は関係ないので、排除すると、MAP推定は次のようになる。 $$\th...
コメントを投稿
続きを読む

ヒープ構造

Introduction English ver 今日はヒープ構造について書きます。ヒープ構造はデータ構造の一種です。ちょうど大学の自主ゼミグループのセミナー合宿に参加させてもらい、そこでグラフ理論を勉強したので、メモをしておこうと思います。   slide  はこんなのを使いました。 Overview データ構造 二分木 ヒープ 実装 ヒープソート データ構造 ヒープ構造の前に、データ構造について、説明します。データ構造とは、データを保存する手法であります。データ構造は、そのデータについてどのような操作を行いたいかによって、最適なものを選ぶことになります。 ヒープ構造はプライオリティキューと呼ばれれるデータ構造を表す方法です。プライオリティキューで行いたい操作は以下の二つです。 データの追加 最小値の抽出 二分木 まず、グラフを定義します。E と V は集合とし、 $e \in E$、つまりEの要素をedge(枝)と呼びます。また、$v \in V$、つまりVの要素をnodeと呼びます。 g:E->V×V をEからV × Vへの写像とします。この時、.(E,V,g)をグラフを言います。 例えば、次のようなものがあります。 丸いのがそれぞれのnodeで、矢印がedgeになります。 各edgeに対して、始点v1と始点v2を対応させるのが写像gの役目です。 根付き木とは次のような木のことです。 これはnode1からnodeが二つずつどんどん派生していっています。 特に、次のような木を 二分木 といいます。 特徴は、ノードが上からなおかつ左から敷き詰められています。一番上のノードを根といいます。また、例えば2を基準にすると、1は2の親、4,5は2の子、3は2の兄弟、8,9,10,11,12は葉と呼ばれます。 ヒープ ヒープ構造はプライオリティキューを二分木で表現したものです。プライオリティキューでやりたいことは次のことでした。 データの追加 最小値の抽出 . では、どのようにこの二つの操作を実現するのでしょうか。 初めにデータの追加について説明します。 1. 二分木の最後に追加す...
コメントを投稿
続きを読む