2009-12-26

読書メーター

日記

以下のWebサービスに登録してみました。

読書メーター

http://book.akahoshitakuya.com/ (マイページ)

鑑賞メーター

http://video.akahoshitakuya.com/ (マイページ)

「趣味は読書と映画鑑賞です」などと公言している割には忙しさにかまけてそれらを満喫していなかったのですが、これを機にまた始めようと思います。

2009-12-13

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

Algorithm

メモ書き．

階層型 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++を使用することでかなり良い結果が出るとのこと．

2009-12-12

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

Algorithm

メモ書き．

全探索 (線形探索)

最も単純な方法は全探索である．注目点から空間中の全点の距離を測り，その距離が最小になる点を最近傍点とする．なお，計算量は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 となっていることが望ましい．