ボールツリーは、多次元空間内の点を、ボールと呼ばれる入れ子状の超球の階層に分割するために使用される二分木データ構造です。ツリー内の各ノードは、データ点のサブセットを含むボールを表し、ルートノードはすべての点を含みます。ツリーは、データ点を再帰的に2つのグループに分割し、各グループを独自のボールで囲むことで構築され、最大リーフサイズや最小ボール半径などの停止基準が満たされるまで続けられます。ボールツリーは主に、最近傍クエリ、類似性検索、カーネル密度推定を高速化するために使用され、機械学習アプリケーション、例えばデータ拡張やクラスタリングなどで一般的に利用されます。
代替の空間インデックス構造（k-dツリーなど）に対するボールツリーの主な利点は、高次元空間でのパフォーマンスです。k-dツリーは軸に平行な超平面を使用して空間を分割しますが、これは次元の呪いにより次元が増加するにつれて非効率になる可能性があります。一方、ボールツリーは、データの局所的な分布に適応する計量ボールを使用して分割します。この特性により、ボールツリーは、特にデータがクラスター構造または低い内在次元を持つ場合に、検索空間の大部分をより効果的に刈り込むことができます。その結果、ボールツリーは、ロボット工学、天文学、ニューラルネットワークのハイパーパラメータ調整など、さまざまな科学的および工学的な文脈で採用されています。
構造と構築
ボールツリーは、それぞれ中心と半径で表される一連の入れ子状のボールによって定義されます。中心は、多くの場合、ボール内に含まれる点の重心として選択され、半径は、そのボール内の任意の点までの中心からの最大距離です。ツリーは再帰的アルゴリズムを使用して構築されます。各ステップで、アルゴリズムは現在の中心から最も遠い点を選択し、次に最初に選択された点から最も遠い2番目の点を選択します。これらの2つの点はピボットとして機能し、残りの点を各ピボットへの近接性に基づいて2つのクラスターに分割します。このプロセスは、リーフノードが指定された数（通常は小さな定数）未満の点を含むようになるまで、結果として得られる各クラスターに対して繰り返されます。
ボールツリーの構築時間は、低次元のn個の点に対してO(n log n)ですが、距離計算のコストが増加するため、非常に高次元では低下する可能性があります。構築を改善するためのいくつかの戦略が存在します。これには、近似的最遠点選択の使用や、対数深度を保証するためのツリーのバランス調整が含まれます。計量の選択も構造に影響します。ユークリッド距離が一般的ですが、ボールツリーは、マンハッタン距離やミンコフスキー距離など、三角不等式を満たす任意の計量を使用して構築できます。
最近傍探索
ボールツリーの最も一般的な用途は、分類および回帰タスクの基本であるk近傍法（k-NN）探索です。探索アルゴリズムはツリーを再帰的にトラバースし、これまでに見つかった最良の候補点の優先度キューを維持します。各ノードで、アルゴリズムはクエリ点からノードのボール中心までの距離を計算します。この距離からボールの半径を引いた値が、現在のk番目の最近傍距離よりも大きい場合、そのボール内の点は現在の最良値よりも近くに存在できないため、サブツリー全体を刈り込むことができます。この刈り込みは、ボール内の任意の点がクエリから少なくとも特定の距離だけ離れていることを保証する三角不等式を利用しています。
実際には、ボールツリーは、k-NNの計算複雑性を、クエリあたりO(n)（ナイーブスキャン）から、低い内在次元を持つデータに対して平均でおよそO(log n)に削減できます。しかし、次元が増加するにつれて、刈り込み効率は低下します。研究者は、クエリツリーとデータツリーを同時にトラバースするデュアルツリーアルゴリズムなどのバリエーションを提案し、高次元設定でのパフォーマンスをさらに向上させています。これらの技術は、scikit-learnやAmazon Web Services SageMakerなどの人工知能フレームワークで使用されるライブラリに統合されています。
アプリケーション
ボールツリーは、機械学習パイプラインで広く使用されています。カーネル密度推定では、ボールツリーは、個々の点ではなく点のクラスターからの寄与を集約することにより、局所密度推定の計算を高速化します。また、トランスフォーマーモデルのクロスアテンションメカニズムやマルチヘッドアテンションアーキテクチャにも登場しますが、関連するキーの効率的な取得が有益となる場合があります。ただし、従来の実装では高密度アテンションが使用されます。
機械学習以外では、ボールツリーは、ロボット工学の経路計画や衝突検出、コンピュータグラフィックスのレイトレーシング、地理情報システムの空間クエリに使用されています。例えば、ウェイモや他の自動運転車システムは、地図フィーチャの高速な最近傍取得のためにセンサーデータをインデックス化する際にボールツリーを使用します。天文学では、ボールツリーは高速な近接クエリによる星のカタログ化に役立ちます。その汎用性は、基礎となる計量の単純さと、ハッシュベースの近似手法とは異なり、正確なクエリ結果を保証することに由来しています。
他の構造との比較
ボールツリーは、k-dツリー、Rツリー、局所性鋭敏型ハッシング（LSH）としばしば比較されます。k-dツリーは軸に平行な分割によって空間を分割し、低次元（通常20未満）では効率的ですが、高次元では過剰なバックトラッキングが発生するという欠点があります。ボールツリーは軸に平行な分割を必要とせず、データの形状に適応できます。データベースの境界矩形に主に使用されるRツリーは、任意の計量に対しては柔軟性が低くなります。LSHは近似結果を提供し、非常に高次元では高速ですが、正確な最近傍を保証しません。ボールツリーは中間的な選択肢を提供します。つまり、k-dツリーよりも高次元でのパフォーマンスが優れた正確なクエリを実現しますが、非常に高次元では線形探索を依然として上回ることはありません。
制限と拡張
ボールツリーの主な制限は、次元の呪いです。次元の数が増加するにつれて、周囲の空間に対するボールの体積の比率が非常に小さくなり、刈り込みが非効率になります。このような場合、LSHのような近似手法が好まれます。さらに、ボールツリーは静的構造であり、点の挿入や削除にはツリーの再構築が必要なため、バランスの取れたバリアントを使用しない限り、動的データセットには適していません。
拡張には、高レベルではボール分割を使用し、低レベルでは軸に平行な分割を使用するk-dツリーボールハイブリッドや、特定のデータ仮定の下でほぼ対数時間のクエリ時間を保証するカバリングツリーが含まれます。適応計量や学習インデックスに関する研究も続いており、深層学習モデルが分割境界を予測しますが、そのようなアプローチは依然としてニッチな分野です。
関連項目
- k-dツリー
- 最近傍探索
- メトリックツリー
- 次元削減