プロトタイプ法とk-NN - データが語る「近さ」の力

犬か猫か判定するとき、「最も近い過去のデータに従え」——この単純な発想が時に最強の分類器になる。 K-means、LVQ、k-NN、DANNまで、「近さ」を武器にした分類手法を視覚的に学ぼう。

プロトタイプとは何か - 代表点の発想

スーパーで果物を仕分けするとき、私たちは無意識に「これはリンゴの典型に近い、あれはミカンの典型に近い」と判断している。この「典型」がプロトタイプ（代表点）だ。

2クラスのデータ点から各クラスのプロトタイプ（代表点）が登場し、ボロノイ境界が形成されるアニメーション — 黄色い大きな点がプロトタイプ。各データ点は最も近いプロトタイプに属する。

機械学習の文脈では、各クラス（グループ）をいくつかの代表点で表し、新しいデータが来たときに「どの代表点に最も近いか」で分類する手法をプロトタイプ法という。

プロトタイプを使う手法には大きく3つある：

K-meansクラスタリング — 各クラスを複数の代表点で表す。代表点はクラスの「重心」に収束する。
学習ベクトル量子化（LVQ） — 代表点を境界に適した位置に学習で動かす。
ガウス混合モデル — データを確率分布として表現する「柔らかい」代表点。

これらは全て、「最も近い代表点のクラスに分類する」という基本ルールを共有する。どれを使うかによって、代表点のどこに配置するかが変わる。それが性能の差を生む。

\hat{G}(x) = \arg\min_k \min_j \|x - m_k^{(j)}\|

この式を読み解こう：

$$x$$ は分類したい新しいデータ点
$m_k^{(j)}$ はクラス $$k$$ の $$j$$ 番目のプロトタイプ（代表点）
$\|\cdot\|$ はユークリッド距離（2点間の直線距離）

つまり「全ての代表点との距離を計り、最も近い代表点のクラスに分類する」——それがプロトタイプ法の本質だ。

K-meansクラスタリング - 反復で収束する代表点

K-meansは最もシンプルなプロトタイプ法だ。「各クラスの重心（平均の位置）を代表点とする」という考え方を、反復的に洗練させる。

K-meansの反復収束プロセス。初期プロトタイプ（×マーク）が各クラスタの重心へ矢印で移動するアニメーション — ×マークのプロトタイプが緑の矢印に沿って各クラスの重心へ収束していく。

アルゴリズムの手順

各クラスに $$R$$ 個の初期プロトタイプをランダムに配置
すべての訓練データ点を、最近接プロトタイプに割り当て
各プロトタイプを、割り当てられた点の平均に移動
変化がなくなるまで2〜3を繰り返す

なぜこれが機能するか？平均は「割り当てられた全ての点への距離の二乗和を最小化する」点だからだ。つまり、各ステップで「割り当て」と「更新」の両方が改善され、収束が保証される。

分類への応用: 各クラスで独立にK-meansを実行し、プロトタイプにクラスラベルを付ける。そして最近接プロトタイプのクラスで分類する。

K-meansの弱点

プロトタイプはクラス内のデータの「重心」に収束するため、クラスの内部に配置される傾向がある。クラス境界付近の「判定が難しいゾーン」に代表点がない場合、精度が落ちる。

次に見るLVQはこの問題を解決しようとする試みだ。

LVQ - 境界を学習する代表点

K-meansのプロトタイプは「クラスの重心」に収束する。しかし分類では境界付近が最も重要だ。境界から離れた「コア」の領域は、どんな手法でも正しく分類できる。

学習ベクトル量子化（LVQ: Learning Vector Quantization）は、この問題を解決する。「ベクトル量子化」という名前は難しそうだが、意味はシンプルだ。「ベクトル（データ点）を量子化（少数の代表点に丸める）する」——その代表点を境界付近の最適位置に置く手法だ。

LVQのプロトタイプ更新規則。左パネルでは同クラスのデータ点にプロトタイプが引き寄せられ、右パネルでは異クラスのデータ点からプロトタイプが押し出される — 左：同クラス（緑矢印）→ 引き寄せる。右：異クラス（赤矢印）→ 遠ざける。

LVQのアイデアは直感的だ：

正解クラスのプロトタイプなら: 近づける（「このプロトタイプは良い代表だ」と強化）
不正解クラスのプロトタイプなら: 遠ざける（「このプロトタイプは間違いを犯している」と弱化）

これを訓練データ点を1つずつ処理しながら繰り返すことで、プロトタイプが境界付近の「最も重要な場所」に移動していく。

m_{j(k)} \leftarrow m_{j(k)} + \varepsilon(x_i - m_{j(k)}) \quad \text{（同クラス：近づける）}

m_{j(k)} \leftarrow m_{j(k)} - \varepsilon(x_i - m_{j(k)}) \quad \text{（異クラス：遠ざける）}

$\varepsilon$ （イプシロン）は学習率と呼ばれる小さな正の数で、反復が進むにつれてゼロに収束させる（「最初は大きく動き、後から微調整する」イメージ）。

K-meansとの違い

K-meansは各クラスの内部を見て重心を計算する。LVQはクラス間の境界を見ながら、境界付近のプロトタイプを最適な位置に移動させる。

次は全く別のアプローチへ: プロトタイプを事前に学習するのではなく、全ての訓練データをそのまま「記憶」として使う手法がある。それがk-最近傍法（k-NN）だ。

k-最近傍法（k-NN）- 多数決で分類する

プロトタイプ法は「事前に代表点を学習する」。これとは全く対照的な手法がk-最近傍法（k-NN: k-Nearest Neighbor）だ。

k-NNは「学習しない」。訓練データを全てそのまま記憶し、新しいデータが来たときに初めて判断する。

k-NNの多数決プロセス。白いクエリ点の周りに拡大する円が広がり、k=5の近傍点が強調され、多数決でクエリ点が橙色に変わる — 円が広がって5個の近傍点を捕捉。橙3個・青2個の多数決でクエリ点が橙に決定。

アルゴリズムの仕組み

クエリ点 $$x_0$$ （分類したい点）から最も近い $$k$$ 個の訓練データ点を見つける
それら $$k$$ 個の中で最も多いクラスに分類（多数決）

たとえば $$k=5$$ のとき、5個の近傍点のうち3個が「クラスA」、2個が「クラスB」なら → クラスAに分類。

\hat{G}(x_0) = \arg\max_k \frac{1}{k} \sum_{i \in \mathcal{N}_k(x_0)} I(g_i = k)

各記号の意味：

$\mathcal{N}_k(x_0)$ : $$x_0$$ に最も近い $$k$$ 個の訓練データのインデックス集合
$$g_i$$ : $$i$$ 番目の訓練データのクラスラベル
$I(\cdot)$ : 条件が真のとき1を返す指示関数（当てはまれば1、外れれば0）

「近傍 $$k$$ 個のうち、各クラスに何点属するかを数え、最も多いクラスに決める」という多数決だ。

なぜ単純なのに強いのか

この「なんと単純な！」と思えるアプローチが、手書き文字認識・衛星画像分類・心電図パターン認識などで最良の結果を出すことがある。理由は強力な理論的保証にある：

\text{1-NN誤り率} \leq 2 \times \text{ベイズ誤り率}

「ベイズ誤り率」とは理論上の最小誤り率——どんなに賢い分類器でも超えられない壁だ（データ自体のノイズによる限界）。1-NNはその最大2倍の誤り率しか持たない。これは非常に強い保証だ。

k と決定境界 - 「近さ」の精度を決める数

$$k$$ の値が決定境界の形に劇的な影響を与える。同じデータでも、 $$k$$ を変えると全く違う境界が引かれる。

k=1（左）とk=15（右）の決定境界の比較。左はギザギザの複雑な境界、右は滑らかな曲線的な境界 — 同じデータ・同じアルゴリズム。k=1（左）では複雑な境界、k=15（右）では滑らかな境界。

kの値による違い

k=1（最も近い1点だけで決める）: 各訓練点が「自分の縄張り」を主張する。境界は非常に複雑でギザギザ。訓練データに完全にフィットしているが、ノイズにも過剰反応する。

k=15（近い15点の多数決）: 多くの点の意見を聞く。境界は滑らかになり、大局的なパターンを捉える。しかし細かい構造を見逃す可能性がある。

バイアス・バリアンスのトレードオフ

これは機械学習で頻繁に登場するバイアス・バリアンスのトレードオフだ：

バイアス: 「的の中心からのズレ」= モデルが本質的な構造を見逃す度合い
バリアンス: 「的へのばらつき」= モデルがデータの変動に敏感すぎる度合い

$$k$$ が小さい ↔ バイアス低・バリアンス高（訓練データに過剰適合）

$$k$$ が大きい ↔ バイアス高・バリアンス低（本質的な構造を見逃す）

最適な $$k$$ は問題の複雑さによる。「超平面で綺麗に分離できるシンプルな問題」では大きなkが最良。「チェッカーボードのように複雑な境界を持つ問題」では小さなkが最良。最適な $$k$$ はクロスバリデーションで選ぶ。

次元の呪い - 高次元での「近さ」の崩壊

k-NNには致命的な弱点がある。次元が増えると「近い」はずの点がどんどん遠くなる。これを「次元の呪い」という。

1D→2D→高次元と次元が増えるにつれて、近傍（赤い領域）が空間全体を覆っていく様子を3パネルで表示 — 左から1D、2D、高次元。赤い近傍領域が次元増加とともに空間全体に広がっていく。

数字で見る次元の呪い

1次元（数直線）: 単位区間[0,1]に100個の点があれば、各点の最近傍はおよそ0.01の距離にある。

2次元（正方形）: 単位正方形に100個の点があれば、最近傍はおよそ0.1の距離に。

10次元（超立方体）: ここが問題だ。10次元の単位超立方体に100万個の点があったとしても、 1-近傍の中央値距離はおよそ0.52。

超立方体の端（中心から最大距離 $\sqrt{10}/2 \approx 1.58$ ）に対して0.52という数字は、近傍点が立方体の大部分を占める領域にある、ということだ。「近い点」を探したつもりが、実は全体のかなりの範囲を見回している。

何が問題か？

k-NNは「クエリ点の近傍では、クラス確率がほぼ一定」という仮定に基づく。しかし次元が高いと、「近傍」がとても遠く、その中でクラス確率が大きく変化してしまう。「近い」はずの点が実は全然近くない——これが精度低下の原因だ。

この問題を解決するのが次に見る「適応的最近傍法」だ。

適応的最近傍法（DANN）- 楕円形の近傍

次元の呪いを克服するアイデア：近傍の形を丸から楕円に変える。

標準的なk-NNは「円（球）形」の近傍を使う。しかし、クラス境界が特定の方向に走っている場合：

境界に沿う方向（クラスが変わらない方向）は、遠くまで見ても安全
境界を横切る方向（クラスが変わる方向）は、慎重に見なければならない

標準k-NNの円形近傍（左）とDANNの楕円形近傍（右）の比較。同じデータ上でクエリ点の近傍形状が異なり、楕円形は境界方向に狭く境界に沿う方向に広い — 左：円形近傍は境界を越えてしまう。右：楕円形近傍は境界に沿って伸び、誤りを防ぐ。

適応的最近傍法（DANN: Discriminant Adaptive Nearest-Neighbor）はこの直感を数学にする：

クラスが変化しない方向: 近傍を広げる（「安全地帯」なので遠くまで見られる）
クラスが変化する方向: 近傍を狭める（「危険地帯」なので慎重に）

つまり、近傍を境界に沿って引き伸ばした楕円形にする。

DANNは各クエリ点の周辺50点を使って、局所的なクラス境界の方向を推定し、それに応じて距離の計算方法を変える。

D(x, x_0) = (x - x_0)^T \Sigma (x - x_0)

ここで $\Sigma$ は適応的共分散行列（クエリ点 $$x_0$$ の周辺から計算される）。

\Sigma = W^{-1/2}\left[B^* + \varepsilon I\right]W^{-1/2}

$$W$$ : クラス内共分散（同じクラス内での点の散らばり）
$$B$$ : クラス間共分散（クラスの重心間の差異）
$B^* = W^{-1/2}BW^{-1/2}$ （標準化されたクラス間共分散）
$\varepsilon$ : 小さな正数（数値安定性のため）

「クラス間の差が大きい方向（ $$B$$ 大）では近傍を縮め、クラス内の散らばりが大きい方向（ $$W$$ 大）では近傍を広げる」という仕組みだ。

効果: 高次元でもクラス識別に本当に関係する方向だけに着目できる。不要な方向に近傍が広がることを防ぐ。

まとめ - 「近さ」の哲学

このページで見てきた手法を振り返ろう。

4つの手法（K-means、LVQ、k-NN k=1、k-NN k=15）の決定境界を2x2グリッドで比較するアニメーション — 同じデータから4種類の境界が生まれる。それぞれ「近さ」の使い方が異なる。

K-meansからDANNへの発展

K-means: クラスの「中心」を代表点とする。シンプルだが、境界付近の最適化がない。
LVQ: 訓練を通じて代表点を境界付近の最適位置に移動させる。
k-NN: 代表点を使わず、全データを記憶して多数決で分類する。強力な理論的保証あり。
DANN: 高次元の問題に対応するため、近傍の形を適応的に変える。

どんな問題に使うか

データが少なく特徴量が低次元: k-NNが最強になりやすい
決定境界が非常に複雑: 小さなk（k=1や3）が有利
決定境界がシンプル: 大きなkで滑らかな境界を使う
高次元問題: DANNやSVM（前章）など、次元の呪いに対応した手法を選ぶ

手法	学習コスト	予測コスト	長所	短所
K-means	中（反復）	低	シンプル	境界最適化なし
LVQ	高（反復）	低	境界最適化	理論的根拠弱い
k-NN	なし	高（全データ探索）	強い理論保証	次元の呪い
DANN	中（局所計算）	高	高次元対応	複雑な実装

最後に深い問いを

これらの手法の本質は「モデルを仮定しない」点にある。線形回帰も決定木もニューラルネットワークも、データの中に隠れたパターン（ルール）を見つけようとする。

しかしk-NNはルールを探さない。データそのものが答えだ。

「理解（ルールを学ぶ）」と「記憶（データを覚える）」——どちらが賢いのか？

この問いは機械学習の中心にある。k-NNは「記憶」の道を選び、それが最強になる問題が確かに存在する。