k 近傍法

基本の k 近傍法はパラメータ化した決定関数を当てはめません。ラベル付き点を保存し、問い合わせ時に距離を測って並べ、最近傍 k 点の多数決を取ります。重みの最適化はなくても、前処理、距離の選択、索引構築には作業が必要です。

k は整列した表をどこで切るかだけを決めます。同じ問い合わせと距離でも k=1 と k=3 で答えが変わります。小さい k は細部と誤ラベルを拾い、大きい k は孤立ノイズと本物の小集団をともに消し得ます。

データがモデルになる

線形分類器は訓練集合を少数のパラメータへ要約します。kNN は集合自体を保ち、総当たり版の設定は主に保存です。予測時に N 個の d 次元点との距離と並べ替えを支払います。

本課の距離は d=√((p₁−q₁)²+(p₂−q₂)²)。軸が比較可能だという前提があります。メートルをミリメートルにすると値は千倍、平方への寄与は百万倍です。標準化や分野に合う距離を特徴の意味から選び、前処理は学習データで当てはめて評価への漏洩を防ぎます。

KD-tree や ball tree は適したデータで走査を減らしつつ厳密な近傍を返せますが、最悪時や高次元では全走査に近づきます。HNSW、IVF などは近傍を取り逃す可能性と速度を交換します。規模、次元、距離の質、待ち時間を合わせて判断します。

k が変えるもの

k=1 は一番近い一点が決め、誤ラベルもそのまま信じます。k=N は全体の多数クラスをどこでも返します。人数を増やすと孤立ノイズを抑えられる一方、周囲より小さな本物の構造も多数決で負けます。アルゴリズムはノイズと小集団を意味から区別しません。

初期データには A 領域内の誤った B と、B 集団の横の二点の本物の A 前哨があります。k=1 は誤りを信じ、k=9 は前哨を消します。k は保存した点の自己採点ではなく、独立した検証データで選びます。

地図の作り方

保存するのは点と手順であり、境界ではありません。画面は 55×55 格子の中心で距離、整列、切出し、投票を実行して塗ります。セルの辺が厳密な境界ではありません。

k=1 は標本点の Voronoi 分割です。各点が自分に最も近い領域を支配します。本課では矛盾する重複座標がないため、訓練点は自身が唯一の距離ゼロの近傍となり、訓練正解率は 100% です。新しい点の正しさは保証しません。k が増えると小領域が消え、N 付近で全体の多数色へ近づきます。

「二つの島」は線形分類器の凸性制限と比較します。局所投票は同一クラスの凸性や連結性を要求せず、三票なら両島を保てます。十三票では全体の多数に沈みます。形を表現できても、どの k でも保つわけではありません。

ステップごとの例

14 点は A が 8、B が 6。A 六点は上半分、B 五点は右下です。(−1,3) は A の中の誤ラベル B ですが、初めから特別扱いしません。本物の A 前哨は (0,−3)、(1,−4)。問い合わせは q=(−1,2)、初期 k=3 です。

1. 配置、拍 1。 点をラベルで塗り、問い合わせは白抜きにします。重みや学習した境界はありません。
2. 距離、拍 2。 十四本の破線を引き、保存順に距離を並べます。最寄りの誤ラベル点は 1.00、A の (−2,3) と (−2,1) は √2≈1.41、遠い B は 7 を超えます。
3. 整列、拍 3。 Python の (d,y) と同じく距離、次に A→B のラベル順。同距離・同ラベルは元の順を保ちます。
4. 選択と投票、拍 4–5。 三行目の下で切り、B、A、A を採用します。三番目を通る円と票数 A 2、B 1 を表示します。
5. 判定、拍 6。 A を返します。距離と投票の式を使い、学習した採点関数は使っていません。
6. k=3 の地図、拍 7。 左上は A、右下は B、本物の A 前哨にも小領域が残ります。
7. k=1、拍 8–10。 距離と順序は固定して一行だけに切り替えます。誤ラベル B が一票で勝ち、問い合わせは B。A 領域に B の島が現れ、保存点での正解率は依然 100% です。
8. k=9、拍 11–13。 A 6 対 B 3 で問い合わせは A に戻ります。誤りの島と本物の前哨がともに消えます。(0,−3) の九近傍は A 4、B 5 なので本物の A を B とします。
9. 輪の規則。 誤りの輪は正しくラベル付けされた点との不一致だけを示し、誤ラベル点には付けません。アルゴリズムは誰がノイズか知りません。この区別は教材作者が出所を知るため可能です。
10. 全体比較、拍 14。 k=1、3、9、13 の地図を並べます。1 はノイズの島、3 はこの例のノイズ修正と前哨を両立、9 は前哨を喪失、13 は全て A。14 点中 13 点なら A は最低 7、B は最大 6 なので必ず A となり、本物の B 五点が誤りです。
11. 終了、拍 15。 設定した k=3 と答え A に戻ります。保存、距離、整列、切出し、投票が全手順です。

計算量

一問い合わせは距離 O(Nd)、全整列 O(N log N)。上位 k 個のヒープなら O(N log k) で維持できます。本課は切替実験のため全順序を残します。モデル保存とコピーは O(Nd)、距離表は別に O(N)。前処理と索引構築は「保存だけ」の基本版には含めません。

厳密索引の効果はデータ次第、近似索引は近傍集合やクラスを変える場合があります。「学習が速い」だけで総費用を評価できません。

境界ケース

• 標本と一致：距離ゼロで k=1 は通常そのラベル。ただし同座標の矛盾ラベルには同点規則が必要です。距離加重版はゼロ除算も扱います。
• 距離の同点：距離、ラベル、安定した元順で処理します。二クラスで奇数 k なら票数は同点になりません。多クラスや偶数では most_common(1) の順序へ無意識に任せず規則を決めます。
• k=N：位置を無視し全体の多数を返します。本例では k=13 で既に単色です。
• 遠い問い合わせ：自動拒否せず、外部の領域は端の点に支配され得ます。似た学習例を見た証拠ではありません。
• 高次元：多数の独立特徴では距離が集中し、最短と最長の比が 1 に近づく場合があります。全高次元で必ず失敗するわけではありませんが、距離や次元削減、学習した表現が必要情報を保つか調べます。

よくある間違い

• 重みの訓練を期待する。基本版に最適化はなく、問い合わせ、前処理、索引の費用を測ります。
• 同じ問い合わせで k を変えると距離も再計算すると思う。本実験は dists[:k] だけを変えます。点や問い合わせが変われば再計算が必要です。
• k=1 の訓練満点を信頼する。独自の座標なら自分を見つけるだけです。汎化は検証集合で測ります。
• 単位を無視する。数値範囲の大きい特徴が距離を支配し得ます。
• 55×55 のセルの辺を正確な境界と読む。投票はセル内部でも変わり得ます。