K近傍法
k近傍法(ケイきんぼうほう、英: k-nearest neighbor algorithm, k-NN)は、入力との類似度が高い上位 k 個の学習データで多数決/平均するアルゴリズムである。
パターン認識(分類・回帰)でよく使われる。最近傍探索問題の一つ。k近傍法は、インスタンスに基づく学習の一種であり、怠惰学習 の一種である。その関数は局所的な近似に過ぎず、全ての計算は分類時まで後回しにされる。また、回帰分析にも使われる。
訓練例は、多次元の特徴空間におけるベクトルである。空間は、訓練例のラベルと位置によって領域に分割されている。空間内のある点には、その k 個の最近傍の訓練例に最も多く付けられているクラスラベル c が割り当てられる。このとき、一般にユークリッド距離が使われる。
アルゴリズムの訓練段階では、訓練例の特徴ベクトルとクラスラベルだけを保持している。実際の分類段階では、クラスが未知である標本の特徴空間におけるベクトルが与えられる。この新たなベクトルと既存のベクトル群との距離を計算し、k 個の最近傍の標本が選択される。新たなベクトルを特定のクラスに分類する方法はいくつかある。最も一般的な手法は、k 個の最近傍のオブジェクトの中で最も一般的なクラスに分類する方法である。この技法による分類の問題点は、全訓練例で個体数が最も多いクラスに分類される可能性が高くなる点である。この対策として、k 個の最近傍のオブジェクトの間で、新たなベクトルとの距離の大小を考慮して(重み付けして)クラスを決定する方法がある。