kd木

kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。

kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される^[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造をkdトライと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある^[2]。

kd木上の操作

kd木の構築

軸に対応した分割平面の選択方法は様々なものがあり、kd木の構築方法も様々である。典型的なkd木の構築方法は以下のようになる。

木構造を下降すると共に、分割平面を選択する軸を巡回するようにする。例えば、根においてx軸に垂直な平面とし、根の子ではy軸に垂直な平面とし、根の孫ではz軸に垂直な平面とする、というように軸を巡回するように選択していく。
各ステップで、分割平面生成で選択される点は、kd木に入れる全ての点の対応する軸の座標値の中央値となる点とする。なお、前提として全ての点の集合がアルゴリズムの先頭で得られるものとする。

この方法では平衡kd木が得られ、各葉ノードと根との距離は等しくなる。しかし平衡木があらゆる応用において最適とは限らない。

また、常に中央値となる点を選択することが求められているわけではない。中央値を気にしない場合、単に平衡木となることが保証されないだけである。中央値を選択するアルゴリズムやソートをしない場合のヒューリスティックとしては、固定個の点を無作為に選択し、それらの中の中央値を選んで分割するという方式がある。実用上はこの技法で十分平衡的な木が得られる。

n個の点のリストを与えられたとき、以下のアルゴリズムで平衡kd木を構築できる。

function kdtree (list of points pointList, int depth)
{
    if pointList is empty
        return nil;
    else
    {
        // 深さに応じて軸を選択し、軸が順次選択されるようにする
        var int axis := depth mod k;

        // 点のリストをソートし、中央値の点を選択する
        select median from pointList;

        // ノードを作成し、部分木を構築する
        var tree_node node;
        node.location := median;
        node.leftChild := kdtree(points in pointList before median, depth+1);
        node.rightChild := kdtree(points in pointList after median, depth+1);
        return node;
    }
}

中央値より後ろ（after）の点には、中央値以上の座標値の点を含ませるのが一般的である。別の手法として、他の次元で点を比較する「スーパーキー(superkey)」関数を定義する方法もある。他にも、中央値に等しい点を両側に属させることもありうる。

このアルゴリズムをPythonで実装すると次のようになる。

class Node:pass

def kdtree(pointList, depth=0):
    if not pointList:
        return

    # 深さに応じて軸を選択し、軸が順次選択されるようにする
    k = len(pointList[0]) # 全ての点が同じ次元を持つと仮定
    axis = depth % k

    # 点のリストをソートし、中央値の点を選択する
    pointList.sort(key=lambda x:x[axis])
    median = len(pointList)/2 # 中央値を選択

    # ノードを作成し、部分木を構築する
    node = Node()
    node.location = pointList[median]
    node.leftChild = kdtree(pointList[0:median], depth+1)
    node.rightChild = kdtree(pointList[median+1:], depth+1)
    return node

このアルゴリズムは任意のノードについて不変条件を生成し、左の部分木にある全ノードは分割平面の一方の側にあり、右の部分木にある全ノードは同じ分割平面のもう一方の側にある。分割平面上にある点はどちらの側にも出現する可能性がある。あるノードの分割平面はそのノードに対応した点を通る（上記コードでは node.location で表されている）。

kd木への要素追加

kd木への点の追加は、他の木構造への要素の追加と同じように行える。まず、木の走査を根から開始し、追加しようとしている点が対応する座標値に対して右側なのか左側によって右または左の子ノードへと移っていく。葉ノードに到達したら、同様にそのノードに対応する点の座標値と比較して右または左に子ノードを追加する。

kd木からの要素削除

kd木から1つの点を削除する場合、不変量が維持されるようにしなければならない。最も簡単な方法は、削除したい点に対応するノードから下の全ノードについて、対応する全ての点についてkd木を再構築することである。ノードの軸およびピボット値を保持する必要がある。

kd木の平衡化

kd木の平衡化は注意を要する。kd木は多次元に渡ってソートされているため、一般的な木の回転 (tree rotation) を行って平衡化すると、不変量が保持されなくなる。

kd木での最近傍

kd木に含まれない点が与えられ、その点に最も近いkd木上の点を探す問題を考える（最近傍探索）。この場合、単純なテストで木の大部分を捨てられることを利用する。この場合、木構造を深さ優先探索で走査し、各段階で最短距離の近似計算を行う。アルゴリズム上より近傍の点がないと判断されたとき、最近傍が決定され、終了する。

まず、最短距離を無限としておいて、根ノードを調べる。次に、与えられた点を含む右または左の部分領域（それぞれ超矩形になっている。3次元の場合は直方体）を探す。これを繰り返していって、与えられた点を含む最小の領域（葉ノード）を求める。次に上方向に再帰的に、親ノードのもう一方の領域がより近い点を持っていないかを調べていく。これは、与えられた点を中心として半径が現在の最近傍の点までの距離となる超球（3次元なら単なる球）と各領域の超矩形とが重なるかどうかを調べることでなされる。まだ調べていない矩形がこの球と重ならないなら、その矩形がより近い近傍点を含むことはない。これを全ての領域が捨てられるか探索されるまで繰り返す。そして、最終的に残った点が最近傍となる。さらにこのアルゴリズムは、単に最近傍を求めるだけでなく、最近傍の距離の二乗も求められる。このアルゴリズムの時間計算量は O(logN) である。

このアルゴリズムは簡単な修正で拡張する方法がいくつか存在する。

近似最近傍探索は、単に木構造上で調べる点の個数の上限を決めておくか、探索にかかる時間を決めておいて割り込むことで実現される（後者はハードウェアによる実装にふさわしい）。木構造にすでに含まれている座標の点の最近傍を求める場合、常に距離が0の点が存在するはずであり、近似によって探索を打ち切るとそれを求めることができないという問題がある。

近似最近傍探索は劇的に計算時間を抑えられるため、ロボット工学などのリアルタイム性が要求される場合によく使われる。

高次元データ

kd木は高次元空間での最近傍探索には適さない。次元を D としたとき、点の個数 N は N >> 2^D となっているのが望ましい。そうでないと、高次元データをkd木で表すと、最近傍探索でほとんどの点を調べることになり、力まかせ探索とあまり差がない。高次元データでの最近傍探索問題はNP困難問題と似ていると考えられている^[3]。そのため近似最近傍探索の手法が使われることが多い。

計算量

n個の点から静的なkd木を構築する場合、中央値を求めるアルゴリズムで変わる。
- 単純にO(n log n) のソートを使って中央値を各レベルについて計算するとすると、全体として O(n log ² n) の時間がかかる。
- より高速な線形中央値探索アルゴリズム（例えば Cormen et al^[4]）を使う場合、計算量は O(n log n) になる。
平衡kd木への新たな点の挿入には、O(log n) の時間がかかる。
平衡kd木からの点の削除には、O(log n) の時間がかかる。
平衡kd木である軸に平行な範囲にある点を求める場合、 O(n^1-1/d +k) の時間がかかる。ここで、k は報告される点の個数、d は kd木の次元である。

派生

kd木が点の代わりに矩形または超矩形を格納する場合がある。2次元の矩形は4次元のオブジェクト (x_low, x_high, y_low, y_high) とみなすことができる。したがって、矩形範囲探索は、その矩形範囲に重なる全ての矩形を求める問題となる。木構造は通常、各葉ノードが矩形に対応するように構築される。直交範囲検索では、中央値との比較に反対側の座標値を用いる。例えば、現在のレベルの分割が x_high に沿って行われているなら、探索矩形の x_low の座標値を用いる。中央値が探索矩形の x_low より小さいなら、左側の分枝には探索矩形と重なるものがないと判断でき、刈り取ることができる。さもなくば、両方の分枝を走査する必要がある。これの1次元の特殊ケースを区間木と呼ぶ。

脚注

^ Preparata, Franco P., Shamos, Michael Ian. Computational Geometry: An Introduction. Springer-Verlag, 1985: ISBN 3-540-96131-3
^ de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. Computational Geometry: Algorithms and Applications. Springer-Verlag, 1997: ISBN 3-540-65620-0
^ Piotr Indyk. Nearest neighbors in high-dimensional spaces. Handbook of Discrete and Computational Geometry, chapter 39. Editors: Jacob E. Goodman and Joseph O'Rourke, CRC Press, 2nd edition, 2004.
^ Cormen, T. H., Leiserson, C. E., Rivest, R. L., Introduction to Algorithms. 第10章中央値と順序統計量. McGraw-Hill, 1996: ISBN 0-07-013143-0

参考文献

Bentley, J. L. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sep. 1975), 509–517.
Bentley, J. L. 1990. K-d Trees for Semidynamic Point Sets. SCG '90: Proc. 6th Annual Symposium on Computational Geometry (1990), 187–197
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000年). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0 Section 5.2: Kd-Trees, pp.99–105.

外部リンク

libkdtree++ - C++ で実装したオープンソースのkd木ライブラリ

[1] Preparata, Franco P., Shamos, Michael Ian. Computational Geometry: An Introduction. Springer-Verlag, 1985: ISBN 3-540-96131-3

[2] Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. Computational Geometry: Algorithms and Applications. Springer-Verlag, 1997: ISBN 3-540-65620-0

[3] Piotr Indyk. Nearest neighbors in high-dimensional spaces. Handbook of Discrete and Computational Geometry, chapter 39. Editors: Jacob E. Goodman and Joseph O'Rourke, CRC Press, 2nd edition, 2004.

[4] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Introduction to Algorithms. 第10章中央値と順序統計量. McGraw-Hill, 1996: ISBN 0-07-013143-0

[1]

[2]

[3]

[4]

kd木

目次