最近傍探索のあれこれ 主にk-d tree

メモ書き．

全探索 (線形探索)

最も単純な方法は全探索である．注目点から空間中の全点の距離を測り，その距離が最小になる点を最近傍点とする．なお，計算量はO(n)

k-d tree (k-dimensional tree)

上手に二分木をつくることで探索空間を二分探索することが可能．最も有名なのがk-d tree．

どうやって木をつくるか

簡単のため2次元で考えると手順は以下のようになる．

1. x軸に平行(別に垂直でもよい)に空間を二分割する．上下でノードをつくる

2. y軸に平行に空間を二分割する．左右でノードをつくる

3. x軸に平行に空間を二分割する．上下でノードをつくる

4. ・・・

これを再帰的に繰り返す．

分割とk-d tree

どうやって空間を二分割するか

図では簡単のために単純にど真ん中で空間を分割しているが，点の座標値の中央値で分割するとk-d treeは平衡木になる．平衡木になると探索の計算量がほぼO(log n)になるのでお得．
全点を対象として中央値を計算すると木の構築に時間がかかるので，点をランダムサンプリングして中央値を計算する方法もある．

高次元にはおすすめできない

高次元データをk-d treeに展開すると結局ほとんどの点を調べることになり，全探索とあまり変わらなくなる．
k-d treeを採用するときには，

次元数: d

点の個数: n

としたとき

n >> 2^d となっていることが望ましい．