k近傍法（k-NN）は、分類と回帰に使用されるノンパラメトリックなインスタンスベース学習手法である。どちらの場合も、入力は特徴空間におけるk個の最も近い訓練例で構成される。出力は、k-NNが分類に使用されるか回帰に使用されるかによって異なる。分類では、出力はクラスメンバーシップであり、k個の最近傍間の多数決によって決定される。回帰では、出力はk個の最近傍の値の平均（または加重平均）である。k-NNは遅延学習の一種であり、関数は局所的にのみ近似され、すべての計算は関数評価まで延期される。距離計算に依存するため、このアルゴリズムはデータの局所構造と距離メトリックの選択に敏感である。
このアルゴリズムは、1951年にアメリカ空軍航空医学学校のEvelyn FixとJoseph Hodgesによって、当初はノンパラメトリック分類手法として初めて開発された。その後、1967年にThomas CoverとPeter Hartによって拡張・形式化され、漸近誤差限界が確立された。それ以来、k-NNは機械学習、パターン認識、データマイニングにおける基本的なツールとなり、より複雑なモデルのベースラインとしてよく使用されている。
仕組み
クエリポイントが与えられると、アルゴリズムはすべての訓練例までの距離（通常はユークリッド、マンハッタン、またはミンコフスキー距離）を計算する。次に、距離が最小のk個の訓練例を選択する。分類では、予測ラベルはこれらk個の最近傍の中で最も頻繁に出現するものとなる。回帰では、予測値は最近傍のターゲット値の平均となる。kの選択は重要である。kが小さい場合（例：1）は分散が高くノイズに敏感になり、kが大きい場合は局所的なパターンを平滑化してバイアスが増加する可能性がある。一般的な手法は、交差検証によってkを選択することで、バイナリ分類では同点を避けるために奇数値がよく使用される。
このアルゴリズムは距離メトリックも必要とする。ユークリッド距離は連続特徴の標準であるが、高次元またはカテゴリカルデータでは、ハミング距離やコサイン類似度などの他のメトリックが使用される場合がある。特徴量の範囲が大きいと距離計算を支配するため、特徴スケーリング（正規化や標準化など）が不可欠である。
特性とバリアント
k-NNはノンパラメトリックであり、基礎となるデータ分布について強い仮定を置かない。また、インスタンスベースであり、訓練セット全体を保存し、予測時に直接使用する。これにより、訓練は簡単（基本的にデータを保存するだけ）になるが、予測は計算コストが高く、クエリごとにO(nd)の時間複雑度となる。ここで、nは訓練サンプル数、dは特徴数である。
いくつかのバリアントがこれらの制限に対処している。重み付きk-NNは、より近い近傍に高い影響を与え、多くの場合、逆距離重みを使用する。局所重み付き回帰は、近傍内で線形モデルを適合させる。大規模データセットでは、k-d木、ボール木、局所性鋭敏型ハッシュなどの近似最近傍探索技術が検索コストを削減する。高次元では、距離の判別性が低下するため、次元の呪いがパフォーマンスを低下させる。次元削減や特徴選択がしばしば適用される。
応用
このアルゴリズムは、コンピュータビジョンにおける画像分類、自然言語処理におけるテキスト分類、バイオインフォマティクスにおける遺伝子発現解析などの分野で広く使用されている。類似した好みを持つユーザーやアイテムを見つけるレコメンデーションシステムにも登場する。金融では、信用スコアリングや不正検出に使用される。その単純さと解釈可能性により、探索的解析の最初の選択肢や、ニューラルネットワークなどのより複雑なモデルに対するベンチマークとして一般的である。
強みと限界
k-NNの主な強みは、その単純さ、実装の容易さ、および低～中次元の小規模から中規模のデータセットでの有効性である。訓練フェーズが不要なため、インクリメンタル学習に適している。しかし、その限界には、高いメモリ使用量（すべての訓練データを保存する）、遅い予測時間、無関係な特徴やノイズへの感度、高次元空間でのパフォーマンスの低さが含まれる。また、すべての特徴が等しく重要であると仮定するが、これは実際にはほとんど当てはまらない。
他の手法との関係
k-NNは、決定木やサポートベクターマシンなどの他のノンパラメトリック手法としばしば比較される。これは機械学習における基礎的な手法であり、人工知能カリキュラムと並んで頻繁に教えられている。その原理は、合成近傍を生成するデータ拡張技術などのより高度な手法の基盤となっており、訓練例を難易度で順序付けるカリキュラム学習でも使用される。現代の実践では、k-NNはメトリック学習のための深層学習モデルの最終層として使用されることがあり、学習された埋め込みが最近傍探索を使用して比較される。
関連項目
参考文献
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.