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

マハラノビス距離

Introduction


今日はマハラノビス距離について書いていきます。
マハラノビス距離はそれぞれの次元に相関があるときに有効とされています。
ある特徴と特徴に相関があることは往々にしてあると思います。
この距離は距離の公理を満たします。
また、統計学において大事な距離関数になります。
もし、統計や機械学習に興味がおありでしたらぜひこのブログをご覧ください。

概要

  • 距離の公理
  • マンハッタン距離の定義
  • マンハッタン距離のイメージ

距離の公理

もし、dが距離関数であるならば、dは次を満たします。
\(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)\)

マハラノビス距離

マハラノビス距離は距離関数です。
次のように定義されます。
\[D_{M}(x) = \sqrt{(x-\mu)^T \Sigma^{-1} (x-\mu)}\]
ここで、 \(\mu\) is mean vector
\[\mu = (\mu_1,\mu_2,....,\mu_n)\]
さらに \(\Sigma\) は共分散行列です。
xとyのマハラノビス距離は
\begin{eqnarray*} d(x,y) &=& \sqrt{(x-\mu-(y-\mu)^T \Sigma^{-1} (x-\mu-(y-\mu)}\\ &=& \sqrt{(x-y)^T \Sigma^{-1} (x-y)} \end{eqnarray*}です。

マハラノビス距離のイメージ

初めに、ユークリッド距離を見てみましょう。
\[d(x,y) = \sqrt{<x^T,y>}\]
ユークリッド距離は \(x\) and \(y\) がもし、ある円の上にあるのなら、同じ距離としてみます。
enter image description here
これはデータが円状に分布しているときに有効になります。
enter image description here
しかし、データが楕円上に分布しているときは、ユークリッド距離は有効ではありません。
enter image description here
なぜなら、上のXとYを同じ距離だと見たいからです。
マハラノビス距離はXとYが同じ楕円の上のある時に等距離とみなします。
enter image description here
距離は機械学習でよく登場します。距離関数をマハラノビス距離を使うことでなにか面白い結果が得られるかもしれません。

コメント

このブログの人気の投稿

Thorem of SVM part 2

Introduction 日本語 ver This post is written about theorem of SVM. This post is part 2. Part 1 is written about deriving the objective function. I will write about dual problem. The objective function which deriving in Part 1 is called the main problem. Typically, We optimize not the main problem, but the dual problem. I will write about deriving the dual problem from the main problem. If you until look up part 1, please look up Theorem of SVM part 1 . I implement SVM. It post is Implement linear SVM Implement kernel SVM Overview Main problem Dual problem  Lagurange function maximize L about dual variable, minimize L about primal variable minimize L about primal variable, maximize L about dual variable. Main problem I will review the main problem in Part 1. $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$ This problem is called s...

K-means 理論編

Introduction English ver 今日は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で他は0であるので、 $$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}|| + ...

Definition of Topology space

Introduction 日本語 ver Today, I will write about General Topology. General topology is very impossible for studying mathematics. General topology defines phase to define continuity of function. Today, I will explain phase. Also, This post is my review of General Topology. Overview  Distance space Axiom of phase Topology space Open set Distance space Firstly, Distance space is defined. Let X is set, $d:X\times X ->\mathbb{R}$, (X,d) is distance space $\iff$ $\forall x,y \in X,~~~~~d(x,y) \geq 0$ $\forall x,y \in X,~~~~~x = y \implies d(x,y) = 0$ $\forall x,y \in X,~~~~~d(x,y) = d(y,x)$ $\forall x,y,z \in X, ~~~~d(x,y) + d(y,z) \geq d(x,z)$ this condition is called axiom of distance. d is called distance function. Topology  space Let (X,d) is distance space. $\mathbb{O} \in 2^X$ is phase in (X,d) $\iff$ $\phi,X \in \mathbb{O}$ $\forall O_1,O_2 \in \mathbb{O} \implies O_1 \cap O_2 \in \mathbb{O}$ $\forall \Lambda ,~~\forall \{O_\l...