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

Theorem of kernel K-means

Introduction

Today, I will write about a theorem of kernel K-means. The kernel K-means cover the weak point of K-means. I will explain this weak point of K-means and strong point of kernel K-means. If you have not looked yet, please look at the Theorem of K-means.
I implement kernel K-means. Its post is Implement kernel K-means.

Overview

  •  A weak point of K-means
  • Kernel trick 
  • kernel K means
  • Algorithm


A weak point of K-means

For example, I prepare the following dataset.

It is impossible for this dataset to cluster by K-means because this data is distributed shape of the circle. K-means classify data in accordance with the Euclid distance between data and prototype. The prototype is representative of each class. A Prototype of K-means is mean vector. Thus, K-means classify dataset as follows.

K-means does not work, if not so this like dataset.
The dataset which is able to classify by K-means is consist of mass for each class. For example,


Kernel K-means cover this weak point of K-means.

Kernel Trick
Firstly, I explain Kernel Trick.
If dataset $X$ is not able to classify linear hyperplane. Then, the map $\phi$ send to space which is able to classify linear hyperplane.


Kernel is defined as follows.
$$K(x,y) = \phi(x)^T \phi(y)$$

It is difficult to compute $\phi$, but It is easy to compute $K(x,y)$.
This method is called kernel trick.

kernel K means

I review the objective function of K-means.

$$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$

here, prototype is $\mu_i ~\forall k \in K$.
$r_n$ is the 1 of K coding scheme and $r_{nk}$ is k'th element of $r_n$
then
$$\mu_k = \frac{\sum_{n} r_{n_k} x_n}{\sum_n r_{n_k}}$$
and
$$k = \arg \min_{j} || x_n - \mu_{j} || \implies r_{nk} = 1$$

$$else \implies r_{n_k} = 0$$


I rewrite this objective function as follows.

$$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||\phi(x_n)-\mu_k||^2$$

then
$$\mu_k = \frac{\sum_{n} r_{n_k} \phi(x_n)}{\sum_n r_{n_k}}$$


Thus, distance between $x_n$ and prototype $\mu_k$ is
$$||\phi(x_n) - \frac{\sum_{m}^{N} r_{m_k} \phi(x_m)} {\sum_{m}^{N} r_{m_k}} ||^2$$
$$= \phi(x_n)^T \phi(x_n) - \frac{2 \sum_{m}^{N} r_{n_k} \phi(x_n)^T \phi(x_m)}{\sum_{m}^{N} r_{n_k}} + \frac{\sum_{m,l}^{N} r_{n_k} r_{n_k} \phi(x_m)^T \phi(x_l)}{ \{ \sum_{m}^{N} r_{n_k} \}^2 }$$

kernel K-means compute $\phi(x_n)^T \phi(x_m)$ as $K(x_n,x_m)$

Algorithm

  1. make initial value of prototype. input K: number of clusters.
  2. for iteration in iteration times.
  3. for $n \in N$ do 
  4. for $k \in K$ do
  5. Compute distance $x_n$ and prototype of class k.
  6. end for k
  7. Pick up class $k_n \in {1,2,..,K}$ which make distance  $x_n$ and prototype of class k minimizing.
  8. divide $x_n$ in class $k_n$
  9. end for n
  10. if there is no change, finish repeating iteration.


Reference
http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf

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$としま...
コメントを投稿
続きを読む

K-means 理論編

Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事は カーネルK-meansの実装 を御覧ください。 この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。 概要 1 of K 符号化法 プロトタイプ 歪み尺度 最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。 ベクトル$r_n:1 \times K$ を $$r_n := (0,0,..,1,..,0)$$ このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。 こののような表現の仕方を1 of K符号化法と呼びます。 プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。 歪み尺度 プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。 この時、k-meansの目的関数は次のようになります。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 $r_{nk}$ は$r_n$のk番目の要素です。 この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、 $$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$ ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。 よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...
コメントを投稿
続きを読む

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