オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

【機械学習】k 最近傍法 / kNN 法 / k Nearest Neighbor Method

Index

k 最近傍法 / kNN 法 / k Nearest Neighbor Method

機械学習アルゴリズムのひとつ.

認識したい入力データとすべての学習データ (鋳型 / Template) との距離計算を行い、
最も近い学習データが属するクラスに識別する方法を最近傍法 / NN法 / Nearest Neighbor Methodという.

最近傍法では、学習データが多ければ、精度のよい認識を行うことができるが、計算時間がかかる.

最も近い 1 つの学習データのクラスに識別する代わりに、
最も近い k 個の学習データ学習データを選び、所属する学習データの数が最も多いクラスに識別する方法を、
k 最近傍法 / kNN 法 / k Nearest Neighbor Method という.

最近傍法

変数定義

 K 個のクラスを  \Omega\ =\ \{C_{1},\ \cdots,\ C_{K} \} i 番目のクラスの学習データ数を  N_{i}、 その集合を  S_{i}\ =\ \{x_{1}^{i},\ \cdots,\ x_{N_{i}}^{i}\} とする.

識別規則

識別規則

 Class\ =\ \left\{
\begin{array}{ll}
arg \displaystyle \min_{i} \{ \min_{j} d(x,\ x_{j}^{i}) \} & \displaystyle \min_{ij} d(x,\ x_{j}^{i}) < t \\
Reject &  \displaystyle \min_{ij} d(x,\ x_{j}^{i}) \geq t
\end{array}
\right.

ボロノイ境界

最近傍法の原理は、入力データに最も近い鋳型 / Template を見つけること.

各鋳型 / Template は、隣接する鋳型と等距離にある境界で囲まれた 支配領域をもち、この支配領域をボロノイ領域という.

また、その境界をボロノイ境界という.

k 最近傍法 / kNN 法 / k Nearest Neighbor Method

最近傍の鋳型 / Template を  k 個とってきて、 それらがもっとも多く所属するクラスに識別する方法を k 最近傍法 / kNN 法 / k Nearest Neighbor Method という.

kNN法とベイズ誤り率

kNN 法の計算量

計算量の計算のための設定

クラスの番号を  i\ =\ 1,\ \cdots,\ K とする.

各クラスのデータの数を同じとし、その番号を  j\ =\ 1,\ \cdots,\ M とする.

また、データの次元を  d とする.



投票型 kNN 法では、入力データ  x が与えられたとき、
すべてのクラスの、すべてのデータ  x_{j}^{(i)} とのユーグリッド距離の 2 乗、つまり

 d^{2}(x,\ x_{j}^{(i)})\ =\ (x\ -\ x_{j}^{(i)})^{T}\ (x\ -\ x_{j}^{(i)})



を計算する必要がある.

計算量の削減

この距離計算に、差ベクトルを求めるための  K\ \times\ M\ \times\ d 回の減算と積和が必要となる.

さらに、距離を昇順にソートする必要があるが、
これはおおよそ  K\ \times\ M\ \times\ \log(KM) のオーダーの比較と置換の処理を必要とする.

kNN 法は、データの次元が大きくなる場合に多くの時間と記憶容量が必要であり、
リアルタイムには向いていない手法であるが、その制約を緩和する試みが行われてきた.

計算量削減のアルゴリズム

誤り削減型 kNN

圧縮型 kNN

分枝限定法

近似近傍探索

画像処理への応用

参考