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

このブログの人気の投稿

ヘッセ行列

Introduction English ver 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要ヘッセ行列の定義ベクトルを用いたテイラー展開関数の最適性ヘッセ行列の定義仮定 f は次のような条件を満たす関数です。. f はn次元ベクトルから実数値を出力します。このベクトルは次のように表せます。

$x = [x_1,x_2,,,,x_n]$

$\forall x_i , i \in {1,2,,,n}$ , f は二回偏微分可能です。定義ヘッセ行列は

$\frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。$ よってヘッセ行列は次のように表せます。 \[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldo...

大学院試験　-外部への道しるべ-

始めにこの度、京都大学大学院情報学研究科システム科学専攻に合格することができました！！！僕は現在、立命館大学という関西の私立大学に通っているので、外部受験をしたことになります。さらに、学部は数学専攻で、大学院からは情報学(の中でも機械学習)専攻になるので、専門も変えることになります。この記事では、外部の大学院、もしくは専攻替えを考えている人向けに書こうと思っているので、目次で気になった項目があれば、ぜひ、読んでいってくださいませ。( *´艸｀) ちなみに、予測点数は線形微積6~7割、専門科目満点、英語かなり低いので内緒です。（笑）得点開示を要求するので、得点がわかったら、また追記します。目次外部受験を目指すまで、目指したきっかけ外部受検の大変さ専攻替えの大変さ合格するために英語が苦手な人へ数学科の学部から情報学(機械学習)の大学院を目指す人へ応援外部受検を目指すまで、目指したきっかけここでは、自分の大学生活がどんなだったかを書いてるだけなので、興味のない人は飛ばしましょう。（笑）僕が学部二回生頃に、当時数理科には機械学習の研究をされている先生が一人だけ所属されていました。その先生に、直接弟子入りさせていただき、僕の機械学習への道は始まりました。。。(メインは遺伝統計学の研究でした。) 弟子入りした直後は、タイピングもなめくじのように遅かったですし、gitもpullする前にpushしたこともありました。。。しかし、その先生は、目的に最先端で届く道のりを用意してくださいました。プログラミングを初めて一か月ほどで、t-SNEの実装をしたり(遺伝統計学の研究で必要だった)、四か月ほどで、カーネルc-SVMの実装をしたり(やってみなとゆわれて（笑）)することができました。その後も、学部二回生、三回生ながら、論文を読んで実装してきました。学部二回生冬には、遺伝統計学の研究を株式会社パーソルキャリアさん主催のハッチングフェスというデータサイエンティストのためのイベントで、発表しました。このイベントでは、企業の方もたくさん来られて、知り合えるチャンスがかなりあります！！ (名刺を作っておくと、「えっ、学生なのに名刺持ってるの？！」ってなるので、覚えてもらえます。...

カーネル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-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...

journey of Froakie (ケロマツの旅路)

このブログを検索