kdツリー

k -d ツリー
3 次元のk -d ツリー。最初の分割 (赤い垂直面) により、ルート セル (白) が 2 つのサブセルに分割され、各サブセルは (緑の水平面によって) 2 つのサブセルに分割されます。最後に、4 つのセルが (4 つの青い垂直面によって) 2 つのサブセルに分割されます。これ以上の分割は行われないため、最後の 8 つはリーフ セルと呼ばれます。
タイプ	多次元BST
発明された	1975
発明者	ジョン・ルイス・ベントレー
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 検索 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 入れる ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 消去 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 空間の複雑さ 空間 ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

ウィキメディア・コモンズには、 kd ツリーに関連するメディアがあります。

コンピュータサイエンスにおいて、k -dツリー（ k次元ツリーの略）は、k次元空間内の点を整理するための空間分割 データ構造です。k次元とは、正確にk本の直交軸または任意の数の次元の空間に関係するものです。^[1] k -dツリーは、次のようないくつかのアプリケーションに役立つデータ構造です。

• 多次元検索キーを含む検索（範囲検索や最近傍検索など）
• ポイントクラウドを作成します。

k -d ツリーは、バイナリ空間分割ツリーの特殊なケースです。

k -d ツリーは、すべてのノードが k 次元の点であるバイナリ ツリーです。[ 2 ]すべての非^{リーフノードは、}半空間と呼ばれる 2 つの部分に空間を分割する分割超平面を暗黙的に生成すると考えられます。この超平面の左側の点は、そのノードの左サブツリーで表され、超平面の右側の点は右サブツリーで表されます。超平面の方向は、次の方法で選択されます。ツリー内のすべてのノードは、k次元の 1 つに関連付けられ、超平面はその次元の軸に垂直になります。したがって、たとえば、特定の分割に対して "x" 軸が選択された場合、サブツリー内のノードよりも小さい "x" 値を持つすべてのポイントは左サブツリーに表示され、大きい "x" 値を持つすべてのポイントは右サブツリーに表示されます。このような場合、超平面はポイントの x 値によって設定され、その法線は単位 x 軸になります。^[3]

軸に沿った分割面を選択する方法は多数あるため、 k -dツリーを構築する方法も多数ある。k- dツリー構築の標準的な方法には、以下の制約がある。^[4]

• ツリーを下に移動すると、分割平面の選択に使用される軸が循環します。(たとえば、3 次元ツリーでは、ルートはxに揃えられた平面を持ち、ルートの子は両方ともyに揃えられた平面を持ち、ルートの孫はすべてzに揃えられた平面を持ち、ルートのひ孫はすべてxに揃えられた平面を持ち、ルートの玄孫はすべてyに揃えられた平面を持ち、というようになります。)
• ポイントは、分割平面を作成するために使用されている軸の座標に関して、サブツリーに配置されるポイントの中央値を選択することによって挿入されます。( nポイントのセット全体を事前にアルゴリズムに入力するという前提に注意してください。)

この方法により、各リーフ ノードがルートからほぼ同じ距離にあるバランスの取れた k -d ツリーが作成されます。ただし、バランスの取れたツリーは必ずしもすべてのアプリケーションに最適であるとは限りません。

中央点を選択する必要がないことに注意してください。中央点を選択しない場合、ツリーがバランスが取れているという保証はありません。複雑な中央値検索アルゴリズム^{[5] [6]をコーディングしたり、}ヒープソートやマージソートなどのソートを使用してn 個のポイントすべてをソートしたりすることを避けるために、ランダムに選択された固定数のポイントをソートし、それらのポイントの中央値を分割面として使用することが一般的な方法です。実際には、この手法により、バランスの取れたツリーが得られることがよくあります。 ${\displaystyle O(n)}$ ${\displaystyle O(n\log(n))}$

n 個のポイントのリストが与えられた場合、次のアルゴリズムは中央値検索ソートを使用して、それらのポイントを含むバランスの取れたk -d ツリーを構築します。

関数kdtree (ポイントのリストpointList、int depth)
{
    // 軸がすべての有効な値を循環するように、深さに基づいて軸を選択します。var 
    int axis :  = depth mod k;

    // ポイント リストを並べ替え、ピボット要素として中央値を選択します。pointList
    から軸によって中央値を選択します。

    // ノードを作成し、サブツリーを構築します
    node.location := 中央値;
    node.leftChild := kdtree( pointList内の中央値の前の点、深さ + 1);
    node.rightChild := kdtree( pointList内の中央値の後の点、深さ + 1);
    ノードを返します。
}

中央値の「後」のポイントには、現在の次元で中央値よりも厳密に大きいポイントのみが含まれるのが一般的です。現在の次元で中央値上にあるポイントについては、すべての次元でそれらを比較する関数を定義することができます。場合によっては、ポイントを「より小さい」サブセットと「より大きいか等しい」サブセットに分割するなどして、中央値に等しいポイントを中央値の片側に配置することもできます。

このアルゴリズムは、任意のノードについて、左のサブツリー内のすべてのノードが分割平面の一方の側にあり、右のサブツリー内のすべてのノードがもう一方の側にあるという不変条件を作成します。分割平面上にあるポイントは、どちらの側にも現れる可能性があります。ノードの分割平面は、そのノードに関連付けられたポイント (コードではnode.locationと呼ばれます) を通過します。

バランスのとれたk -d ツリーを構築するための代替アルゴリズムでは、ツリーを構築する前にデータを事前ソートします。次に、ツリーの構築中に事前ソートの順序を維持し、各細分レベルでの中央値の検索というコストのかかるステップを排除します。このようなアルゴリズム 2 つは、バランスのとれたk -d ツリーを構築して三角形をソートし、 3 次元コンピュータ グラフィックスのレイ トレーシングの実行時間を改善します。これらのアルゴリズムは、k -d ツリーを構築する前にn 個の三角形を事前ソートし、最良のケースでは時間内にツリーを構築します。 ^{[7] [8]} バランスのとれたk -d ツリーを構築して点をソートするアルゴリズムの最悪のケースの複雑度は です。^{[9] [10]}このアルゴリズムは、ツリーを構築する前に、ヒープソートやマージソートなどのソートを使用して、k次元のそれぞれでn個の点を事前ソートします。次に、ツリーの構築中にこれらのk個の事前ソートの順序を維持し、各細分レベルでの中央値の検索を回避します。 ${\displaystyle O(n\log n)}$${\displaystyle O(kn\log(n))}$${\displaystyle O(n\log(n))}$

他の検索ツリーに要素を追加するのと同じ方法で、 k -d ツリーに新しいポイントを追加します。まず、ルートから始めてツリーをトラバースし、挿入するポイントが分割面の「左側」にあるか「右側」にあるかに応じて、左または右の子に移動します。子を配置するノードに到達したら、ノードの分割面のどちら側に新しいノードが含まれているかに応じて、新しいポイントをリーフ ノードの左または右の子として追加します。

このようにポイントを追加すると、ツリーのバランスが崩れ、ツリーのパフォーマンスが低下する可能性があります。ツリーのパフォーマンス低下率は、追加されるツリー ポイントの空間分布と、ツリー サイズに対する追加ポイントの数によって異なります。ツリーのバランスが崩れすぎると、最近傍検索など、ツリーのバランスに依存するクエリのパフォーマンスを回復するために、ツリーのバランスを再調整する必要がある場合があります。

不変条件を破ることなく既存のk -dツリーからポイントを削除する最も簡単な方法は、対象ノードの子からすべてのノードとリーフのセットを作成し、ツリーのその部分を再作成することです。^[11]

別のアプローチは、削除された点の代わりを見つけることです。^[12]まず、削除する点を含むノードを見つけます。R がリーフノードである基本ケースでは、置き換えは必要ありません。一般的なケースでは、をルートとするサブツリーから置き換え点、たとえば を見つけます。 に格納されている点をで置き換えます。次に、 を再帰的に削除します。 ${\displaystyle R}$${\displaystyle p}$${\displaystyle R}$${\displaystyle R}$${\displaystyle p}$${\displaystyle p}$

置換ポイントを見つけるには、（たとえば）を判別し、右の子がある場合は、右の子をルートとするサブツリーから最小値を持つポイントを見つけます。それ以外の場合は、左の子をルートとするサブツリーから 最大値を持つポイントを見つけます。${\displaystyle R}$${\displaystyle x}$${\displaystyle R}$${\displaystyle x}$${\displaystyle x}$

k -d ツリーは複数の次元でソートされるため、k -d ツリーのバランスをとるには注意が必要です。ツリー回転技術を使用してバランスをとると不変条件が破られる可能性があるためです。

バランスk -d ツリーにはいくつかのバリエーションがあります。分割k -d ツリー、疑似k -d ツリー、KDB ツリー、hB ツリー、Bkd ツリーなどがあります。これらのバリエーションの多くは適応 kd ツリーです。

最近傍探索(NN) アルゴリズムは、ツリー内で指定された入力ポイントに最も近いポイントを見つけることを目的としています。この探索は、ツリーの特性を使用して探索空間の大部分をすばやく排除することで効率的に実行できます。

k -d ツリーで最も近い近傍を検索する手順は次のとおりです。

1. アルゴリズムは、ルート ノードから開始して、検索ポイントが挿入される場合と同じように、ツリーを再帰的に移動します (つまり、ポイントが分割次元の現在のノードより小さいか大きいかに応じて左または右に移動します)。
2. アルゴリズムがリーフ ノードに到達すると、ノード ポイントをチェックし、距離が「現在の最適」よりも良い場合は、そのノード ポイントが「現在の最適」として保存されます。
3. アルゴリズムはツリーの再帰を解き、各ノードで次の手順を実行します。
   1. 現在のノードが現在の最適ノードよりも近い場合は、それが現在の最適ノードになります。
   2. このアルゴリズムは、分割平面の反対側に、現在の最良点よりも検索点に近い点があるかどうかを確認します。概念的には、これは、分割超平面を、現在の最短距離に等しい半径を持つ検索点の周りの超球と交差させることによって行われます。超平面はすべて軸が揃っているため、これは、検索点の分割座標と現在のノード間の距離が、検索点から現在の最良点までの距離 (全体の座標) よりも短いかどうかを確認する単純な比較として実装されます。
      1. 超球面が平面を横切る場合、平面の反対側により近い点が存在する可能性があるため、アルゴリズムは、検索全体と同じ再帰プロセスに従って、現在のノードからツリーの別のブランチを下に移動して、より近い点を探す必要があります。
      2. 超球面が分割面と交差しない場合は、アルゴリズムはツリーを上って進み続け、そのノードの反対側にあるブランチ全体が削除されます。
4. アルゴリズムがルート ノードに対してこのプロセスを終了すると、検索が完了します。

一般的に、アルゴリズムは平方根の計算を避けるために、比較に二乗距離を使用します。さらに、比較のために変数に現在の最適距離の二乗を保持することで、計算を節約できます。

このアルゴリズムは、簡単な変更を加えることで、いくつかの方法で拡張できます。1つの点だけではなく、現在のk 個のベスト点を維持することで、点に最も近いk個の近傍点を提供できます。分岐は、 k個の点が見つかり、分岐が現在のk 個のベスト点のいずれよりも近い点を持つことができない場合にのみ削除されます。

また、近似アルゴリズムに変換して、より高速に実行することもできます。たとえば、近似最近傍検索は、ツリー内で調べるポイントの数に上限を設定するか、リアルタイム クロックに基づいて検索プロセスを中断することによって実現できます (ハードウェア実装では、こちらの方が適している可能性があります)。ツリー内にすでに存在するポイントの最近傍は、距離がゼロのノードの改良を更新しないことで実現できます。その結果、これには、一意ではないが元の検索ポイントと同じ場所にあるポイントを破棄するという欠点があります。

近似最近傍法は、最適なポイントを徹底的に検索しないことにより速度が大幅に向上するため、ロボットなどのリアルタイム アプリケーションで役立ちます。その実装の 1 つが、best-bin-first searchです。

範囲検索は、パラメータの範囲を検索します。たとえば、ツリーに収入と年齢に対応する値が保存されている場合、範囲検索は、年齢が 20 ～ 50 歳で収入が 50,000 ～ 80,000 であるツリーのすべてのメンバーを検索するようなものです。kd ツリーは、ツリーの各レベルでドメインの範囲を半分に分割するため、範囲検索を実行するのに役立ちます。

二分探索木の解析により、 n個のノードを含むk次元k -d木における範囲探索の最悪ケースの時間は、次の式で与えられることがわかった。^[13]

${\displaystyle t_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}$

ランダムに分布した点の場合、最も近い点を見つけることは平均に対する操作ですが、一般的な分析は難しいです。 ^[14]${\displaystyle O(\log(n))}$

高次元空間では、次元の呪いにより、アルゴリズムは低次元空間よりも多くの枝を訪問する必要があります。特に、点の数が次元の数よりわずかに多い場合、アルゴリズムはすべての点の線形検索よりもわずかに優れているだけです。一般的な規則として、次元がkの場合、データ内の点の数nは である必要があります。そうでない場合、k -d ツリーを高次元データで使用すると、ツリー内のほとんどの点が評価され、効率は網羅的検索よりも良くありません。^[15]また、十分に高速な回答が必要な場合は、代わりに近似最近傍法を使用する必要があります。 ${\displaystyle n\gg 2^{k}}$

さらに、低次元空間であっても、クエリ ポイントのk近傍点間の平均ペアワイズ距離が、クエリ ポイントと各k近傍点間の平均距離よりも大幅に短い場合、クエリ ポイントから各近傍点までの距離が同じ大きさであるため、近傍点検索のパフォーマンスは線形に向かって低下します。(最悪の場合、原点を中心とした球面上に分散した点のクラウドを考えてみましょう。すべての点は原点から等距離にあるため、原点から近傍点を検索するには、球面上のすべての点を反復処理して近傍点を特定する必要があります。この場合、近傍点は一意ではありません。)

最悪の場合のk -d ツリー検索の潜在的に重大なパフォーマンス低下を軽減するために、ツリー検索アルゴリズムに最大距離パラメータを指定し、ツリーの特定のブランチ内の最も近いポイントがこの最大距離よりも近くなることができない場合は、再帰検索を刈り込むことができます。これにより、最近傍検索で最近傍が返されない可能性があり、これは、クエリ ポイントからこの最大距離内にポイントがないことを意味します。

• n 個のポイントから静的なk -d ツリーを構築する場合、最悪の場合の複雑さは次のようになります。
  • ヒープソートやマージソートなどのO ( n log n )ソートを使用して新生ツリーの各レベルで中央値を見つける場合はO ( n log ² n ) 。
  • O ( n log n )：O ( n )の中央値の中央値アルゴリズム^{[5] [6]}を使用して新生木の各レベルで中央値を選択する場合。
  • k次元木を構築する前に、ヒープソートやマージソートなどのO ( n log n )ソートを使用して、k次元のそれぞれでn個の点が事前にソートされている場合、O ( kn log n )となる。^[10]
• バランスのとれたk -d ツリーに新しいポイントを挿入するには、O (log n )時間がかかります。
• バランスのとれたk -d ツリーからポイントを削除するには、O (log n )時間がかかります。
• バランスのとれたk -dツリーで軸に平行な範囲を照会するにはO ( n1−1 ^/k + m )の時間がかかります。ここで、mは報告されたポイントの数、kはk -dツリーの次元です。
• ランダムに分散された点を持つバランスのとれたk -d ツリーで 1 つの最近傍を見つけるには、平均してO (log n )の時間がかかります。

k -d 木には、点の代わりに長方形や超長方形を含めることもできます。^{[16] [17]}したがって、範囲検索は、検索長方形と交差するすべての長方形を返す問題になります。木は、すべての長方形を葉にして通常の方法で構築されます。直交範囲検索では、中央値と比較するときに反対の座標が使用されます。たとえば、現在のレベルが x_{高に沿って分割されている場合、検索長方形の x低}座標を確認します。中央値が検索長方形の x_低座標よりも小さい場合、左の枝の長方形は検索長方形と交差することはないため、剪定できます。それ以外の場合は、両方の枝を走査する必要があります。1次元の特殊なケースである 間隔木も参照してください。

また、ポイントがリーフのみに格納されたk -d ツリーを定義することもできます。^[4]この形式のk -d ツリーでは、標準的な中央分割以外のさまざまな分割メカニズムを使用できます。中点分割ルール^[18]では、ポイントの分布に関係なく、検索対象の空間の最長軸の中央を選択します。これにより、アスペクト比が最大 2:1 になることが保証されますが、深さはポイントの分布に依存します。スライディング中点と呼ばれるバリエーションでは、分割の両側にポイントがある場合のみ、中央で分割します。それ以外の場合は、中央に最も近いポイントで分割します。Maneewongvatana と Mount は、これが一般的なデータ セットで「十分に優れた」パフォーマンスを提供することを示しています。

スライディングミッドポイントを使用すると、近似最近傍クエリに で回答できます。この方法では、近似範囲カウントに で回答できます。 ${\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}$${\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}$

類似バリエーション:

• 暗黙のk -d ツリー、明示的に格納された分割セットではなく、暗黙の分割関数によって定義されたk -d ツリー
• 最小/最大k -d ツリー、各ノードに最小値と最大値を関連付けるk -d ツリー
• 緩和k -d木、各ノードの判別式が任意であるk -d木

関連するバリエーション:

• 四分木、2次元に同時に分割する空間分割構造で、各ノードには4つの子ノードがある。
• オクトツリーは、3次元に同時に分割する空間分割構造で、各ノードには8つの子ノードがあります。
• ボールツリー、最近傍探索に便利な多次元空間分割
• Rツリーと境界区間階層、重なり合う領域を持つ点ではなくオブジェクトを分割するための構造
• ヴァンテージポイントツリーは、データを分割するために超平面ではなく超球を使用するk -dツリーの変種である。

k -d ツリー で解決できる問題:

• 再帰分割、 k -d木に似た統計的決定木を構築するための手法
• クレーの測度問題、長方形の和集合の面積を計算する問題、k -d 木を使って解ける問題
• ギロチン問題、与えられた長方形の集合を包含するのに十分な大きさのセルを持つk -d 木を見つける問題

• ALGLIB には、 k -d ツリーベースの最近傍法と近似最近傍法のアルゴリズムのC#およびC++実装があります。
• 計算アルゴリズム ライブラリCGAL には、 k -d ツリー ベースの最近傍法、近似最近傍法、および範囲検索アルゴリズムの実装があります。
• 科学計算用のPythonライブラリであるSciPy には、 k -d ツリー ベースの最近傍検索アルゴリズムの実装が含まれています。
• 機械学習用の Python ライブラリであるscikit-learnには、最近傍検索と半径近傍検索をサポートするk -d ツリーの実装が含まれています。