Processing math: 1%
スキップしてメイン コンテンツに移動

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 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 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...
コメントを投稿
続きを読む

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータXを例えば次のように線形分離できるように\phi(x)に送る写像\phiを考えます。 カーネルは次のように定義されます。 K(x,y) = \phi(x)^T \phi(y) \phiを具体的に計算することは難しいですが、K(x,y)を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2 ここで、 プロトタイプは\mu_i ~\forall k \in Kとしま...
コメントを投稿
続きを読む