k近傍法（k-NN）アルゴリズムとは？仕組みと特徴をわかりやすく解説

k近傍法（k-NN）アルゴリズムの概要

k近傍法（k-Nearest Neighbors：k-NN）は、クラスへの所属（Y）と予測変数 X₁、X₂、…、X_n との関係の構造について、何ら前提を置かない分類手法です。

この手法は、線形回帰で仮定されるような線形形式など、特定の関数形におけるパラメータ推定を行わないため、「ノンパラメトリックなアプローチ」と呼ばれます。代わりに、データセット内の予測変数値同士の類似性から情報を引き出して分類を行う点が大きな特徴です。

k-NNの基本的な仕組み

k近傍法の考え方は非常にシンプルです。まず、分類したい新しいデータに類似したレコードを、訓練データセットの中から k 個認識します。次に、これらの類似した（近傍の）レコードを利用して、新しいレコードをクラスに割り当てます。具体的には、近傍レコードの中で最も多く占めるクラス（多数派クラス）へ新規データを分類します。ここで、新規レコードの予測変数の値を X₁、X₂、…、X_n と表します。

距離の測り方：ユークリッド距離

この手法における中心的な課題は、予測変数の値に基づいてデータ間の距離をどのように計算するかという点です。最も広く知られている距離尺度が「ユークリッド距離」です。2つのレコード (X₁, X₂, …, X_n) と (U₁, U₂, …, U_n) の間のユークリッド距離は、次の式で表されます。

$$\mathrm{\sqrt{(X_1-U_1)^2+(X_2-U_2)^2+...+(X_n-U_n)^2}}$$

k-NNアルゴリズムでは、予測対象の各データと訓練セット内の各データとの間で、何度も距離計算を繰り返す必要があります。そのため、計算コストが低いユークリッド距離が、k-NNにおいて最も広く採用されています。

予測変数の標準化が重要な理由

予測変数ごとにスケール（単位や値の範囲）が大きく異なる場合があるため、ほとんどの場合、ユークリッド距離を計算する前に予測変数を標準化しておく必要があります。このとき使用する平均値と標準偏差は訓練データから求めたものを使用し、分類対象となる新規データは標準化の計算には含めません。検証データについても同様に、この計算には含まれない点に注意しましょう。

クラス割り当てのルール

分類対象データと既存レコードとの距離を計算した後は、近傍レコードのクラス情報に基づいて、対象レコードにクラスを割り当てるためのルールが必要になります。

最もシンプルなケースは k = 1 の場合です。この場合は最も近いデータ（最近傍）を探し、新しいデータをその最近傍と同じクラスに分類します。

シンプルなのに強力：1-NNの性能

興味深いことに、たった1つの最近傍を使ってレコードを分類するという直感的でシンプルな発想は、訓練データセットに大量のレコードが存在する場合に、驚くほど強力に機能することが知られています。実際、1-近傍法の誤分類率は、各クラスの確率密度関数を完全に把握できている理想的な状況での誤分類率の2倍を超えないことが、理論的に示されています。