K_DM Book
用語集
対象者 標準
対象者別の入口 →

対象者の設定はこのブラウザの中にだけ保存されます。

言語 JA

k近傍法 (k-NN)

入門

02.2.7

k近傍法 (k-NN)

最終更新 2020-04-22 読了時間 4 分
まとめ
k近傍法(k-NN)は、予測したい点から距離が近い \(k\) 個の訓練サンプルを探し、その多数決でラベルを決める分類手法です。学習時には係数を 1 つも計算せず、訓練データをそのまま覚えておくだけなので「怠惰学習(lazy learning)」と呼ばれます。決める値は近傍数 \(k\) と票の重み付け(weights="uniform" か "distance")の 2 つだけで、境界は点の並びに沿った曲線になります。読み終えると、KNeighborsClassifier の k を検証精度で選び、StandardScaler を省くと距離がどう歪むかを説明できるようになります。

直感 #

新入生の部活を当てるゲームを考えます。手がかりは握力と 50 m 走のタイムで、先輩 600 人の記録と所属は分かっています。いちばん記録が似ている先輩 5 人を探し、5 人のうち 3 人が運動部ならこの新入生も運動部と答える。これが \(k = 5\) の k-NN です。「近くのサンプルは同じラベルを持つ」という仮定だけで動くので、学習の段階では何も計算しません。新しい点が来るたびに全訓練データとの距離を測り、近い順に \(k\) 個を選んで票を数えます。weights="distance" を指定すると、近い先輩の票ほど重くなります。

何が起きているか(ステップで見る) #

コードを読む前に、この手法が図の上で何をしているかを追ってみましょう。「再生」を押すか、スライダーを動かすと 1 手順ずつ進みます。

見るポイント:k を変えると同じ点の予測が変わる。k が小さいと近くの 1 点に振り回され、大きいと多数派に流される。

式で書くと何を数えているか #

多数決を式にすると「票数が最大のクラスを選ぶ」だけです。テスト点 \(\mathbf{x}\) に対して \(\mathcal{N}_k(\mathbf{x})\) を訓練データのうち距離が近い \(k\) 個の集合とすると、クラス \(c\) に対する票数は

$$ v_c = \sum_{i \in \mathcal{N}_k(\mathbf{x})} w_i \,\mathbb{1}(y_i = c) $$

で表されます。ここで \(w_i\) は各サンプルの重みで、weights="uniform" なら全員 1、weights="distance" なら距離の逆数です。最も票の多いクラスが予測ラベルとなります。図の上では、\(\mathcal{N}_k(\mathbf{x})\) は「テスト点を中心にちょうど \(k\) 個が入る円」、\(v_c\) はその円の中の色の数です。

Pythonで k を選んで決定領域を描く #

次のコードは make_blobs で 3 クラス 600 点を作り、\(k = 1, 3, 5, 7, 11\) を 30 % の検証データで比べて、最も検証精度が高かった \(k\) の決定領域を描きます。背景の色は「その場所に新しい点が落ちたら何クラスと答えるか」です。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from __future__ import annotations

import matplotlib.pyplot as plt
import numpy as np
from matplotlib.colors import ListedColormap
from sklearn.datasets import make_blobs
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

def run_knn_demo(
    n_samples: int = 600,
    random_state: int = 7,
    weights: str = "distance",
    k_values: tuple[int, ...] = (1, 3, 5, 7, 11),
    validation_ratio: float = 0.3,
    title: str = "k-NN の判別領域",
    xlabel: str = "特徴量1",
    ylabel: str = "特徴量2",
    class_label_prefix: str = "クラス",
) -> dict[str, object]:
    """Evaluate k-NN for several neighbour counts and plot decision regions.

    Args:
        n_samples: Number of synthetic samples to draw.
        random_state: Seed for reproducible sampling.
        weights: Weighting scheme handed to KNeighborsClassifier.
        k_values: Candidate neighbour counts to evaluate.
        validation_ratio: Fraction of the data reserved for validation.
        title: Title for the generated figure.
        xlabel: Label for the x-axis.
        ylabel: Label for the y-axis.
        class_label_prefix: Prefix used when labelling the classes.

    Returns:
        Dictionary with validation scores per k and the best-performing k.
    """
    X, y = make_blobs(
        n_samples=n_samples,
        centers=3,
        cluster_std=[1.1, 1.0, 1.2],
        random_state=random_state,
    )

    rng = np.random.default_rng(random_state)
    indices = rng.permutation(len(X))
    split = int(len(X) * (1.0 - validation_ratio))
    train_idx, valid_idx = indices[:split], indices[split:]
    X_train, X_valid = X[train_idx], X[valid_idx]
    y_train, y_valid = y[train_idx], y[valid_idx]

    scores: dict[int, float] = {}
    for k in k_values:
        model = make_pipeline(
            StandardScaler(),
            KNeighborsClassifier(n_neighbors=k, weights=weights),
        )
        model.fit(X_train, y_train)
        scores[k] = float(model.score(X_valid, y_valid))

    best_k = max(scores, key=scores.get)
    best_model = make_pipeline(
        StandardScaler(),
        KNeighborsClassifier(n_neighbors=best_k, weights=weights),
    )
    best_model.fit(X, y)

    xx, yy = np.meshgrid(
        np.linspace(X[:, 0].min() - 1.5, X[:, 0].max() + 1.5, 300),
        np.linspace(X[:, 1].min() - 1.5, X[:, 1].max() + 1.5, 300),
    )
    grid = np.column_stack([xx.ravel(), yy.ravel()])
    predictions = best_model.predict(grid).reshape(xx.shape)

    unique_classes = np.unique(y)
    levels = np.arange(unique_classes.min(), unique_classes.max() + 2) - 0.5
    cmap = ListedColormap(["#fee0d2", "#deebf7", "#c7e9c0"])

    fig, ax = plt.subplots(figsize=(7, 5.5))
    contour = ax.contourf(xx, yy, predictions, levels=levels, cmap=cmap, alpha=0.85)
    scatter = ax.scatter(
        X[:, 0],
        X[:, 1],
        c=y,
        cmap="Set1",
        edgecolor="#1f2937",
        linewidth=0.6,
    )
    ax.set_title(f"{title} (k={best_k}, weights={weights})")
    ax.set_xlabel(xlabel)
    ax.set_ylabel(ylabel)
    ax.set_xlim(xx.min(), xx.max())
    ax.set_ylim(yy.min(), yy.max())
    ax.grid(alpha=0.15)

    legend = ax.legend(
        handles=scatter.legend_elements()[0],
        labels=[f"{class_label_prefix} {cls}" for cls in unique_classes],
        loc="upper right",
        frameon=True,
    )
    legend.get_frame().set_alpha(0.9)
    fig.colorbar(contour, ax=ax, label="予測クラス")
    fig.tight_layout()
    plt.show()

    return {"scores": scores, "best_k": int(best_k), "validation_accuracy": scores[best_k]}

metrics = run_knn_demo(
    title="k-NN の判別領域",
    xlabel="特徴量1",
    ylabel="特徴量2",
    class_label_prefix="クラス",
)
print(f"最良の k: {metrics['best_k']}")
print(f"検証精度 (最良の k): {metrics['validation_accuracy']:.3f}")
for candidate_k, score in metrics["scores"].items():
    print(f"k={candidate_k}: 検証精度={score:.3f}")

k-NNの判別領域

実行結果の読み方 #

タイトルに表示される \(k\) が、5 通りの候補のうち検証精度が最も高かった値です。print される k=1 の検証精度が他より低ければ、1 点に振り回される過学習が起きている証拠です。背景の 3 色の境目は直線ではなく、点の並びに沿って曲がっています。これは k-NN が「境界の式」を持たず、場所ごとに多数決をやり直しているからです。

k の値と決定境界 #

k の値を変えると決定境界がどう変化するか、リアルタイムで確認できます。

k-NNは全訓練データを保持するため、データが大きいと推論が遅くなります。また、高次元データでは距離の差が縮まり識別力が低下する「次元の呪い」が発生します。特徴選択やPCAで次元を減らしてから適用してください。

weights="distance"を指定すると、近い点ほど強い影響を持つ重み付き投票になり、境界付近の精度が改善されます。\(k\)は奇数に設定すると多数決で同票になるリスクを減らせます。

使いどころと落とし穴 #

k-NN が向くのは、特徴量が 2〜10 個程度で、クラスの境界が曲がっているデータです。苦手なのは特徴量が数百を超える高次元データで、どの点との距離も似た値になり \(k\) 個の近傍がほぼ無作為になります。この場合は PCA で 10〜50 次元に落としてから適用します。間違えやすい設定は StandardScaler の省略です。年収(単位 万円)と年齢(単位 歳)をそのまま渡すと、距離はほぼ年収の列だけで決まり、年齢の差は 1 万円の差にも負けます。訓練データが 100 万点を超えて予測が遅いなら、algorithm="kd_tree" か "ball_tree" を試すか、ロジスティック回帰 のように学習時に式を作る手法に切り替えます。

まとめ #

k-NN は「距離が近い \(k\) 個の多数決」だけで分類する手法で、学習時に係数を求めないぶん予測時に全訓練データとの距離計算が走ります。\(k\) は検証データの精度で選び、\(k = 1\) は過学習、\(k\) が大きすぎると少数クラスが多数決で消えます。StandardScaler で各特徴量を平均 0・分散 1 に揃えないと、スケールの大きい列だけで距離が決まるので、パイプラインに必ず入れます。高次元では「次元の呪い」で近傍が意味を失うため、次元削減か別の手法を検討してください。

参考文献 #

  • Cover, T. M., & Hart, P. E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21 E7.
  • Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning. Springer.