1 基本概念
近傍探索は、与えられた対象に対して、距離や類似度の意味で近い要素を効率よく見つけるための方法群である。検索対象は点、文書、画像、特徴ベクトル、状態空間上の解候補など多岐にわたり、全件比較を避けながら有望な候補を抽出することを目的とする。厳密な最良解を求める場合もあれば、実用上十分な近似結果を高速に得る場合もある。
1.1 近傍の定義
近傍とは、ある基準点の周囲にある対象集合を指す。定義は問題設定に依存し、半径を固定して「その範囲内にある点」を近傍とする場合もあれば、最近傍のように順位で定める場合もある。実装上は、検索したい関係を明確に定義することが、アルゴリズム選択の前提となる。
1.2 距離と類似度
近さの尺度は大きく距離と類似度に分かれる。距離は「どれだけ離れているか」を表し、値が小さいほど近い。類似度は「どれだけ似ているか」を表し、値が大きいほど近いと解釈される。両者は相互変換できる場合もあるが、データの性質によって扱いやすさが異なる。
1.2.1 ユークリッド距離
ユークリッド距離は、空間内の点同士の直線的な距離である。幾何学的に直感的で、連続値の特徴量に広く用いられる。単純だが、高次元では各次元の寄与が分散しやすく、近さの判別が難しくなることがある。
1.2.2 マンハッタン距離
マンハッタン距離は、各座標差の絶対値を足し合わせた尺度である。格子状の移動を連想させるためこの名がある。外れ値の影響を受けにくい場面があり、特徴量の各成分を独立に評価したいときに使われる。
1.2.3 コサイン類似度
コサイン類似度は、ベクトル同士の向きの近さを測る指標である。大きさよりも方向を重視するため、文書ベクトルや埋め込み表現でよく使われる。値が高いほど方向が近く、内容的な一致度の目安として働く。
1.3 探索対象の表現
探索の効率は、対象をどのように表現するかに強く左右される。数値ベクトル、文字列、集合、グラフ上の状態など、表現形式によって有効な索引構造や比較方法が変わる。前処理で特徴を圧縮したり正規化したりすることも、探索性能の改善に寄与する。
2 探索手法
近傍探索の手法は、正確性と速度の折り合いをどう取るかによって整理できる。単純な全探索は確実だが重く、専用の索引を用いる方法は高速化に向く。さらに、近似を許すことで大規模データでも実用的な応答時間を実現しやすくなる。
2.1 総当たり探索
総当たり探索は、全ての候補と基準対象を比較する方法である。実装は容易で、結果の正しさも明確だが、データ量が増えると計算負荷が急速に高まる。小規模問題や検証用途では有効だが、大規模環境では補助的な基準として扱われることが多い。
2.2 空間分割法
空間分割法は、検索空間を領域に分け、不要な部分をまとめて除外する考え方である。点群を局所的な範囲に整理することで、比較対象を減らしやすくなる。低次元から中程度の次元で特に有効であり、範囲判定が比較的単純な場合に向いている。
2.2.1 領域分割木
領域分割木は、空間を再帰的に区切って管理する木構造である。各節点が担当領域を持ち、探索時には条件に合わない枝を刈り込む。代表例として、点群を階層的に分ける構造があり、範囲検索や最近傍検索の補助に使われる。
2.2.2 格子分割
格子分割は、空間を規則的なセルに区切って対象を配置する方式である。位置が近い要素を同じセルまたは隣接セルに集めやすく、局所的な探索に適する。セルサイズの設定が性能を左右し、粗すぎると候補が増え、細かすぎると管理コストが上がる。
2.2.3 ハッシュ法
ハッシュ法は、近い対象が同じ桶に入りやすいように写像を設計する手法である。通常のハッシュ表とは異なり、近傍関係を反映するような関数を用いる点が特徴である。候補を大きく絞れる一方で、衝突や取りこぼしを伴うため、近似探索と相性がよい。
2.3 木構造を用いる手法
木構造を用いる方法は、データの階層的整理によって探索範囲を縮める。節点ごとの境界や分割規則を利用し、関連の薄い領域を早めに除外する。構造が適切に保たれていれば、比較回数を大幅に抑えられる。
2.3.1 二分木
二分木は、各節点が二つの子を持つ基本的な木構造である。近傍探索では、値の大小や空間の片側・反対側という条件で枝を選別する。単純な分岐により実装しやすいが、データ分布に偏りがあると性能が不均一になる。
2.3.2 範囲木
範囲木は、ある区間や範囲に含まれる要素を効率よく取り出すための構造である。検索対象が数値列や座標集合のように順序を持つ場合に有効で、複数条件の絞り込みにも対応しやすい。近傍判定の前処理として使われることもある。
2.3.3 近傍木
近傍木は、各点について近い候補をたどりやすくした木構造である。局所的な接続情報を利用して、探索を少ない分岐で進める。用途によって作り方は異なるが、類似点の集合をまとめて扱う発想が共通している。
2.4 近似探索
近似探索は、厳密な最適候補を保証しない代わりに、十分近い結果を速く返す方法である。大規模データや高次元環境では、完全性より応答速度が重視されることが多い。実務では、再現率や誤差の許容範囲を定めて運用される。
2.4.1 局所探索
局所探索は、現在の候補の近くを重点的に調べる手法である。初期値から少しずつ改善し、周辺の有望な点へ移動していく。山登り型の更新や反復改善と親和性が高く、全空間を広く走査する必要がない。
2.4.2 確率的手法
確率的手法は、ランダム化を利用して探索の偏りを抑える方法である。候補の選択や枝の展開に偶然性を導入することで、局所的な行き詰まりを避けやすくなる。厳密な保証は弱くなる場合があるが、平均的な性能を高めやすい。
2.4.3 多段階絞り込み
多段階絞り込みは、粗い判定から細かい判定へ順に進める方法である。最初に軽量な基準で候補を減らし、その後に高精度な比較を行う。処理の前半で多くを除外できれば、後段の計算負担を大きく抑えられる。
3 理論的性質
近傍探索の理論では、計算量、精度、空間表現の性質が主要な論点となる。アルゴリズムの速さだけでなく、返される結果がどの程度信頼できるかも重要である。さらに、データ次元が増すと、直感的な効率が失われることがある。
3.1 計算量
計算量は、入力規模に対してどれだけの処理や記憶を要するかを示す指標である。近傍探索では、前処理、問い合わせ、更新の各段階で異なる負荷が生じる。単純な比較回数だけでなく、索引の構築コストや保守の手間も評価対象になる。
3.2 正確性と近似性
正確性は、真の近傍を必ず見つけられるかどうかに関わる。近似性は、完全一致ではなくても実用的に十分な候補を返せるかを示す。用途によって要求水準は異なり、検索、推薦、分類補助などでは近似結果が有用なことが多い。
3.3 次元の呪い
次元の呪いは、次元数の増加により空間分割や距離の意味が薄れ、探索が難しくなる現象である。高次元では点が疎になり、近い・遠いの差が見えにくくなる。多くの手法が次元上昇に対して急速に効率を失うため、特徴選択や次元削減が重要になる。
3.4 探索半径と候補数
探索半径を広げると候補数は増え、狭めると減る。前者は取りこぼしを減らしやすい一方で計算量が増し、後者は高速だが見逃しが起こりやすい。適切な半径設定は、精度と速度の均衡を取るうえで重要である。
4 応用
近傍探索は、似た対象を素早く見つける必要がある多くの分野で使われる。検索対象が文書でも画像でも、あるいは数値データでも、基本的な考え方は共通している。データ量の増大に伴い、その重要性はさらに高まっている。
4.1 情報検索
情報検索では、問い合わせ文に近い文書や項目を見つけるために近傍探索が使われる。語彙の一致だけでなく、埋め込み表現による意味的な近さも扱われる。関連候補を効率よく並べるため、索引構造と再ランキングの組み合わせが用いられることが多い。
4.2 画像処理
画像処理では、画素、特徴点、局所記述子、画像全体の特徴量などを対象に近いものを探す。類似画像検索、パターン照合、重複検出などで利用される。視覚情報は高次元になりやすいため、近似的な方法が実用上重要になる。
4.3 機械学習
機械学習では、近傍探索が学習と推論の双方で役立つ。近いデータ点を参照することで、局所的な構造を活かした判断が可能になる。特徴空間での距離設計が、モデルの性能に直接影響することも多い。
4.3.1 分類
分類では、近い訓練例の多数決や重み付き投票を通じてラベルを推定する方法がある。代表的には、近傍を利用する単純な分類器が知られている。距離尺度の選び方が結果に反映されやすく、前処理の影響も大きい。
4.3.2 クラスタリング
クラスタリングでは、互いに近い点を同じ समूहにまとめる際に近傍関係が活用される。密度に基づく手法やグラフ構造を使う手法では、局所的なつながりが重要になる。近い要素を素早く抽出できると、グループ形成の計算が効率化される。
4.3.3 異常検知
異常検知では、周囲に似た例が少ない点を外れ値候補として扱うことがある。近傍が疎な対象は、通常とは異なる振る舞いを示す可能性が高い。局所密度や近接距離を指標にすることで、比較的単純なルールでも有効な判定ができる。
4.4 組合せ最適化
組合せ最適化では、解候補の近さを利用して探索空間を絞る。近接する状態同士の移動を繰り返し、より良い解を探す局所探索法と関係が深い。候補を体系的に整理できると、広大な解空間の中でも実行可能な探索が行いやすくなる。
</INTERNAL_LINK_CANDIDATES> 距離（対象間の隔たりを表す尺度） 類似度（対象同士の似ている度合いを表す尺度） ユークリッド距離（直線的な幾何距離） マンハッタン距離（座標差の絶対値和による距離） コサイン類似度（ベクトルの向きの一致度を表す指標） 空間分割法（検索空間を領域に分けて候補を減らす方法） 領域分割木（空間を階層的に区切る木構造） 格子分割（空間を規則的なセルに分ける手法） ハッシュ法（近い対象を同じ桶に集めやすい写像方式） 近似探索（完全性より速度を重視する探索） 局所探索（近傍周辺を重点的に調べる反復法） 確率的手法（ランダム化を用いて探索を進める方法） 多段階絞り込み（粗い判定から精密判定へ進む手法） 次元の呪い（高次元で探索効率が落ちる現象） 特徴選択（有用な特徴量を選ぶ前処理） 次元削減（特徴空間の次元を減らす変換） 再ランキング（初期候補を精査して順位を入れ替える処理） 埋め込み表現（意味や構造を数値ベクトルで表したもの） 異常検知（通常と異なるデータを見つける技術）