K近傍法（k-NN）は、分類と回帰の両方に使用されるノンパラメトリックな教師あり学習アルゴリズムである。分類では、新しいデータ点は、距離メトリックによって決定される特徴空間内のk個の最近傍点の中で最も一般的なクラスに割り当てられる。回帰では、出力はそれらの近傍点の値の平均（または加重平均）である。このアルゴリズムはインスタンスベースであり、トレーニングデータセット全体を保存し、予測が必要なときにのみ計算を実行し、すべての一般化をクエリ時まで延期する。
この手法は1951年にEvelyn FixとJoseph Hodgesによって初めて開発され、後にThomas Coverによって拡張された。これは最も単純な機械学習アルゴリズムの1つであるが、特に決定境界が不規則な場合に、多くの領域で競争力のある精度を達成できる。その性能は、kの選択、距離メトリック、および特徴量のスケーリングに大きく依存する。
歴史的発展
k-NNの起源は1951年に遡り、米国空軍航空医学学校で働いていたEvelyn FixとJoseph Hodgesが、最近傍点に基づくノンパラメトリック分類法を導入した。彼らの研究は、特定の統計的分布を仮定せずに観測を分類する必要性によって動機付けられた。1967年、Thomas CoverとPeter Hartは、誤り率がベイズ最適分類器と比較してどの程度であるかを含む、アルゴリズムの特性を形式化した画期的な論文を発表した。これにより、k-NNはパターン認識における理論的に基づいたアプローチとして確立された。このアルゴリズムは、1960年代から1970年代にかけてコンピューティングの台頭とともに人気を博し、トレーニング時間は最小限で済むが、大量のストレージを必要とした。後の発展、例えば加重投票や距離メトリック学習の導入は、その限界のいくつかに対処した。
アルゴリズム概要
k-NN分類では、入力はラベル付きサンプルのトレーニングセットで構成され、各サンプルは多次元空間内の特徴ベクトルとして表される。アルゴリズムはこれらのベクトルとそのラベルを保存する。クエリ点が提示されると、クエリからすべてのトレーニング点までの距離を計算し、最も近いk個を選択し、それらの間で最も頻繁に現れるクラスを割り当てる。k=1の場合、クエリは単にその最近傍点のクラスに割り当てられる。kの選択は重要であり、小さなkは高い分散とノイズへの感度につながる可能性があり、大きなkは決定境界を過度に平滑化し、他のクラスの点を含む可能性がある。
回帰では、出力はk個の最近傍点のターゲット値の平均である。これは最近傍平滑化として知られている。k=1の場合、予測値が最も近いトレーニング点の値と正確に一致する最近傍補間になる。加重バリアントは、より近い近傍点に高い影響を与え、多くの場合、距離の逆数（1/d）に比例する重みを使用する。
距離メトリックと特徴量スケーリング
距離メトリックの選択は重要である。連続特徴量には、ユークリッド距離が最も一般的である。テキスト分類などの離散特徴量には、ハミング距離またはオーバーラップメトリックが使用される。遺伝子発現解析などの専門分野では、相関係数（ピアソン、スピアマン）が使用されてきた。このアルゴリズムの距離への依存は、異なる単位やスケールを持つ特徴量が計算を支配する可能性があることを意味する。したがって、各特徴量を共通のスケール（例：zスコアまたは最小最大スケーリング）に正規化することは、等しい寄与を確保するために不可欠である。この前処理ステップは、精度を大幅に向上させることができる。
統計的特性
統計的観点から、k-NNは基礎となるデータ分布の関数形式を仮定しないため、ノンパラメトリック法である。トレーニングデータはペア（X_i, Y_i）であると想定され、X_iは特徴ベクトル、Y_iはクラスラベルである。特定のクエリ点xに対して、トレーニング点はxへの距離によって並べ替えられる。アルゴリズムの誤り率は、kがnとともに適切に成長し、k/nがゼロに近づく場合、サンプルサイズが増加するにつれてベイズ誤り率に収束する。CoverとHartによって確立されたこの特性は、k-NNを漸近的に最適にする。しかし、有限サンプルでは、アルゴリズムは次元の呪いに悩まされる。特徴量の数が増えると、空間の体積は指数関数的に成長し、点はまばらになり、距離の測定が意味をなさなくなる。
利点と欠点
k-NNの主な利点は、その単純さとトレーニングフェーズがないことである。新しいデータ点を追加することで簡単に更新できる。また、多クラス問題に効果的であり、複雑な決定境界を捉えることができる。しかし、顕著な欠点もある。予測時間は、すべてのトレーニング点までの距離を計算する必要があるため遅く、最適化（例：KDツリーやボールツリーの使用）なしでは大規模データセットには実用的でない。無関係な特徴量やノイズの多いデータに敏感である。また、アルゴリズムはデータの局所構造に敏感であり、外れ値や不均衡なクラス分布が結果を歪める可能性がある。歪んだ分布では、多数派クラスがk個の近傍点に現れる可能性が高いため、支配的になる。逆距離による重み付けや抽象化手法を使用することで、これを軽減できる。
バリアントと拡張
いくつかのバリアントがk-NNの限界に対処している。加重k-NNは、距離に基づいて近傍点に重みを割り当て、より近い点がより多くの影響を持つようにする。大マージン最近傍法や近傍成分分析などの距離メトリック学習手法は、精度を向上させるためにカスタム距離メトリックを学習する。編集k-NNは、ノイズの多いまたは誤分類されたトレーニング点を削除して一般化を改善する。凝縮k-NNは、分類に不可欠な点のみを保持することでトレーニングセットサイズを削減する。局所適応k-NNは、クエリ点の周囲の密度に基づいてkを調整する。これらのバリアントは、Machine learningやArtificial intelligenceなどの分野で性能を向上させるために適用されてきた。
応用
k-NNアルゴリズムはさまざまな領域で使用されている。パターン認識では、画像分類や手書き文字認識に適用される。医学では、患者の特徴に基づく診断に使用される。金融では、信用スコアリングや不正検出に役立つ。レコメンデーションシステムでは、類似したユーザーやアイテムを見つける。バイオインフォマティクスでは、遺伝子発現データを分類する。その単純さから、Neural networkやDeep learningなどのより複雑なモデルを比較するための一般的なベースラインとなっている。
他の手法との関係
k-NNはインスタンスベース学習の一種であり、トレーニング中に明示的なモデルを構築するNeural networkやSupport Vector Machineなどのモデルベースのアプローチとは異なる。また、ノンパラメトリック密度推定とも関連している。Machine learningのより広い文脈では、k-NNはしばしばベンチマークとして使用される。これは、大規模システムで使用される局所性鋭敏型ハッシュや近似最近傍探索の開発に影響を与えた。Deep learningなどの現代の手法が多くのタスクでk-NNを凌駕しているが、k-NNは小規模データセットや解釈可能な予測にとって依然として価値がある。
実用的な考慮事項
k-NNを実装する際には、いくつかの実用的な問題が生じる。kの値は通常、交差検証によって選択される。二値分類での同点を避けるために、kの奇数値がよく使用される。特徴量のスケーリングは不可欠である。KDツリーなどの効率的なデータ構造は最近傍探索を加速できるが、高次元では性能が低下する。非常に大規模なデータセットでは、近似手法が必要である。アルゴリズムのメモリ使用量はトレーニングセットサイズに比例し、これが制限になる可能性がある。現代のアプリケーションでは、k-NNは他のアルゴリズムと組み合わせられることがあり、例えばNeural networkから学習された埋め込みの上で最終分類器として使用される。