k近傍法 (k-NN)（高校生向け）

こんな場面を想像してみよう #

新入生が「どの部活に入りそうか」を当てるゲームをします。手がかりは体力テストの 握力 と 50 m 走のタイム の 2 つ。先輩たち 600 人の記録と所属（運動部・文化部・帰宅部）は分かっています。

あなたならどう当てますか。たぶん「この新入生と記録がいちばん似ている先輩」を探し、「その先輩が運動部なら、この子も運動部だろう」と考えるはずです。1 人だけだと偶然かもしれないので、似ている先輩を 5 人 選んで多数決にする。これが k近傍法（k = 5）です。

上の図は、2 つの特徴量で 3 つのクラスを分けた例です。丸い点が覚えているデータ、背景のうすい色が「この場所に新しい点が来たら何色と答えるか」です。直線ではなく、点の並びに合わせた曲がった境界が 3 色の間にできています。

仕組み：距離を測って、近い順に並べて、多数決 #

新しい点が 1 つ来たとき、k近傍法がやることは 4 つだけです。まず新しい点を図に打ちます。この時点ではまだ色はついていません。次に覚えているすべての点との距離を 1 つずつ測ります。2 点 \((x_1, y_1)\), \((x_2, y_2)\) の距離は \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\) で、図では新しい点から各点へ線を引いて、その長さを比べるイメージです。そのうえで近い順に k 個（ここでは 5 個）選びます。図では新しい点を中心に、ちょうど 5 個が入る円を描くことに当たります。最後に 5 個の色を数えて多数決をとり、いちばん多い色を答えにします。同数のときは「近い点の票を重くする」などで決めます。

背景の色分けは、図のすべての場所でこの 4 ステップをやった結果です。境界線とは「多数決の結果が入れ替わる場所」のことなので、点の並びに沿ってぐにゃぐにゃになります。

動かして見てみよう #

下の図で「再生」を押すと、説明した手順が 1 つずつ進みます。手順ごとの説明は図の下に出ます。

k を変えると図はどう変わる？ #

k = 1 のときは、いちばん近い 1 点の色をそのまま使います。境界は細かくギザギザになり、1 個だけ別の色の点がまぎれていると、その点のまわりに小さな「島」ができます。上の図はこの状態です。k を大きくすると多数決に参加する点が増えるので、1 個の例外に引きずられなくなり、境界がなめらかになります。ただし k = 50 のように大きくしすぎると、数の少ないクラスが多数決で消えてしまいます。

つまり k は「細かく合わせる」と「大まかに合わせる」のバランスを決めるつまみです。情報IIで学ぶ過学習（覚えたデータにだけ合いすぎること）は、k が小さすぎるときに起こります。

電卓感覚で計算してみる #

先輩 5 人の記録（握力 kgf、50 m 走 秒、所属）から、新入生（握力 26、タイム 8.0）の所属を k = 3 で当てる計算です。

1
2
3
4
5
6
7
8
9

import math
seniors = [(30, 7.5, "sports"), (28, 7.8, "sports"), (22, 8.6, "culture"),
           (20, 8.9, "culture"), (25, 8.2, "home")]   # (grip, 50m time, club)
new = (26, 8.0)
dist = sorted((math.hypot(g - new[0], t - new[1]), c) for g, t, c in seniors)
k = 3
votes = [c for _, c in dist[:k]]
print(dist[:k])
print("prediction:", max(set(votes), key=votes.count))

近い 3 人は帰宅部 1 人・運動部 2 人なので、答えは運動部になります。ここで距離を見ると、握力の差（単位 kgf）がタイムの差（単位 秒）よりずっと大きく、距離をほぼ握力だけで決めてしまっています。これが次の注意点です。

気をつけたいこと #

最初の課題は「単位のちがう特徴量を混ぜると距離がゆがむ」ことです。握力 20〜30 とタイム 7〜9 では、握力の差ばかりが効きます。各特徴量を「平均 0、標準偏差 1」にそろえる標準化をしてから距離を測るのが基本です。二つ目は、データが多いと予測が遅いこと。学習で式を作らないぶん、予測のたびに全データとの距離を測るので、先輩が 10 万人いれば 10 万回の計算になります。三つ目は、特徴量が多すぎると「近い」が意味を失うことです。項目が 50 個も 100 個もあると、どの点との距離も似た値になり、多数決が効かなくなります（次元の呪い）。

やってみよう #

まず、方眼紙に赤 6 点・青 6 点を自由に打ち、新しい点を 1 つ置いて、k = 1 と k = 5 で答えがどう変わるか試してみよう。ものさしで距離を測ってもよいし、三平方の定理で \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\) を計算してもよい。次に、「似ている人を探して多数決」で判断している身近な例を 2 つ挙げてみよう（例：おすすめの動画、服のサイズ選び）。最後に、上のコードの握力を「g 単位」（26000 など）に書き換えると、答えはどうなるだろう。単位をそろえないと近い 3 人の顔ぶれがどう変わるかを確かめよう。

つぎに読む #

票の重みづけの式や scikit-learn での実装、k を自動で選ぶ方法は 標準版の k近傍法 で扱っています。境界を「直線 1 本」で引く方法は 高校生向けのロジスティック回帰、確率の掛け算で分ける方法は 高校生向けのナイーブベイズ へ。当たった割合の測り方は 分類の評価指標 へ。