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

カーネルK-means 理論編

Introduction

今日は、カーネル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とします。
r_nは1 of K符号化法であり、r_{nk}はr_nのk番目の要素です。
この時、
\mu_k = \frac{\sum_{n} r_{n_k} x_n}{\sum_n r_{n_k}}
そして、
k = \arg \min_{j} || x_n - \mu_{j} || \implies r_{nk} = 1

else \implies r_{n_k} = 0


次のように目的関数を書き換えます。

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

その時、
\mu_k = \frac{\sum_{n} r_{n_k} \phi(x_n)}{\sum_n r_{n_k}}


それゆえ、x_nとプロトタイプ\mu_kの距離は
||\phi(x_n) - \frac{\sum_{m}^{N} r_{m_k} \phi(x_m)} {\sum_{m}^{N} r_{m_k}} ||^2
= \phi(x_n)^T \phi(x_n) - \frac{2 \sum_{m}^{N} r_{n_k} \phi(x_n)^T \phi(x_m)}{\sum_{m}^{N} r_{n_k}} + \frac{\sum_{m,l}^{N} r_{n_k} r_{n_k} \phi(x_m)^T \phi(x_l)}{ \{ \sum_{m}^{N} r_{n_k} \}^2 }

カーネルK-meansでは\phi(x_n)^T \phi(x_m)をK(x_n,x_m)として計算します。

Algorithm

  1. プロトタイプの初期値、K:クラスの数
  2. for iteration in iteration times.
  3. for n \in N do 
  4. for k \in K do
  5. x_nとクラスkのプロトタイプの距離を計算します。
  6. end for k
  7. x_nとクラスkのプロトタイプの距離の中で最小にさせるようなクラスk_nを選びます。
  8. x_nのクラスをk_nとします。
  9. end for n
  10. もし、プロトタイプベクトルにほとんど変化がない場合はカーネルK-meansを終了します。


Reference



ラベル

Labels:

コメント

コメントを投稿

このブログの人気の投稿

ロジスティック回帰 理論編

Introduction English ver 今日はロジスティック回帰について書こうと思います。ロジスティック回帰は機械学習の中でも基本とされています。ロジスティック回帰は二値を分類するためのアルゴリズム、モデルです。 概要 この記事はPRMLを参考に書かせていただいています。 最適化には反復再重みづけ最小二乗法を用いています。 シグモイド関数 分類のための確率を定義 交差エントロピー誤差関数 反復再重みづけ最小二乗法 シグモイド関数 初めにシグモイド関数を定義します。 以下のような関数です。 \sigma(a) = \frac{1}{1+\exp(a)} 後に扱うので、シグモイド関数の微分を計算しておきます。きれいな形をしています。 \begin{eqnarray*} \frac{d}{d a} \frac{1}{1+\exp(a)} &=& \frac{\exp(-a)}{(1+\exp(-a))^2} \\ &=& \frac{1}{1+\exp(-a)} \frac{\exp(-a)}{1+\exp(-a)}\\ &=& \frac{1}{1+\exp(-a)} \{ \frac{1+\exp(-a)}{1+\exp(-a)} - \frac{1}{1+\exp(-a)} \} \\ &=& \sigma(a)(1-\sigma(a)) \end{eqnarray*} シグモイド関数は機械学習において大事な役割を果たしています。 シグモイド関数は以下のような形をしています。 これを見てわかる通り、シグモイド関数は次のような性質を持っています。 シグモイド関数は 定義域は(-\infty,\infty)で定義され、値域は(0,1)で定義されています シグモイド関数は単調増加関数です シグモイド関数は(0,0.5)で点対称です シグモイド関数の値を確率として考えることができるようになります。 分類のための確率の定義 初めにデータが正しく分類されたかの確率を考えてみる。 この直線は超平面だと思ってください。 超平面は以下のように表されます。 w^T x= 0 wは超平面に対する法線ベク...
コメントを投稿
続きを読む

Mahalanobis' Distance

Introduction 日本語 ver Today, I will write about Mahalanobis’ Distance. Mahalanobis’ Distance is used when each dimension has a relationship. This distance is fulfilled definition of distance. Mahalanobis’ Distance is important for Statics. If you interested in Statics or Machine Learning, Please see my this blog. Overview definition of distance deficition of Mahalanobis’ Distance image of Mahalanobis’ Distance definition of distance if d is distance function, d if fulfilled following condtion. d:X \times X -> R d(x,y) \geq 0 d(x,y) = 0 \leftrightarrow x = y d(x,y) = d(y,x) d(x,z) \leq d(x,y) + d(y,z) Mahalanobis’ Distance Mahalanobis’ Distance is distance function. Mahalanobis’ Distance is defined by following from D_{M}(x) = \sqrt{(x-\mu)^T \Sigma^{-1} (x-\mu)} here, \mu is mean vector \mu = (\mu_1,\mu_2,....,\mu_n) and, \Sigma is variance-convariance matrix. Mahalanobis’ Distance between x and y is \begin{eqnarray...
コメントを投稿
続きを読む