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

Implement kernel k-means

Introduction  

Today, I implement kernel k-means. The k-means algorithm is clustering algorithm. A reason that I implement kernel k-means algorithm is that I and my friend conceived introducing kernel to k-means. I investigated paper of kernel k-means. I found [This page](http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf)  Thus I could implement kernel k-means algorithm. I introduce the implementation of normal k-means and kernel k-means.


I handle the only implementation of kernel k-means. I will write the theory of kernel k-means. If I finished writing it, I publish on this post.

# I finished. Theorem of K-means

Overview  


  • dataset  
  • a few explaining k-means
  •  k-means  
  •  kernel k-means  


Dataset  

I used two datasets. first data is designated for normal k-means. second data is designated for kernel k-means.


First data has consisted of three group and two-dimensional data, 300 samples.
The distribution is as follow.

Second data has consisted of two groups and two dimensional, 300 samples.
The distribution is as follow.

I publish a code of dataset.
THIS PAGE!!
A few explaining k-means
k-means algorithm computes mean vector in K class. second, k-means algorithm computes the distance between each data point and each mean vector. third, k-means algorithm choice as a new label of data point. How to choice is a mean vector in class K which minimize the distance between a mean vector and data point.
k-means  


Firstly, I implement normal k-means algorithm. I use first data to test my code. A Result of the test is complicated.


The centroid is mean vactor.


However, the k-means algorithm has weak points. You can understand by looking as follow.


This image is results that I use my k-means algorithm for second data.
Normal k-means depend on Euclid distance between the mean vector and data point in data space. Therefore I failed to cluster.

Kernel k-means
I failed to cluster in normal k-means.
However, I success clustering by using kernel trick.
Its result is as follow.



This clustering is complicated.
the kernel is the best way of non-linear clustering.


CODE
My code of kernel k-means algorithm is published in this page.

A git_Kmeans_def.py file is written function used in normal k-means.
A git_Kmeans_main.py file is the main file. This file is written if __name == '__main__':.

A git_kernel_Kemans_def.py file is written function used in kernel k-means.
A git_kernel_Kemans_main.py file is a main file. This file is written 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$としま...
コメントを投稿
続きを読む

最尤推定

Introduction English ver 今日は最尤推定について加工と思います。これは統計的推定でよく使われる手法です。最尤推定の例も書こうと思います。初めに尤度の説明をし、そのあとで最尤推定の説明をします。 概要 尤度 最尤推定 最尤推定の問題点 尤度 前提条件から得られる観察データを考えます。この時、えられた観測データに対して前提条件が尤もらしい条件であるかの値を尤度といいます。 なにをゆっているのかわからない人がほとんどだと思います。。。 尤度の例を扱っていきます。 コインを投げることを考えます。このコインは確率Pで表、確率1-Pで裏を出すコインだとします。 例えば、100回コインを投げたとき、全て表だったとします。この時このコインが表が出る確率はかなり1に近いことが予想されます。 ではもし、表が出る確率PがP=0.5だとします。この時、表が100回連続で出る確率は$0.5^{100} = 7.88860e-31$になります。あり得ない確率ですね。これがP=0.5としたときのもっともらしさです。つまり、あまり現実的ではないということです。 もしP=0.99とするとき、100回とも表が出る確率は$0.99^{100} = 0.3666....$となります。つまり、P=0.99としたときの尤度は0.36くらいということです。よって、P=0.5よりかは現実見があることになります。まだまだ低い数字ではありますが。 観測データである、100回表が出るという事象を固定したとき、尤度はPを変数としたP(100回表|P)を尤度関数と呼びます。この関数の値を尤度と呼びます。 尤度が高いほうが尤もらしい値、つまり理にかなっているなと感じることができる値ということになります。 例えば、先ほどの例でゆうと、 P=0.5としたときの尤度は7.88860e-31でした。P=0.99としたときの尤度は0.3666でした。よってP=0.5より、P=0.99のほうが尤もらしい自然な値ということになります。 最尤推定 最尤推定とは得られた観測データからデータが依存している分布のパラメーターを推測するための手法です。 最尤推定では尤度を最大化して、最も尤もらしいパラメーターを求めます。 確率密度関数...
3 件のコメント
続きを読む

離散フーリエ変換

Introduction English ver 今日は離散フーリエ変換について書きます。 現在、シグナル解析についてのpdfを作成中です。このpdfは github で公開中です。 シグナル解析は、courseraのレクチャーで勉強中です。 ここ にリンクを貼っておきます。 pdfは随時更新中です。
2 件のコメント
続きを読む