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

Theorem of K-means

Introduction

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. It is naturally derived from the objective function.

Distortion measure

Let prototype vector is $\mu_i ~\forall k \in K$.
Then, k-means have the objective function like as follows.

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

here, $r_{nk}$ is k'th element of $r_n$.

I explain about this objective function. because $r_{n}$ have only 1 in k'th element,

$$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$

here, $\mu_{k_n}$ is prototype vector of class which belonged $x_n$.

Thus,
$$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ... + ||x_N - \mu_{x_N}||$$


Firstly,I minimise $J$ about $r_n$.

Because $||x_n-\mu_k||^2$ is distance between $x_n$ and prototype vector of class k,
$r_n$ is decided as follows.

$$k = \arg \min_{j} || x_n - \mu_{j} || \implies r_{nk} = 1$$
$$else \implies r_{n_k} = 0$$



Secondly, I minimise $J$ about $\mu_k$ when I fix $r_{n_k}$.
Partial is
$$2\sum_{n=1} ^{N} r_{n_k} (x_n-\mu_k) = 0$$
Thus,
$$2\sum_{n=1} ^{N} \{r_{n_k} x_n\} - \mu_k \sum_{n=1}^{N}r_{n_k} = 0 $$
$$\mu_k = \frac{\sum_{n} r_{n_k} x_n}{\sum_n r_{n_k}}$$

We regard this value of $\mu_k$ as mean vector of class k.

As result, we found prototype vector is mean vector.

If you know EM algorithm, minimizing $J$ about $r_n$ is E step and minimizing $J$ about $\mu$ when I fix $r_n$ is M step.

Reference
https://www.amazon.co.jp/パターン認識と機械学習-上-C-M-ビショップ/dp/4621061224

Labels:

コメント

コメントを投稿

このブログの人気の投稿

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

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}|| + ...
コメントを投稿
続きを読む