) kd-tree 2 kd-tree

情報システム基礎論２：第 7 回 (担当：古賀)
kd-tree
2014 年 6 月 3 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
はじめに
1
これまで検索対象は 1 次元データ、つまりスカラ量であった。今回は 2 次元データ、3 次元データといっ
たベクトルデータ検索を考える。ベクトルデータを検索するためのデータ構造である kd-tree を紹介する。
• d: 次元数
2
kd-tree
kd-tree(k dimensional tree) は 2 分探索木を多次元用に拡張したもの。
• S = {v1 , v2 , · · · , vn }: d 次元ベクトルの集合。S を kd-tree に登録する。
2.1
基本アイデア
20
9
5
30
16
35
図 1: 1 次元の 2 分探索木
1 次元の場合、2 分探索木では
• 根ノードが数直線を 2 分割する。
• 根以外のノードは部分数直線を 2 分割する。
9
20
30
図 2: 2 分探索木による数直線の分割
d 次元の場合は、
• 根ノードは d 次元空間を 2 分割すればよい。
1
• 根以外のノードは d 次元部分空間を 2 分割すればよい。
但し、分割方向に自由度がある → 分割方向を指定して分割する
2.2
アルゴリズム
S から kd-tree を作るアルゴリズム kd-tree(S) を示す。
Definition 1 d 次元ベクトル p = (p1 , p2 , . . . , pd ) とする。つまり、pi ：ベクトル p の第 i 次元の値。
Step 0: if S = φ, return 空の kd-tree
else if |S| = 1, return 1 ノードのみからなる kd-tree
/* 以下は S が 2 つ以上のデータを含む時 */
Step 1: S から根ノード root を選ぶ。また、分割次元 split を定める。
Step 2: S 0 = S − root とする。
Step 3: S 0 を 2 つに分割する。
0
Sleft
= {p ∈ S 0 |psplit ≤ rootsplit }
0
Sright
= {p ∈ S 0 |psplit > rootsplit }
0
Step 4: 左部分木 Tl を生成する。Tl = kd-tree(Sleft
)
0
Step 5: 右部分木 Tr を生成する。Tr = kd-tree(Sright )
Step 6: root が根で Tl と Tr をそれぞれ左子ノード、右子ノードとした木 T を構築。T を戻り値として
終了。
分割次元の選択: いくつかの方法が考えられる。
1. 次元を順番に選択。実装簡単。
2. 分散が大きい次元を選択
root の選択: 左右の部分木をバランスさせたい → 分割次元 split に関する S のメジアンを root とする。
例：2 次元の 4 点 (2,5)(6,3)(3,8)(8,9) に大して kd-tree を作った例。分割次元は y,x の順番で選択。
(8,9)
(3,8)
(2,5)
y
(6,3)
(3,8)
x
(2,5)
(6,3)
(8,9)
図 3: 2 次元 kd-tree
2
アルゴリズム kd-tree の計算量: root 選択時のメジアン計算はソーティングが必要なので O(n log n)。
0
ソーティング時に S 0
right と Sleft を決定できる。また、kd-tree の高さは O(log n)。よって、計算量は
O(n log n × log n) = O(n log2 n).
2.3
検索操作と挿入操作
検索操作 access(q) は通常の 2 分探索木とほぼ同じ。d 次元ベクトル q と kd-tree の内部ノードの分割次
元の値を比較し、左子ノードに進むか、右子ノードに進むかを決定。
挿入操作 insert(p) も 2 分探索木とほぼ同じ。但し、p の挿入により葉ノードが内部ノードに変化する場
合は分割次元の指定が必要となる。
バランスがとれた kd-tree では 1 回の検索、挿入の計算量は O(log n)。挿入操作を繰り返すと 2 分木の
バランスが崩れる可能性があるが、1 次元の場合とは異なり木の再構成は簡単でない。
3
類似検索
ここまで検索操作 access(q) とは q そのものをデータベース S から探すことであった。
一方、S から q に近いデータを探す操作を類似検索と呼ぶ。類似検索の結果は q と一致する必要はない。
q をクエリ (query) と呼ぶ。
1. NN-探索 (nearest neighbor search): q に最も近い S のデータを探す。D(p, q) は p,q 間の距離を表す。
return p ∈ S such that D(p, q) ≤ D(p0 , q) for any other p0 ∈ S
2. kNN-探索 (k nearest neighbor search): q に最も近いデータを S から k 個探す。
3. レンジ探索 (range search): q から距離 r 以内の S のデータを探す。
return p ∈ S such that D(p, q) ≤ r
以下では NN-探索について論じる。NN-探索は、q と S の全データとの距離を計算すれば自明にできる。
いかに距離計算の回数を減らせるかが NN-探索では重要
1 次元データならバイナリサーチで O(log n) 回の距離計算で可能。
3
a2 (8,9)
R2
a2(8,9)
R2
q
q
(2,5)
(2,5)
(6,3)
(6,3)
R1
R1
図 4: 類似検索で必要となる距離計算
kd-tree による NN-検索
4
4.1
アイデア
図 4 は 3 点からなる単純な 2 次元 kd-tree である。点 (2,5) によって、空間が 2 つの長方形 R1 と R2 に
分割されている。R1 の split 次元の値 < R2 の split 次元の値。q はクエリ。
q は上長方形 R2 に含まれるので R2 に含まれる点が q に近そう。そこで R2 に含まれる点の中で q に一
番近い点 a2 を求めてみる (図 4 では (8,9))。この時、
• q を中心とし半径 r = D(q, a2 ) の超球が下長方形 R1 と重ならない時、親ノード及び R1 内の点につ
いて距離計算は省略できる (図 4 左)。距離計算回数=1。
• R1 と重なる時は、親ノード及び R1 内の点に対して距離を調べる必要がある (図 4 右)。距離計算回
数=3。
4
4.2
アルゴリズム
アルゴリズム NNfind(q, S, R, root) (簡易版)
• 入力：(1) クエリ q, (2) データ集合 S, (3)d 次元超直方体 R, (4)kd-tree の根ノード root
• 出力：(1)S の中で一番 q に近い点 a, (2) その距離 dst。
Step 1: q が R1 と R2 のどちらに近いかを判定。
• Rn : q に近い超直方体
• Rf : q に遠い超直方体
if qsplit < rootsplit , Rn = R1 ; Rf = R2 ;
else Rn = R2 ; Rf = R1 ; /* qsplit ≥ rootsplit */
Step 2: Rn の中で一番 q に近い点 an 及びその距離 dstn を求める。これは再起呼出で記述できる。
• Sn : Rn に内包される S の部分集合
• Sf : Rf に内包される S の部分集合
(an , dstn )=NNfind(q, Sn , Rn ,root の Rn 側の子ノード);
Step 3: q を中心とする超球が Rf と重なるかで処理を切り替える。
if (q を中心とする半径 dstn の超球と Rf が重ならない){
return(an , dstn );
}
else{
親ノードとの距離 D(q, root) 計算。
/* Rf の中で一番 q に近い点 af 及びその距離 dstf を再起呼出で計算*/
(af , dstf )=NNfind(q, Sf , Rf ,root の Rf 側の子ノード);
dst = min{dstn , D(q, root), dstf };
a は dst に対応する点;
return(a, dst);
}
———————————————————
再起できないケース: Step 1 の前に記述する。
Step 0:
if(root=null) return(null,∞);
if(root が葉ノード) return(root, D(q, root))
• Rn ,Rf を「q から近い超直方体」、「q から遠い超直方体」としたのは再起呼出時に q が R に含まれ
ないケースが発生するため。図 5 参照。
5
R
Rf
(8,9)
Rn
(3,8)
(2,5)
Rn
R
(8,9)
Rf
(3,8)
(2,5)
q
(6,3)
q
(6,3)
図 5: 再起呼出時の処理
4.2.1
簡易版の改良
Step 3 で q を中心とする超球の半径を dstn としているのは無駄。過去に見付かった q へ最も近い点ま
での距離を max dist とし、半径 max dist の超球を使えばよい。図 6 参照。dstn を半径とする超球は Rf
と重なるが、max dist を半径とする超球は Rf と重ならない。
R
Rf
(8,9)
Rn
(3,8)
dstn
(2,5)
q
max_dist
(6,3)
R1
図 6: 簡易版の無駄な処理
NNfind の最終的なアルゴリズムを 7 ページに示す。下線が付いた部分が簡易版との差分。
4.3
実行時間
NNfind の実行時間 = log n + 調べる超直方体の数。
右辺第 1 項は kd-tree 上で q を検索して葉に到達するまでの時間。右辺第 2 項は S に含まれる点の分布に
依存。S の中で q に最も近い点を a とすると、q を中心とする半径 D(q, a) の超球と重なる超直方体は少な
くとも調べなければならない。
• D(q, a) 小 → 調べる超直方体数小。例えば、R の中にデータが高密度で万遍なく分布する場合。
• D(q, a) 大 → 調べる超直方体数大
実験的に実行時間は
• 低次元空間であれば n にはあまり依存しない。
6
• 空間次元数 d には指数的に依存。
アルゴリズム NNfind(q, root)
• 入力：(1) クエリ q, (2)kd-tree の根ノード root
• 出力：(1)S の中で一番 q に近い点 a, (2) その距離 dst。
Step 0: /* 再起できないケースの処理 */
if(root=null) return(null,∞);
if(root が葉ノード) {
if(D(q, root) < max dist) max dist = D(q, root);
return(root, D(q, root));
}
Step 1: q が R1 と R2 のどちらに近いかを判定。
• Rn : q に近い超直方体
• Rf : q に遠い超直方体
if qsplit < rootsplit , Rn = R1 ; Rf = R2 ;
else Rn = R2 ; Rf = R1 ; /* qsplit ≥ rootsplit */
Step 2: Rn の中で一番 q に近い点 an 及びその距離 dstn を求める。これは再起呼出で記述できる。
• Sn : Rn に内包される S の部分集合
• Sf : Rf に内包される S の部分集合
(an , dstn )=NNfind(q,root の Rn 側の子ノード);
Step 3: q を中心とする超球が Rf と重なるかで処理を切り替える。
if (q を中心とする半径 max dist の超球と Rf が重ならない){
return(an , dstn );
}
else{
親ノードとの距離 D(q, root) 計算。 if(D(q, root) < max dist) max dist = D(q, root);
/* Rf の中で一番 q に近い点 af 及びその距離 dstf を再起呼出で計算*/
(af , dstf )=NNfind(q,root の Rf 側の子ノード);
dst = min{dstn , D(q, root), dstf };
a は dst に対応する点;
return(a, dst);
}
7
kd-tree での NN 探索がうまくいく例といかない例
Andrew Moore, ”An introductory tutorial on kd-trees”, Technical Report No.209, Computer Laboratory, University of Cambridge, 1991 より引用。
良い例
悪い例
8

Download Report