カーネルk-meansの実装

Introduction  

English ver

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

English ver

今回使うのは二つのデータセットです。一つ目は、普通の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