近傍探索

ひとことで言うと

近傍探索は、クエリ $\mathbf{q}$ に対して、データ集合の中から距離が小さい点を探す処理です。最も近い1点だけでなく、近い順に $k$ 点を返す方法や、半径 $r$ の内側を返す方法も同じ問題として扱えます。分類や回帰の前段だけでなく、埋め込みベクトルの検索にも現れます。

なぜ必要か

最も単純な厳密探索は、クエリと全データ点の距離を計算し、最小値または上位 $k$ 個を選びます。データ点数を $n$、特徴量の次元を $d$ とすれば、1クエリの距離計算は $O(nd)$ です。クエリが増えるほど全探索の時間も線形に増え、検索回数が多いサービスでは距離計算が支配的になります。

そこで、検索前にデータを空間的な構造へ整理します。KD-treeのような木は、クエリから遠い領域を候補から外し、残った葉を調べます。ただし、次元が高いと領域を十分に絞れず、木をたどっても多くの点を確認することになります。低次元で効いた構造を、高次元データへそのまま移せるとは限りません。

仕組み

データ点を $\mathbf{x}_i \in \mathbb{R}^{d}$、クエリを $\mathbf{q}$ とし、ユークリッド距離を使うなら

$$d(\mathbf{q}, \mathbf{x}_i)=\sqrt{\sum_{j=1}^{d}(q_j-x_{ij})^2}$$

です。ここで $d$ は特徴量の次元、$q_j$ と $x_{ij}$ はそれぞれクエリと $i$ 番目の点の $j$ 番目の成分です。厳密な最近傍は、この距離が最小になるインデックスを

$$i^*=\underset{i\in\{1,\ldots,n\}}{\operatorname{argmin}}\ d(\mathbf{q},\mathbf{x}_i)$$

で選びます。$k$近傍なら距離を昇順に並べた先頭 $k$ 個、半径探索なら $d(\mathbf{q},\mathbf{x}_i)\le r$ を満たす点です。

KD-treeは各分割で1つの座標軸を使い、点を部分領域へ分けます。ある領域が現在の候補より遠いと判定できれば訪問せず、葉では点の距離を計算します。葉サイズを変えてもクエリ結果は変わらず、探索の計算と木の大きさのバランスが変わります。高次元で除外できる領域が少なくなると枝刈りの効果が薄れ、厳密な全探索に近づきます。

近似最近傍探索は、すべての候補を確認する条件を緩め、候補を絞って近い点を返します。厳密な最近傍を必ず返す保証を、検索時間やメモリと交換する設計です。評価では速度だけでなく、厳密解との一致率や上位 $k$ の再現率を測ります。どこまで誤差を許せるかを先に決めないと、近似の効果を判定できません。

試験でどう問われるか

問われ方	正解に寄る条件	引っかけ
厳密探索の計算量	1クエリで全 $n$ 点との距離を調べるため、$d$ を含めて $O(nd)$	$k$ が小さいからデータ数に依存しないとする
KD-treeの効果	空間分割で遠い領域を枝刈りできるときに候補を減らす	次元やデータ分布に関係なく常に高速とする
近似最近傍の意味	速度・メモリと、最近傍の厳密さや再現率を交換する	近似でも厳密解を必ず保証するとする
APIの使い分け	kneighborsは個数、radius_neighborsは半径で問い合わせる	半径を指定すれば必ず固定個数が返るとする

実装で確かめる

NumPyだけで厳密な1近傍を求めます。全点との距離を計算しているため、データ数に対して線形に仕事が増える形が現れます。平方根は順位を変えないので、比較だけなら二乗距離で十分です。

import numpy as np

X = np.array([[0., 0.], [2., 1.], [5., 4.], [1., 3.]])
q = np.array([1.2, 0.8])
squared = ((X - q) ** 2).sum(axis=1)
order = np.argsort(squared)
print(order[:2], np.sqrt(squared[order[:2]]))

取り違えやすいもの

用語	近傍探索との切り分け
最近傍探索	距離に基づいて候補の点を返す検索処理。ラベルの予測は含まない
木構造探索	候補を絞るためのデータ構造。厳密探索の実装にも使えるが、近似そのものではない
全探索（brute）	全点との距離を計算する方式。結果は厳密だが、1クエリの計算は $n$ に比例する
近似最近傍	候補を限定して速度を得る方式。返す点の厳密さを評価する必要がある
埋め込み検索	文書や画像などをベクトル化した後の検索用途。内部の核心はベクトル間の近傍探索

想起チェック

厳密な全探索がデータ数に対して線形になる理由は何か

1クエリごとに全 $n$ 点との距離を計算するためです。次元を $d$ とすれば距離計算までの目安は $O(nd)$ です。

KD-treeが高次元で効きにくくなるのはなぜか

空間分割しても、クエリから遠いと安全に捨てられる領域が少なくなり、多くの点を確認する必要が出るためです。

近似最近傍を採用するとき、速度以外に何を測るか

厳密解との一致率や、上位 $k$ の再現率です。近似は速度やメモリと検索結果の厳密さを交換するため、許容する品質を数値で確認します。