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

K-means 理論編

Introduction


今日は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}|| + ... + ||x_N - \mu_{x_N}||$$

では、この目的関数を最小化することを考えます。
初めに$J$を$r_n$について最小化することをかんがえます。

$||x_n-\mu_k||^2$ は$x_n$と$x_n$が属しているクラスのプロトタイプとの距離なので、,
$r_n$ は次のように決まります。

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



次に、$r_{n_k}$を固定したときに、$J$を$\mu_k$について最小化します。
偏微分は
$$2\sum_{n=1} ^{N} r_{n_k} (x_n-\mu_k) = 0$$
よって
$$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}}$$

この値はkクラスの平均ベクトルとなっていることがわかります。
その結果、プロトタイプは平均ベクトルであることがわかります。

$r_n$を$\mu_k$について、最適化するわけですが、どちらにももう片方の変数が使われているため、どちらかを固定して交互に最適化する必要があります。

$r_n$を求める$\rightarrow$ $r_n$を固定して$\mu_k$を求める$\rightarrow$ $\mu_k$を固定して$r_n$を求める$\rightarrow$ .......

収束条件は平均ベクトルの変化量を用いることが多いです。平均ベクトルがほとんど動かなくなったら修了します。


もし、EMアルゴリズムをご存知であるならば、$J$を$r_n$について最小化するのはEステップにあたり、$J$を$\mu$について最小化することはMステップにあたります。

Reference

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

ヒープ構造

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. 二分木の最後に追加す...
コメントを投稿
続きを読む

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