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

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:

コメント

コメントを投稿

このブログの人気の投稿

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　 実装例 以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。 予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...
コメントを投稿
続きを読む

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

dijkstra method

Introduction 日本語 ver Today, I will write about the dijkstra method. This method is algorithm which find the shortest distance. The map is expressed by graph. If you never see  this page , look at its page. This page explain the heap structure and definition of graph. The dijkstra method used heap structure, Because heap structure reduce the amout of calculation of dijkstra method. I use  this slide  to explain dijkstra. Overview Algorithm Implementation Algorithm This algorithm is  Decide start node, and this node named A. Allocate $d=\infty$ for each node, but d=0 for start node. Adjacent node of A named adj_list.  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. Remove A from graph network. Find node which have the smallest d and it named A, and if network have node, back to 4. I explain this algorithm by drawing.  I explain algorithm by using this graph.  Fis...
コメントを投稿
続きを読む