オムライスの備忘録

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

トップ > データサイエンス > 【機械学習】k 最近傍法 / kNN 法 / k Nearest Neighbor Method

【機械学習】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

分枝限定法

近似近傍探索

画像処理への応用

参考