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

Mahalanobis' Distance

Introduction


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*} 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*}

Image of Mahalanobis’ Distance

first, I think of Eculid distance. Eculid distance is following form.
\[d(x,y) = \sqrt{<x^T,y>}\]
The eculid distance regard distance between \(x\) and \(y\) as same if x and y exists over same circle.
enter image description here
This thinking has reason that data distributed like following.
enter image description here
but ,if data distributed like ellipse, it is not good at to use Euclid distance.
enter image description here
Because I want to regard distance between X and Y as same.
Mahalanobis’ Distance is regard distance between X and Y as same if X and Y have existed over the same ellipse.
enter image description here
Distance is always used Machine Learning. Machine Learning use Eculid distance, but We get interesting result by using Mahalanobis’ Distance.
Labels:

コメント

コメントを投稿

このブログの人気の投稿

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で他は０であるので、 $$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}|| + ...
コメントを投稿
続きを読む

ダイクストラ法

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

カーネル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$としま...
コメントを投稿
続きを読む