k-最近傍法 (k-Nearest Neighbors, k-NN) とは？
k-NNは、分類・回帰に用いられるシンプルな教師あり学習アルゴリズムです。「怠惰学習」とも呼ばれ、明示的なモデル学習フェーズを持ちません。予測時には、新しいデータ点（テスト点）と最も近い \(k\) 個の訓練データ点（近傍点）を探し、それらの情報（クラスラベルや値）に基づいて予測を行います。
アルゴリズムのステップ（分類の場合）
- 距離計算: テスト点と全ての訓練点との距離を計算します。
- 近傍点の選択: 距離が近い順に \(k\) 個の訓練点を選びます（\(k\)はハイパーパラメータ）。
- 多数決: \(k\) 個の近傍点のクラスラベルで最も多数を占めるクラスを、テスト点のクラスとして予測します。
距離指標: ユークリッド距離
ステップ1の距離計算で最も一般的に用いられるのがユークリッド距離です。2点 \(P_1(x_1, y_1)\) と \(P_2(x_2, y_2)\) の間の直線距離を表します。
$ d(P_1, P_2) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$
計算ステップ
テスト点 \(P_{test} = (2, 3)\) と訓練点 \(P_1 = (1, 1)\) の間のユークリッド距離 \(d_1\) を計算します。
$ d_1 = d(P_{test}, P_1) = \sqrt{(1 - 2)^2 + (1 - 3)^2} \\\
= \sqrt{(-1)^2 + (-2)^2} = \sqrt{1 + 4} = \sqrt{5} \\\
\approx 2.23606...$
小数点以下3桁まで求めると、距離は約 2.236 です。
(参考) テスト点と訓練点 \(P_2=(4, 5)\) の距離 \(d_2\):
$ d_2 = d(P_{test}, P_2) = \sqrt{(4 - 2)^2 + (5 - 3)^2} = \sqrt{2^2 + 2^2} = \sqrt{4 + 4} = \sqrt{8} \approx 2.828$
もし \(k=1\) なら、距離がより近い \(P_1\) のクラスが予測結果となります。
重要ポイント：k-NN
- シンプルさ: アルゴリズムが直感的で理解しやすい。
- 非線形性: 複雑な決定境界を表現できる。
- 計算コスト: 予測時に全訓練データとの距離計算が必要で、データ量が多いと遅い。
- \(k\) の選択: \(k\) の値が性能に大きく影響する（小さいと過学習、大きいと過度に平滑化）。
- スケーリング: 特徴量のスケールを揃える（標準化など）ことが重要。
- 距離指標: ユークリッド距離以外（マンハッタン距離、コサイン類似度など）も利用される。