最近傍探索のあれこれ 階層型K-means tree

メモ書き．

階層型 K-means tree

k-d treeと同じように「上手に二分木をつくることで探索時間を減らしましょう」という手法の一つ．CRUX氏がマッチングに使用しているのを見て，なるほどと思ったのでメモ．

どうやって木をつくるか

K-meansを使って空間中の点群を再帰的にクラスタリングしていくことで二分木をつくる．二分木がつくりたいので，Kの数はもちろん2．

クラスタリングと階層型K-Means tree

高次元にも有効っぽい

直接元論文を読んだわけはないのでアレなのだが，k-d treeと比較すると手法的に高次元にも有効そうである．

初期値依存をどうするか

二分木を使うので理想的な場合の計算量はO(log n)だが，実際の計算量はK-meansのセントロイドの与え方によってかなり変わりそうである．CRUX氏に聞いたところ，K-meansの代わりにK-means++を使用することでかなり良い結果が出るとのこと．