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

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

k近傍法

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

サンプル間の距離計算を直接利用する手法であるため, 性能が特徴量の設計にとても敏感である.

近似最近傍探索

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

kd-tree

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

低次元特徴量空間での最近傍探索では、計算量を抑える効果が高くなる.

距離計算

コサイン距離

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

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

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

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

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

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

マハラノビス距離

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

(x−y)⊤Σ−1(x−y)\displaystyle \sqrt{(\bm{x} - \bm{y})^{\top} \Sigma^{-1} (\bm{x} - \bm{y})}

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

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

参考文献

関連記事