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

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:

コメント

コメントを投稿

このブログの人気の投稿

MAP推定

Introduction English ver 今日はMAP推定（事後確率最大化法）について書きました。MAP推定ではベイズの定理を使います。データが少ないとき、最尤推定の結果をあまり信用できない話は、最尤推定の時に書きました。この時、MAP推定では自分の事前に持っている情報を取り入れることができます。 概要 ベイズの定理 MAP推定 共役分布 MAP推定の例 ベイズの定理 ベイズの定理は $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ です。 ただし、 $P(A|B)$ はBが起こった時のAの起こる確率です。 詳しくは  http://takutori.blogspot.com/2018/04/bayes-theorem.html  を見てください。 Map推定 MAP推定ではベイズの定理を使います。MAP推定は事後確率が最大になるようなパラメータを選びます。 いま、$x_1,x_2,...,x_n$というデータを$\theta$というパラメータを持つ分布から得られたとする。この時$P(\theta|x_1,x_2,...,x_n)$を求めたい。 ここで、ベイズの定理を使う。 $$P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}$$ ここで、$P(\theta)$は$\theta$の事前分布である。 $x_1,x_2,...,x_n$はそれぞれ独立であるので、 $$P(x_1,x_2,...,x_n | \theta ) = \Pi_{i=1}^n P(x_i|\theta)$$. よって、マップ推定は $$\theta^{\star} = \arg \max_{\theta} \frac{\Pi_{i=1}^n P(x_i|\theta) P(\theta)}{P(x_1,x_2,...,x_n)}$$ となる。 $P(x_1,x_2,...,x_n)$という値は$\theta$には依存しない。よって、定数であり、最適化に定数は関係ないので、排除すると、MAP推定は次のようになる。 $$\th...
コメントを投稿
続きを読む

Rolle’s theorem

Introduction 日本語 ver This post is written Rolle’s theorem. The mean-value theorem is proved by Rolle’s theorem. I will write Mean-value theorem at a later. I introduce Maximum principle because proving Rolle’s theorem need Maximum principle. Maximum principle It is very easy. f is continuous function on bounded closed interval.\(\implies\)** f have max value.** Proof This proof is difficult. I write this proof in other posts. Maximum Principle Rolle’s theorem f is continuous function on [a,b] and differentiable function on (a,b). \[f(a) = f(b) \implies \exists ~~c ~~s.t~~ f'(c) = 0 , a<c<b\] Proof f(x) is constant function \[\forall c \in (a,b) , f'(c) = 0\] else when \(\exists t ~~s.t~~f(a) < f(t)\), \(\exists c ~~s.t~~ \max f(x) = f(c)\) by Maximum principle I proof \(f'(c)=0\) f is differentiable on \(x = c\) and \(f(c) >= f(c+h)\). Thus \[f'(c) = \lim_{h \rightarrow +0} \frac{f(c+h) - f(c)}{h} \leq 0\] \[f'(c) = \lim...
コメントを投稿
続きを読む

ヒープ構造

Introduction English ver 今日はヒープ構造について書きます。ヒープ構造はデータ構造の一種です。ちょうど大学の自主ゼミグループのセミナー合宿に参加させてもらい、そこでグラフ理論を勉強したので、メモをしておこうと思います。   slide  はこんなのを使いました。 Overview データ構造 二分木 ヒープ 実装 ヒープソート データ構造 ヒープ構造の前に、データ構造について、説明します。データ構造とは、データを保存する手法であります。データ構造は、そのデータについてどのような操作を行いたいかによって、最適なものを選ぶことになります。 ヒープ構造はプライオリティキューと呼ばれれるデータ構造を表す方法です。プライオリティキューで行いたい操作は以下の二つです。 データの追加 最小値の抽出 二分木 まず、グラフを定義します。E と V は集合とし、 $e \in E$、つまりEの要素をedge(枝)と呼びます。また、$v \in V$、つまりVの要素をnodeと呼びます。 g:E->V×V をEからV × Vへの写像とします。この時、.(E,V,g)をグラフを言います。 例えば、次のようなものがあります。 丸いのがそれぞれのnodeで、矢印がedgeになります。 各edgeに対して、始点v1と始点v2を対応させるのが写像gの役目です。 根付き木とは次のような木のことです。 これはnode1からnodeが二つずつどんどん派生していっています。 特に、次のような木を 二分木 といいます。 特徴は、ノードが上からなおかつ左から敷き詰められています。一番上のノードを根といいます。また、例えば2を基準にすると、1は2の親、4,5は2の子、3は2の兄弟、8,9,10,11,12は葉と呼ばれます。 ヒープ ヒープ構造はプライオリティキューを二分木で表現したものです。プライオリティキューでやりたいことは次のことでした。 データの追加 最小値の抽出 . では、どのようにこの二つの操作を実現するのでしょうか。 初めにデータの追加について説明します。 1. 二分木の最後に追加す...
コメントを投稿
続きを読む