データサイエンス設計マニュアル

10.2 最近傍分類 291

くく

なる。その問題がないとしても、q の最近傍点が q と同じセルにあるという保証はない。特に q

が境界線の近くにあるときには、別のセルになっている可能性が高い。本当に最近傍点を探すつもり

なら、近隣のセルも検索しなければならない。

• kd 木：探索をしやすくするために空間を階層的に分割する木に基づいたデータ構造はたくさんある。

kd 木の各ノードは、任意の次元をルートとし、その次元を半分に分割する中央値の線や面を定義す

る。そして、分割された空間の中で別の次元を使ってさらに分割を繰り返していくことで、最終的に

ノードによって定義される領域に訓練点が 1 つだけ残るようにする。

このような形で分割の階層構造を作っていくと、探索を支援するという意味ではとても理想的だ。

ルートからスタートし、与えられた点 q が中央値の線もしくは面の左右どちら側に含まれるかを判定

する。これで q が含まれる側がわかると、どちらの木で再帰処理を行うかが決まる。木構造を 1 段階

下りるたびに点の集合を半分に分割していくので、検索時間は log n のオーダーになる。

このように空間を分割して探索のための木構造を作る手法にはさまざまな種類があり、あなたが使っ

ているプログラミング言語の関数ライブラリでもそのうちの 1 つ、または一部が実装されているはず

だ。最近傍探索のような問題では高速に探索できるものがあるが、おそらく速度を上げるために正確

度が犠牲になっている。

これらの技法は、次元が低いなら（例えば ...