k近傍法・最近傍探索（kd-tree・近似最近傍）
距離 の距離尺度を使って、近いデータ点を探すアルゴリズムをまとめます。
全体像
- k近傍法：近い $k$ 個のデータ点の多数決・平均で予測する機械学習の手法（予測ルール）
- 最近傍探索：クエリに近いデータ点を探す問題。k近傍法は予測の中でこの探索を部品として使う
- kd-tree・近似最近傍探索：最近傍探索を速くする解き方であり、k近傍法そのものの改良ではない（予測ルールの多数決・平均は変わらない）
k近傍法（予測手法：多数決・平均）
└─ 内部で最近傍探索を使う
│
最近傍探索（近いデータ点を探す問題）
├─ 厳密探索（正確な最近傍を返す）
│ ├─ 全探索（Brute-force）: O(Nd)
│ └─ kd-tree: 低〜中次元で平均 O(log N)
└─ 近似探索（ほぼ近い点を返す）
└─ 近似最近傍探索（ANN）: LSH、HNSW など
| 種類 | 役割 | |
|---|---|---|
| k近傍法 | 予測手法（分類・回帰） | 近傍点から予測値を決める |
| 全探索 | 厳密探索 | 全データとの距離を計算する素朴な探索 |
| kd-tree | 厳密探索 | 空間分割の木構造で探索を高速化する（低〜中次元向け） |
| 近似最近傍探索（ANN） | 近似探索 | 厳密さを犠牲にして高次元・大規模データでも高速に探す |
k近傍法（k-NN: k-Nearest Neighbor）
新しいデータ点（予測したい入力）が与えられたとき、訓練データの中から距離が近い順に $k$ 個のデータ点を選び、その多数決（分類）や平均（回帰）で予測を行う手法です。
- 分類：$k$ 個の近傍点のうち、最も多いクラスを予測結果とする
- 回帰：$k$ 個の近傍点の目的変数の平均値を予測結果とする
- 学習時には何も計算せず、予測時にはじめて距離計算を行う怠惰学習（Lazy Learning）の代表例
- $k$ が小さすぎるとノイズに敏感（過学習気味）、大きすぎると境界がなまる（未学習気味）というトレードオフがある
$k=1$ の場合（最も近い 1 点のクラス・値をそのまま使う）を最近傍法（1-NN）と呼びます。
計算コストの問題
k近傍法の予測は、次の 2 段階に分けられます。
2 の計算は軽く、計算コストの大半は 1 です。素朴な実装（全探索、Brute-force）では、新しいデータ点と訓練データ全件との距離を計算する必要があります。データ数を $N$、次元数を $d$ とすると、1 回の予測に $O(Nd)$ の計算量が必要になり、データ数が増えるほど予測が遅くなります。
この 1 の探索部分を高速化するのが、後述の kd-tree や近似最近傍探索です。多数決・平均という予測ルールは変わりません。
k近傍法とニューラルネットワーク
違い
| k近傍法 | ニューラルネットワーク（LLM など） | |
|---|---|---|
| 学習 | 何も計算しない（訓練データを保持するだけ） | 重み $\theta$ を勾配降下法で更新する |
| 予測時 | 訓練データとの距離を計算して多数決・平均 | 重みを使った順伝播で出力を計算する |
| モデルの実体 | 訓練データそのもの | 学習済みの重み |
| 出力 | クラスや数値 | 語彙上の確率分布（softmax の出力） |
k近傍法 は 入力 → 重みを持つモデル → 次の単語の確率分布 という LLM の流れとは仕組みが異なります。
損失関数の最小化もありません。
関係がある点
- Embedding 空間での近傍検索：単語や文を密ベクトルにしたあと、コサイン距離などで近いものを探す操作は、k近傍法 と同じ考え方です。RAG（検索拡張生成）で関連文書を探す部分がこれにあたります。ここでは LLM 自体ではなく、その周辺の検索部品として使われます
- 距離尺度の知識：ユークリッド距離やコサイン距離は、Embedding の類似度評価でそのまま使うので、k近傍法 の節の内容は LLM の理解に必要です
最近傍探索（Nearest Neighbor Search）
クエリ点 $\boldsymbol{q}$ に対して、データ集合の中から距離が最も近い点（または近い順に $k$ 個の点）を見つける問題です。
k近傍法はこの探索結果を使って予測しますが、最近傍探索自体は予測手法ではなく、検索エンジンやベクトル検索など予測を伴わない用途でも使われます。
解き方は、結果の正確さで次の 2 つに分かれます。
全探索（Brute-force）
クエリ点と全データ点との距離を計算し、小さい順に選ぶ最も素朴な方法です。
- 計算量：1 回の探索に $O(Nd)$
- 実装が単純で、厳密な結果が得られる
- データ数 $N$ が大きいと遅くなる
kd-tree（k-dimensional tree）
データ空間を軸に垂直な超平面で再帰的に分割し、二分木（ツリー）構造に整理しておくことで、最近傍探索を高速化するデータ構造です。
全探索と同じく厳密な最近傍を返し、探索の無駄を減らして速くします。$k$ 個の近傍が必要な場合も、探索中に見つかった上位 $k$ 個を保持して同様に枝刈りできるため、k近傍法の探索部分にも使えます。
仕組みのイメージ
- 分割に使う軸（次元）を 1 つ選ぶ（例： 1 次元目→ 2 次元目→ … と順番に、または分散が大きい軸を選ぶ）
- その軸の中央値（メディアン）でデータを 2 つに分割し、左右の子ノードに振り分ける
- 子ノードでも別の軸を使って同様に分割し、再帰的に木を構築する
- 探索時は、木を根からたどりながら「探索対象が入りうる領域」を絞り込み、関係のない領域（枝）は計算せずに刈り込む（枝刈り、pruning）
計算量
全探索の $O(N)$ と比べて、低〜中次元では大幅に高速化できます。
kd-treeの弱点（次元の呪いとの関係）
次元数 $d$ が大きくなると、分割による絞り込みの効果が薄れ、結局ほとんどの枝を調べる必要が出てきて、最悪 $O(N)$ の全探索に近づいてしまいます。これは 次元の呪い（Curse of Dimensionality） の一例で、高次元空間ではデータ点同士の距離の差がつきにくくなり、空間分割による絞り込みが効きにくくなることに起因します。
近似最近傍探索（ANN: Approximate Nearest Neighbor）
高次元・大規模なデータ（画像や文章の埋め込みベクトルなど）では、kd-tree のような厳密な最近傍探索は実用的な速度で動作しないことが多くなります。そこで、厳密に最も近い点ではなくほぼ近い点を高速に返すことに割り切った手法が 近似最近傍探索（ANN）です。
kd-tree を改良したものではなく、kd-tree が苦手な高次元・大規模データに対する別の選択肢です。
基本的な考え方
- 多少の精度（正確に最近傍を見つけられる保証）を犠牲にする代わりに、探索速度を大幅に向上させる
- 検索エンジン、レコメンデーション、大規模なベクトル検索（Embedding の類似検索など）で広く使われる
- 代表的な実装アプローチには、ハッシュを使って近い点を同じバケットに落とし込む方法（LSH: Locality Sensitive Hashing）や、グラフ構造をたどって近傍を探す方法（HNSW など）がある
kd-tree との関係
| kd-tree | 近似最近傍探索（ANN） | |
|---|---|---|
| 正確さ | 厳密な最近傍を保証 | 近似（正確な保証はない） |
| 得意な場面 | 低〜中次元 | 高次元・大規模データ |
| 次元の呪いへの耐性 | 弱い（高次元で性能劣化） | 相対的に強い（割り切って高速化） |