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

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:

コメント

コメントを投稿

このブログの人気の投稿

Theorem of K-means

Introduction 日本語 ver Today, I will write about the theorem of K-means algorithm. K-means algorithm is a method to do clustering about K of class. The post of implement K-means is Implement kernel K-means This post is written about kernel K-means. The kernel K-means is the method which covers the weak point of K-means. I will explain kernel K-means another post. Overview 1 of K coding scheme prototype vector Distortion measure Computing 1 of K coding scheme K-means algorithm is clustering K of class. Now, K-means algorithm expresses that $x_n$ be belong to k like as follows. Let vector $r_n:1 \times K$ is $$r_n := (0,0,..,1,..,0)$$ this vector have 1 in element of k'th and have 0 in else. This expression is called 1 of K coding scheme. Prototype vector K-means algorithm chooses vector which called a prototype. this vector has represented by the cluster. K-means algorithm is regard mean vector as representative of the cluster. I...
コメントを投稿
続きを読む

Thorem of SVM part 2

Introduction 日本語 ver This post is written about theorem of SVM. This post is part 2. Part 1 is written about deriving the objective function. I will write about dual problem. The objective function which deriving in Part 1 is called the main problem. Typically, We optimize not the main problem, but the dual problem. I will write about deriving the dual problem from the main problem. If you until look up part 1, please look up Theorem of SVM part 1 . I implement SVM. It post is Implement linear SVM Implement kernel SVM Overview Main problem Dual problem  Lagurange function maximize L about dual variable, minimize L about primal variable minimize L about primal variable, maximize L about dual variable. Main problem I will review the main problem in Part 1. $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$ This problem is called s...
コメントを投稿
続きを読む

SVMの理論 part 2

Introduction English ver 今日はSVMの定理について書いていきます。 この記事はpart 2になります。Part 1 では目的関数の導出までを書きました。Part 2では双対問題とゆわれるものを導出します。Part 1で導いた目的関数は主問題と呼ばれます。一般的に、SVMでは主問題ではなく、双対問題を解くことで最適解を得ます。 もし、まだPart 1を見ておられない場合は、 Theorem of SVM part 1 を見てくださるとよいのではないかと思います。 SVMの実装編は Implement linear SVM Implement kernel SVM を御覧ください。 概要 主問題 双対問題  ラグランジュ関数 主変数について、最小化、双対変数について最大化 双対変数について最大化、主変数について最小化 主問題 Part 1で導いた主問題の復習をしておきます。 $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$ これはソフトマージンの時の目的関数ですが、以後ソフトマージンの場合のみを扱っていきます。 さて、双対問題と呼ばれるものですが、これは主問題から自然に導かれます。 双対問題 SVMの最適化問題は凸二次最適化問題と呼ばれる種類の問題です。凸二次最低化問題は、必ず大域最適解に近づくことが知れれており、数値上の安全性が高いとされています。 双対問題を導出します。まず、主問題を以下のように書き換えます。 $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0,~~~, \forall i \in N~ -\epsilon \...
コメントを投稿
続きを読む