k近傍法と距離:近くのデータに聞く

この章で学ぶこと:いろいろな「分け方」

第5章から第7章までは、ロジスティック回帰、ニューラルネットワーク、CNNと、「重みを学習して、点数を計算する」モデルを学んできました。機械学習には、これとは違う考え方のモデルもたくさんあります。この章では、次の手法を、「どんな考え方で分けるのか」「どんなデータに向くのか」 を比べながら学びます。

• k近傍法: 近くのデータに聞く(このレッスン)
• サポートベクターマシン: 一番太い道を通す
• アンサンブル学習: たくさんのモデルで多数決をとる
• 主成分分析: データを少ない数の特徴量にまとめる(そのために、行列の見方を学ぶ)
• クラスタリング: 正解なしで、似たもの同士をまとめる

k近傍法:近くのデータに多数決で聞く

新しいデータがどちらのグループか分からないとき、「近くにあるデータの多くが属しているグループ」だと考えるのは自然です。この考え方をそのまま使うのが k近傍法(k-nearest neighbors、k-NN)です。

1. 新しいデータと、訓練データのすべての点との 距離 を測る
2. 距離が近い順に $k$ 個の点を選ぶ($k$ は自分で決める数)
3. その $k$ 個の多数決で、新しいデータのグループを決める

この図で $k = 5$ とすると、新しいデータ(★)に近い5個の点は、グループBが4個、グループAが1個です。多数決で、新しいデータは グループB と判定します。

k近傍法には、「学習」の段階がほとんどありません。訓練データを覚えておくだけで、予測のたびに全部の点との距離を計算します。このため、データが多いと予測に時間がかかります。

距離の測り方

2つの点 $(1, 2)$ と $(4, 6)$ の距離を考えます。横に3、縦に4離れています。

• ユークリッド距離(まっすぐ測る): 中学3年で習う三平方の定理で、$\sqrt{3^2 + 4^2} = \sqrt{25} = 5$
• マンハッタン距離(碁盤の目の道を歩く): 横と縦の差を足して、$3 + 4 = 7$

特徴量が3個以上あっても、同じように計算できます。ユークリッド距離なら、特徴量ごとの差を2乗して全部足し、平方根をとります。

scikit-learn の k近傍法は、ふつうユークリッド距離を使います(metric="manhattan" で、マンハッタン距離にもできます)。

標準化・k の選び方・次元の呪い

実験:ワインのデータで、標準化の有無を比べる

イタリアの同じ地域で、3種類のブドウの品種から造られたワイン178本について、アルコール度数・色の濃さなど13個の成分を測ったデータを使います。成分から、どの品種のワインかを当てます(テストデータは3割の54本)。

出典: Aeberhard, S. & Forina, M. (1992). Wine [Dataset]. UCI Machine Learning Repository. https://doi.org/10.24432/C5PC7J ライセンス: CC BY 4.0

標準化しないと、正解率は0.7前後にとどまりました。原因は、成分によって 値の大きさがまったく違う ことです。「プロリン」(アミノ酸の一種)という成分は、ワインによって278〜1680と大きくばらつきます(標準偏差314)。一方、「色合い」は0.48〜1.71の範囲で、標準偏差は0.228しかありません。

距離は差の2乗の合計なので、プロリンの差(例えば100)に比べて、色合いの差(例えば0.5)はほとんど効きません。距離が、値の大きい特徴量だけで決まってしまう のです。実際、プロリンだけを使った k近傍法でも、0.611の正解率になりました。第8章で学んだ標準化(平均0、標準偏差1にそろえる)をすると、13個の成分が同じ重さで距離に効くようになり、正解率は0.96以上になりました。

k の選び方

手書き数字のデータ(テストデータ3割)で、k を変えました。

• $k = 1$ は、一番近い1点だけに従うので、訓練データでは必ず正解します(自分自身が一番近い)。たまたま近くにある、ノイズのような点の影響を受けやすくなります
• $k$ を大きくすると、遠くの点まで多数決に加わり、境界がなめらかになりますが、大きすぎると細かい違いを見分けられなくなります

このデータでは $k = 1$ が一番よい結果でしたが、いつもそうとは限りません(ワインでは、標準化ありの $k = 1$ が1.000、$k = 15$ が0.981)。第8章と同じく、交差検証で選びます。

次元の呪い:特徴量が多すぎると、「近い」が意味を失う

0〜1の範囲にでたらめに散らばる点を500個作り、ある1点からの距離を測りました。一番近い点と一番遠い点の距離の比は、次のようになりました。

1000次元では、一番近い点でも、一番遠い点の0.9倍の距離にあります。どの点も同じくらい遠く なってしまい、「近くの点に聞く」考え方が成り立たなくなります。

これは、次元が増えると、空間が急に広くなるためです。1辺の長さ0.2の範囲(中心から±0.1)に入る点の割合は、1次元では約2割ですが、2次元で約4%、3次元で約0.8%、10次元では1万分の1以下になります。同じ数のデータでは、空間がすかすかになってしまうのです。

このように、特徴量が多いと距離やデータの密度が役に立たなくなる現象を 次元の呪い と呼びます。対策として、レッスン5の主成分分析などで特徴量の数を減らします。

Pythonで k近傍法を使う、よくある誤解と振り返り

from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

wine = load_wine()
X_train, X_test, y_train, y_test = train_test_split(
    wine.data, wine.target, test_size=0.3, random_state=0, stratify=wine.target)

model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5))
model.fit(X_train, y_train)            # 標準化の平均・標準偏差を求め、訓練データを覚える
print(model.score(X_test, y_test))     # → 0.963

• n_neighbors が $k$ です
• stratify=wine.target は、訓練データとテストデータで、3つの品種の割合がそろうように分ける指定です
• 標準化と k近傍法を make_pipeline でまとめると、第9章で学んだとおり、標準化の平均と標準偏差が訓練データだけから求められます(データリークを防げます)

NumPy で距離を計算する

import numpy as np

a = np.array([1, 2])
b = np.array([4, 6])
print(np.sqrt(((a - b) ** 2).sum()))   # ユークリッド距離 → 5.0
print(np.abs(a - b).sum())             # マンハッタン距離 → 7

よくある誤解

• 「k近傍法は、学習に時間がかかる」: 学習は訓練データを覚えるだけで、一瞬です。時間がかかるのは 予測 のほうで、すべての訓練データとの距離を計算します
• 「特徴量は、そのままの値で距離を測ればよい」: 値の大きい特徴量だけで距離が決まってしまいます。標準化してから使います
• 「特徴量は多いほど、よく見分けられる」: 次元の呪いにより、特徴量が多すぎると、どの点も同じくらい遠くなり、「近さ」が役に立たなくなります

振り返り

• k近傍法は、近い $k$ 個の訓練データの多数決で予測する。距離はユークリッド距離(三平方の定理)やマンハッタン距離で測る
• 値の大きさがそろっていない特徴量は、標準化してから使う。$k$ は交差検証で選ぶ
• 次元が増えると空間がすかすかになり、距離の差がなくなる(次元の呪い)