k-NNの計算量を切り詰める - 賢く速く近傍を探す

k-NNはシンプルで強力。だが予測のたびに全データと距離を測り直す——これは現実的ではない。空間を切り分ける kd-tree、データを凝縮する condensing、ノイズを除去する editing、そして高次元での落とし穴まで、アルゴリズムの「速くする知恵」を視覚的に学ぼう。

なぜk-NNは「遅い」のか - 予測のたびに走る全探索

k-最近傍法（k-NN）には学習フェーズがない。fit関数を呼んでも、ただデータを保存するだけ。本当のコストは予測のときにやってくる。

新しい入力点 $$x_0$$ が来たとしよう。k-NNがやることはこうだ：

訓練データ $$N$$ 個の点それぞれに対して、 $$x_0$$ との距離を計算する
距離が小さい順にソートし、上位 $$k$$ 個を選ぶ
その $$k$$ 点の多数決（分類）または平均（回帰）を返す

クエリ点から全データ点へ放射状に線が伸び、データ点数が増えるにつれて接続線が爆発的に増えるアニメーション — クエリ点（黄）から全データ点（青）へ線が一斉に伸びる。データが倍になれば線も倍になる。

ステップ1だけで $$N$$ 回の距離計算が必要だ。各距離計算は $$p$$ 次元なら $$O(p)$$ かかる。つまり1クエリあたり $O(N \cdot p)$ の計算量になる。

\text{1クエリの計算量} = O(N \cdot p)

$$O$$ は計算量を表す記法で「〜に比例する」という意味。ここで $$N$$ は訓練データ数、 $$p$$ は特徴量の次元。 $$N$$ が大きいほど、 $$p$$ が大きいほど、線形にコストが膨らむ。たとえば $$N$$ が10倍になれば、予測にかかる時間も約10倍になる。

問題は、この処理が「予測ごと」に発生すること。100万点のデータで毎秒1000クエリを処理したいなら、 1秒間に10億回の距離計算をしなければならない。シンプルさの代償としてはあまりにも重い。

ここに改善の余地が大きく残されている。「全探索しなくても、近傍は見つけられるはずだ」——これがこの章の出発点。

空間を切り分ける - kd-treeで「見るべき領域」を絞る

全点を見なくても近傍は見つけられる。直感を働かせてみよう。

クエリ点が画面の右上にあるとき、画面の左下にある点が「最近傍」になることはまずない。遠い領域は最初から除外できるはずだ。

2D平面をx軸→y軸→x軸と交互に分割してkd-treeを構築し、クエリ点から該当領域のみ探索するアニメーション — 縦・横と交互に空間を分割。クエリ点（黄）の領域だけを探索し、遠い領域（暗色）は枝刈りする。

この発想を形にしたのがkd-tree（k-dimensional tree）だ。空間を再帰的に半分ずつ切り分けて、木構造として整理する：

データ全体を、ある軸（例：x軸）の中央値の点で2つに分ける
それぞれの半分を、次の軸（y軸）の中央値の点で2つに分ける
これを繰り返し、各葉に少数の点だけが残るまで続ける

クエリ時には木をたどって、まずクエリ点が含まれる葉（小さな領域）を見つける。そこに含まれる数点だけで仮の最近傍を決め、その距離を半径とした球が他の領域に侵入していないかだけをチェックする。

侵入していなければ、その領域は完全にスキップ。木の枝を「切り落として」探索を省略するこの発想を、英語ではbranch and bound（枝刈り）と呼ぶ。木構造の比喩がそのまま生きている。

\text{kd-treeの平均計算量} = O(\log N)

$O(\log N)$ は「データが2倍になっても計算時間は1ステップしか増えない」という意味。 100万点でも約20回の判定で済む計算だ。これは全探索の $$O(N)$$ とは桁違いの改善になる。

ただしこれは「データが低次元で偏りなく分布している」場合。高次元になると、後で触れる次元の呪いにより、 kd-treeも全探索に近づいてしまう。

データを凝縮する - Condensingで本質だけを残す

そもそも、N点全てを保持する必要があるのだろうか？

クラスの中心付近にある点は、ほとんどの場合、決定境界の判定に影響しない。境界から遠い「内陸」の点は、他の同じクラスの点に守られているからだ。

本当に重要なのは、境界の近くにある点だけ—— この発想を実装したのがHart (1968) のCondensed Nearest Neighbor（CNN）アルゴリズムだ。

2クラスの散布図から境界近傍の点だけが明るく残り、内陸の点がフェードアウトするアニメーション — 境界付近の点（輪郭あり）だけが保存集合に残る。内陸の点（暗色）は決定境界の判定に不要なため除外される。

手順はこう（簡単のため $$k=1$$ 、つまり最も近い1点で分類する場合を考える）：

訓練データからランダムに1点を選び、それを「保存集合」に入れる
残りの点を1つずつ取り出し、現在の保存集合の中で最も近い点を見つける。その点のクラスと自分のクラスが一致すれば正しく分類できたとみなす
不一致（誤分類）の点だけを保存集合に追加する
データを一巡しても新たな追加が起きなくなったら終了

このアルゴリズムは、決定境界の近くにある「際どい点」を自動的に拾い上げ、中央付近の冗長な点を捨てる。結果として、データ数を大幅に削減できる——時には元の10分の1以下に。

|S_{\text{condensed}}| \ll N

凝縮後の集合 $S_{\text{condensed}}$ は元のデータ数 $$N$$ より大幅に小さい。これにより距離計算のコストが直接削減される。kd-treeと組み合わせれば、さらに効果的だ。

ただしこの手法には弱点もある。ノイズに弱いのだ。誤ラベルの点があると、それが「境界に近い」と判定されて保存集合に残り、しかも境界を歪めてしまう。

ノイズを編集する - Editingで境界をシャープに

Condensingが「本質を残す」アプローチなら、もう一つの戦略は「ノイズを取り除く」だ。

実データには必ず誤ラベルや異常値が混じる。そういう「裏切り者」の点が訓練データに残っていると、 k-NNは惑わされて誤った予測をしてしまう。

ノイズ点（誤ラベルの点）に×マークが現れて消え、境界が滑らかな曲線に整えられるアニメーション — ノイズ点（誤った位置にいる点）が検出されて除外される。残った点で滑らかな境界が形成される。

Multi-edit（Devijver & Kittler, 1982）は、こんなアイデアで動く：

訓練データを2つに分ける：訓練用とテスト用
訓練用で構築したk-NNでテスト用を分類
誤分類されたテスト点を訓練集合から削除
2つを入れ替えて同じことを繰り返す

これにより、自分自身のk-NNから見て「異常な」点（＝ノイズの可能性が高い点）が淘汰される。残ったデータで再度k-NNを構築すると、境界が滑らかになり、汎化性能が向上する。

CondensingとEditingは目的が逆向きだ：

手法	目的	残す点
Condensing	計算削減	境界近く（少数精鋭）
Editing	ノイズ除去	信頼できる多数派

\text{Edit}: \text{自己のk-NNで誤分類される点を除外}

\text{Condense}: \text{現在の集合で正しく分類できる点を除外}

二つの操作は「除外する基準」が正反対だ。実用では、Editing → Condensing の順で組み合わせるのが定石。まずノイズを取り除いてから、本質的な点だけを凝縮する。これによりk-NNは「速くて」「頑健」になる。

計算量を「読む」 - 高次元での落とし穴

ここまでで、k-NNを高速化する3つの武器を見てきた。最後に重要な注意点を一つだけ。

kd-treeも凝縮も、次元 $$p$$ が高くなると効果が薄れる。

理由は前章で見た次元の呪いだ。高次元空間では、ほとんどの点が「お互いに同程度に遠い」状態になる。空間を半分に切っても、クエリ点の球はすぐ隣の領域に侵入してしまい、枝刈りがほとんど効かない。

左：2D空間でkd-treeの探索範囲が小さい。右：高次元空間で探索範囲がほぼ全域に広がる対比アニメーション — 左（低次元）では探索範囲（赤）が小さな領域で済む。右（高次元）では探索範囲がほぼ全域を覆ってしまう。

実用的な目安として：

次元 $$p$$	kd-tree	推奨
$p \le 10$	効果大	普通に使える
$$10 < p < 30$$	効果中	工夫が必要
$p \ge 30$	ほぼ効かない	近似最近傍へ

\text{次元} p \uparrow \quad \Rightarrow \quad \text{kd-treeの効果} \downarrow

高次元では、正確な最近傍を諦めて近似最近傍探索（Approximate Nearest Neighbor, ANN）に切り替えるのが現代的な解だ。代表例を2つだけ紹介する：

LSH（Locality Sensitive Hashing）— 「似た点は同じハッシュ値になりやすい」ハッシュ関数を使い、衝突した点だけを比較する
HNSW（Hierarchical Navigable Small World）— 近い点同士を線で繋いだグラフを作り、その線を辿って近傍を素早く見つける

いずれもわずかな精度低下と引き換えに、圧倒的な速度を得る。検索エンジンや推薦システムの裏側でよく使われている。

なお「次元の呪い」と言っても、データが見かけ上1000次元でも実質的には数十次元の中に固まっていることがある（これを内在次元と呼ぶ）。kd-treeが効くかどうかは、この内在次元次第だ。

k-NNは「シンプルだが計算が重い」と言われがちだが、実はデータ構造の工夫一つで実用範囲が大きく広がる。これがk-NNが今もなお使われ続ける理由の一つだ。