「似たものは似た振る舞いをする」——k近傍法（k-Nearest Neighbors, k-NN）はこの直感をそのままアルゴリズムにしたものです。新しいデータ点を分類するとき、訓練データの中から最も近い $k$ 個の点を見つけ、その多数決で予測します。
k-NNは機械学習で最もシンプルなアルゴリズムの一つです。モデルの「訓練」は訓練データを記憶するだけで、パラメータ推定は行いません。このため怠惰学習（lazy learning）やインスタンスベース学習と呼ばれます。
しかしこの単純さの裏には、距離関数の選択、$k$ の決め方、そして高次元での振る舞い（次元の呪い）という深い課題が隠れています。
k-NNを理解すると、以下のような場面で活用できます。
- 推薦システム: 類似ユーザーや類似アイテムの発見
- 欠損値補完: 近傍のデータから欠損値を推定
- ベースラインモデル: 他のモデルとの性能比較の基準
- 非パラメトリック回帰: 任意の関数形を仮定しない柔軟な回帰
本記事の内容
- k-NNの基本アルゴリズム
- 距離関数の選択（ユークリッド、マンハッタン、ミンコフスキー）
- $k$ の選び方とバイアス-バリアンストレードオフ
- 次元の呪いと対策
- Pythonでのスクラッチ実装と可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 特徴量スケーリングの理論 — k-NNには必須の前処理
- 評価指標の全体像 — 分類の評価
k-NNの基本アルゴリズム
分類のアルゴリズム
- 新しいデータ点 $\bm{x}^*$ に対して、全ての訓練データとの距離を計算
- 距離が小さい順に $k$ 個の訓練データを選択（k近傍）
- $k$ 個の近傍のクラスラベルの多数決で $\bm{x}^*$ のクラスを予測
$$ \begin{equation} \hat{y} = \arg\max_c \sum_{i \in N_k(\bm{x}^*)} \mathbb{1}[y_i = c] \end{equation} $$
$N_k(\bm{x}^*)$ は $\bm{x}^*$ の $k$ 近傍の集合です。
距離関数
距離関数の選択はk-NNの性能に大きく影響します。
ユークリッド距離（$p = 2$）: $d(\bm{x}, \bm{x}’) = \sqrt{\sum_j (x_j – x_j’)^2}$
マンハッタン距離（$p = 1$）: $d(\bm{x}, \bm{x}’) = \sum_j |x_j – x_j’|$
ミンコフスキー距離: $d(\bm{x}, \bm{x}’) = \left(\sum_j |x_j – x_j’|^p\right)^{1/p}$
$k$ の選び方
$k$ の値はバイアス-バリアンストレードオフを制御します。
- $k = 1$: バイアス最小（最近傍の値をそのまま使う）、バリアンス最大（ノイズに敏感）
- $k$ が大きい: バイアス増大（遠くの点の影響を受ける）、バリアンス減少（平均化の効果）
次元の呪い
高次元では「近傍」の概念が機能しなくなります。$d$ 次元の単位超立方体で最近傍をカバーするのに必要な体積の割合は、$k/n$ です。辺の長さ $l$ の超立方体でカバーされる体積は $l^d$ なので
$$ l = \left(\frac{k}{n}\right)^{1/d} $$
$d = 100$、$k/n = 0.01$ のとき、$l = 0.01^{1/100} = 0.955$。つまり各次元の95.5%をカバーする必要があり、「近傍」がほぼ全データを含んでしまいます。
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
np.random.seed(42)
X, y = make_moons(n_samples=300, noise=0.3, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
fig, axes = plt.subplots(1, 3, figsize=(16, 5))
# (a-b) 異なるkでの決定境界
for ax, k in zip(axes[:2], [1, 15]):
model = KNeighborsClassifier(n_neighbors=k).fit(X_scaled, y)
x_min, x_max = X_scaled[:, 0].min() - 0.5, X_scaled[:, 0].max() + 0.5
y_min, y_max = X_scaled[:, 1].min() - 0.5, X_scaled[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
np.linspace(y_min, y_max, 200))
Z = model.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
ax.contourf(xx, yy, Z, alpha=0.3, cmap="RdBu")
ax.scatter(X_scaled[y==0, 0], X_scaled[y==0, 1], c="blue", s=20, alpha=0.6)
ax.scatter(X_scaled[y==1, 0], X_scaled[y==1, 1], c="red", s=20, alpha=0.6)
cv = cross_val_score(model, X_scaled, y, cv=5).mean()
ax.set_title(f"k = {k} (CV Acc = {cv:.3f})", fontsize=13)
ax.set_xlabel("$x_1$", fontsize=12)
ax.set_ylabel("$x_2$", fontsize=12)
ax.grid(True, alpha=0.3)
# (c) kの選択（交差検証）
ax = axes[2]
k_range = list(range(1, 31))
cv_scores = []
for k in k_range:
model = KNeighborsClassifier(n_neighbors=k)
scores = cross_val_score(model, X_scaled, y, cv=5)
cv_scores.append(scores.mean())
ax.plot(k_range, cv_scores, "b-o", linewidth=2, markersize=4)
best_k = k_range[np.argmax(cv_scores)]
ax.axvline(best_k, color="red", linestyle="--", linewidth=2,
label=f"Best k = {best_k}")
ax.set_xlabel("k", fontsize=12)
ax.set_ylabel("CV Accuracy", fontsize=12)
ax.set_title("k Selection via Cross-Validation", fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("knn_algorithm.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、k-NNの特性が読み取れます。
-
左図（k=1）: 非常に複雑な決定境界で、個々のデータ点の周りに細かい領域が形成されています。ノイズにまで過剰に反応しており、過学習の傾向があります
-
中央図（k=15）: 決定境界が滑らかになり、ノイズの影響が抑えられています。三日月形のパターンをよく捉えつつ、過度に複雑にならない良いバランスです
-
右図（k選択）: 交差検証による最適な $k$ の選択を示しています。$k$ が小さすぎると過学習、大きすぎると未学習になるU字型の傾向が見られます
まとめ
本記事では、k-NNの理論と実装について解説しました。
- k-NNは最も近い $k$ 個の訓練データの多数決で分類するノンパラメトリック手法
- 距離関数の選択が性能を左右し、特徴量スケーリングが必須
- $k$ はバイアス-バリアンストレードオフを制御し、交差検証で選択する
- 次元の呪いにより高次元では性能が劣化するため、次元削減との組み合わせが有効
次のステップとして、以下の記事も参考にしてください。
- 特徴量スケーリングの理論 — k-NNの前処理
- 次元削減の全体像 — 次元の呪いへの対策
- サポートベクターマシンの理論 — 別の距離ベース手法