【E資格対策】パターン認識

k近傍法と近似最近傍探索・kd-tree

k近傍法

k近傍法は, 新しいデータが与えられたとき, そのデータから近い任意の $k$ 個のデータの中で, 最も属するデータ数が多いクラスに新しいデータを分類するアルゴリズムである.

近似最近傍探索

最近傍探索では, 次元数やデータ数が大きくなると計算量が膨大になってしまう. そこで, 近傍点との距離の近似解を求めることで計算量を削減した, 近似最近傍探索が用いられることがある. 具体的な手法として, 局所感度ハッシング, kd-tree, Ball-tree などがある.

kd-tree

kd-treeは, 空間内のデータを次元ごとに分割する木構造である. 次元を一つ選び, 閾値で直交するに平面で空間を分割していく. データを分割して管理することで, 最近傍法やk近傍法を用いた探索を高速に行うことができる.

距離計算

コサイン距離

2ベクトル $\bm{x}, \bm{y}$ が与えられたとき, 両者の内積をそれぞれのL2ノルムで割った値 $\dfrac{\bm{x} \cdot \bm{y}}{\|\bm{x}\| \|\bm{y}\|}$ をコサイン類似度と呼び, これは $-1$ から $1$ の値を取る. 自然言語処理において, テキストをベクトル化して類似度を測る場合などで用いられる.

一方, $1$ からコサイン類似度を引いた値 $1 - \dfrac{\bm{x} \cdot \bm{y}}{\|\bm{x}\| \|\bm{y}\|}$ をコサイン距離と呼び, これは $0$ から $2$ の値を取る. コサイン類似度が高いほど, コサイン距離は小さくなる.

Lp距離・ユークリッド距離・マンハッタン距離

Lp距離の定義は次の通り : $\displaystyle \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}}$

$p = 1$ のとき, $\displaystyle \sum_{i=1}^{n} |x_i - y_i|$ はマンハッタン距離と呼ばれる.

$p = 2$ のとき, $\displaystyle \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$ はユークリッド距離と呼ばれる.

マハラノビス距離

マハラノビス距離はデータの相関を考慮した距離で, 2ベクトル $\bm{x}, \bm{y}$ が同じ確率分布に従い, それらの分散共分散行列を $\Sigma$ としたとき, 以下のように定義される :

分散共分散行列を用いることで, ユークリッド距離では考慮されなかったデータ分布の広がりや指向性が反映される.

代表的な利用例として異常検知が挙げられ, これはマハラノビス距離が閾値を超えたデータ点を異常と判断する手法である.

参考文献

• 深層学習教科書 ディープラーニング E資格（エンジニア）精選問題集