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

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:

コメント

コメントを投稿

このブログの人気の投稿

最尤推定

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 件のコメント
続きを読む

heap structure

Introduction 日本語 ver Today, I will write about heap structure. The heap structure is one of the data structure. My reason of studying heap structure is that I joined seminar of Ritsumeikan Univ. I used this  slide  in seminar of Ritsumeikan Univ. Overview data structure binary tree heap Implementation heap sort Data structure I will explain about data structure before explaining about heap. Data structure is how to keep data. Data structure is selected on the basis of operation which you want to.  Heap belong to data structure called priority queue. priority queue have purpose which  add data pick up minimum data (and remove)  Binary Tree Let, E and V are sets. The element $e \in E$ is called edge. The element $v \in V$ is called node. g:E->V×V is map to V × V from E. (E,V,g) is called graph. For example, The arrows are edge. The circles are node. This is expressed map. It is possible to go to node 3 from 1....
コメントを投稿
続きを読む

Pythonでグラフ理論

Introduction English ver 今日はnetworkxというpythonのモジュールについて書きます。 グラフ理論の定義などの情報は ここ の記事に書いてあります。 この記事ではグラフ理論の中身については扱いませんが、Pythonでのnetworkxというモジュールについてメモをしておきます。 Networkx Python3にはnetworkxはすでに入っています。 Python2の方はpipを使ってinstallしてください。コマンドラインで以下のコマンドを実行します。 pip install networkx ではNetworkxを使ってグラフを作っていきます。 初めにimportをしてインスタンスを作っていきます。 import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() 次にグラフにノード（頂点）とエッジ（枝）を入れていきます。 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)]) ではこのGのグラフを描画していきましょう。 以下のコードで描画できます。 nx.draw(G) plt.show() Networkxはたくさんの関数を持っています。 また、随時追記していきたいと思います。 Reference https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f http://akiniwa.hatenablog.jp/entry/2013/05/12/012459
2 件のコメント
続きを読む