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

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:

コメント

コメントを投稿

このブログの人気の投稿

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

ヘッセ行列

Introduction English ver 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 f は次のような条件を満たす関数です。. f はn次元ベクトルから実数値を出力します。 このベクトルは次のように表せます。 \[x = [x_1,x_2,,,,x_n]\] \(\forall x_i , i \in {1,2,,,n}\), f は二回偏微分可能です。 定義 ヘッセ行列は \(\frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。\) よってヘッセ行列は次のように表せます。 \[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldo...
コメントを投稿
続きを読む