k近傍法

ひとことで言うと

k近傍法（k-nearest neighbors）は、訓練データをほぼそのまま保持し、予測したい点の近くにある $k$ 個のデータから答えを決める方法です。分類なら多数決、回帰なら近傍の目的変数の平均が基本で、学習時に係数や決定境界を推定しません。

なぜ必要か

明確な関数形を仮定しにくく、局所的に複雑な境界を持つデータでも、近い観測の傾向を直接使えます。その代わり、訓練時に軽いことと予測時に重いことが入れ替わります。データを「学習して圧縮する」モデルではなく、訓練サンプルを記憶して検索する非パラメトリックな方法だからです。

$k$ は局所性と安定性のつまみです。小さい $k$ はごく近い点に強く反応するため、細かな境界を表せますが、外れ値やノイズで予測が揺れやすくなります。大きい $k$ は広い範囲を平均するので分散を下げ、ノイズを抑えますが、異なる領域を混ぜて境界をぼかしやすく、バイアスが増えます。したがって固定の正解値を暗記するのではなく、検証データで選びます。

観点	小さい $k$	大きい $k$
近傍の範囲	局所的	広域的
バイアス	低い	高い
バリアンス	高い	低い

仕組み

入力 $\mathbf{x}$ と各訓練点 $\mathbf{x}_i$ の距離を計算し、小さい順に並べて上位 $k$ 点を選びます。分類でクラス $c$ の票数を $V_c$ とすると、予測クラス $\hat{y}$ は次で表せます。

$$\hat{y}=\underset{c}{\operatorname{argmax}}\;V_c,\qquad V_c=\sum_{i\in\mathcal{N}_k(\mathbf{x})}\mathbf{1}(y_i=c)$$

$\mathcal{N}_k(\mathbf{x})$ は入力 $\mathbf{x}$ の $k$ 近傍、$y_i$ は訓練点 $i$ のラベル、$\mathbf{1}$ は条件を満たすとき1になる指示関数です。近い点をより重くする設定では、距離の逆数に比例する重みを使えます。

特徴量の単位が違うと、距離の大きな特徴量が近傍順位を支配します。例えば年収を円、年齢を年のまま入れると、年収の差だけで「近さ」が決まりかねません。平均0・標準偏差1への標準化を訓練データで計算し、同じ変換を予測データにも適用します。距離の定義自体の比較は、距離尺度ノートの範囲です。

次元が増えると、距離の大小が近傍らしい局所差を表しにくくなる問題があります。これは次元の呪いノートへ接続する論点で、ここでは「$k$ を調整しても探索と近傍の信頼性が同時に解決するとは限らない」と押さえます。

試験でどう問われるか

問われ方	正解に寄る条件	引っかけ
学習と予測の構造	学習時は訓練データを保持し、予測時に近傍探索する	学習時に重みを最適化して境界を得る
$k$ の大小	小さいと低バイアス・高バリアンス、大きいと高バイアス・低バリアンス	大きい $k$ ほど局所的な境界が細かくなる
前処理	特徴量を同程度の尺度にそろえる	単位の違いは距離に影響しない
分類の出力	近傍ラベルの多数決。距離重みなら近い点の寄与が大きい	常に最も近い1点だけで決める
計算量の位置	主な探索コストは予測時。全探索ではサンプル数と特徴数に依存	学習が軽いので運用コストも常に軽い

実装で確かめる

標準化してから、予測点ごとに距離を計算し、上位 $k$ 件のラベルを数えます。ここでは分類の最小構造をNumPyだけで確認します。

import numpy as np

X = np.array([[0., 10.], [1., 11.], [0., 12.], [8., 10.], [9., 11.], [8., 12.]])
y = np.array([0, 0, 0, 1, 1, 1])
q = np.array([[7., 11.]])
mean, std = X.mean(axis=0), X.std(axis=0)
Xs, qs = (X - mean) / std, (q - mean) / std
dist = np.linalg.norm(Xs - qs, axis=1)
k = 3
neighbors = np.argsort(dist)[:k]
prediction = np.bincount(y[neighbors]).argmax()
print(prediction)

出力は 1 です。標準化を外すと第一特徴の単位やレンジが順位を決めるため、同じアルゴリズムでも結果が変わり得ます。実ライブラリでは n_neighbors が $k$、weights が一様または距離に応じた重み、algorithm が探索方式に対応します。データが増えるほど、予測要求の待ち時間と近傍インデックスのメモリを設計に含めます。

取り違えやすいもの

手法	k近傍法との切り分け
k-means	近傍法はラベル予測、k-meansはクラスタ中心を更新する教師なし手法
線形分類器	線形分類器はパラメータから境界を表すが、k近傍法は局所データの投票で決める
半径近傍法	半径内の点を使い、点数を固定するk近傍法とは近傍の決め方が違う
最近傍法	$k=1$ の特殊例。ノイズに最も敏感な設定になりやすい

想起チェック

k近傍法は学習時と予測時のどちらに計算を寄せるか

訓練データを保持し、予測時に距離計算と近傍探索を行います。

近傍数を大きくしたとき、バイアスとバリアンスはどう動くか

広い範囲を平均するため、一般にバイアスは増え、バリアンスは下がります。境界は滑らかになります。

標準化を先に検討する理由は何か

特徴量の尺度差が距離と近傍順位を支配するのを防ぐためです。訓練時に得た変換を予測時にも使います。