List1には多数 (~7^10) の N 次元ポイント (N <=10) が含まれ、List2には N 次元ポイント (N <=10)と同数またはそれ以下の数が含まれます。
私の仕事は次のとおりです: List1 のすべての点について、List2 のどの点が List1 の点に最も近いか (ユークリッド距離) を確認し、その後、いくつかの操作を実行したいと考えています。List1 に 50 個を超えるポイントがなかったときはネストされたループの方法で単純に実行してきましたが、7^10 ポイントの場合、明らかに多くの時間がかかります。
これを行う最速の方法は何ですか? 計算幾何学の概念は役に立ちますか?
編集: 私は次の場所にいます。List2から kd ツリーを構築し、 List1の各ポイントに対して最近傍検索を実行しています。最初に指摘したように、List1には 7^10 のポイントがあるため、すべてのペアに対してブルート フォース (ユークリッド距離法) を節約していますが、 List1の膨大な数のポイントが多くの時間を消費しています。これを改善する方法はありますか？
良い方法は、kd ツリーのようなものを使用して最近傍検索を実行することです。幸いなことに、このデータ構造を自分で実装する必要はありません。以前に実装されています。私はこれをお勧めしますが、他にもあります：
2 つの解の点の分布について何も知らずに、どちらが最も効率的なアルゴリズムであるかを判断することはできません。しかし、最初の推測では...
最初のアルゴリズムは機能しません— 2 つの理由で: (1) 間違った仮定 - 境界ハルがばらばらであると仮定し、(2) 質問の誤解 - すべてのポイントのペアに対して最短エッジを見つけられません。
...2 つのセットの凸包を計算します。最も近い点は、2 つの重心間の線が通過する 2 つの包の超面上にある必要があります。
中心点を計算し、すべての点の質量が等しいと仮定して重心を計算し、中心から最も遠いものから最も遠いものへとリストを並べ替えることで、凸包を計算できます。次に、リスト内の最も離れた点を取得し、これを凸包に追加し、これまでに計算された凸包内にあるすべての点を削除します (これを行うには、10 次元超三角形を多数計算する必要があります)。リストに凸包上にないものがなくなるまで繰り返します。
2 番目のアルゴリズム: 部分的
List2 の凸包を計算します。List1 の各点について、点が凸包の外側にある場合、最初のアルゴリズムと同様に超面を見つけます。最も近い点はこの面上にある必要があります。顔の場合も同様です。内側にある場合でも、List1 からの点を越えて線を延長することで、ハイパーフェースを見つけることができます。最も近い点は、ハイパーフェースを含むボールの内側にあり、List2 の重心にある必要があります。ただし、ここでは、取得するための新しいアルゴリズムが必要です。最も近い点、おそらくkd-treeアプローチ。
パフォーマンス
List2 が、かなり斜めの形状を介して均等に分散または正規に分散されているようなものである場合、これは検討中のポイントの数を減らすのに適切であり、kd ツリーの提案と互換性があるはずです。
ただし、いくつかの恐ろしいワートのケースがあります。リスト 2 に、幾何学的中心がリストの重心であるトーラスの表面上のポイントのみが含まれている場合、凸包は計算に非常にコストがかかり、削減にはあまり役立ちません。検討中の点数。
私の評価
これらの種類の幾何学的手法は、他のポスターの kd-trees アプローチを補完するのに役立つ場合がありますが、適用する価値があるかどうかを判断するには、点の分布について少し知っておく必要があります。
(1 年後) 200M ポイントすべての 1M を調べた後、早期に終了する kd ツリーは、高次元ではるかに高速になる可能性があります。
結果は、データとメトリックに応じて、統計的に最も近い絶対値に近いだけです。フリーランチはありません。
(1M ポイントのサンプリングと、それらの 1M のみの kd ツリーのサンプリングは、まったく異なり、さらに悪いことに注意してください。)
FLANNは、dim=128 の画像データに対してこれを行います。私は opencv を信じています。高速で堅牢なSciPy cKDTreeのローカル mod に も cutoff= があります。
kd-tree はかなり高速です。この論文のアルゴリズムを使用しましたが、うまく機能しますBentley - 半動的点集合の Kd 木
周辺にはライブラリがあると確信していますが、時々何が起こっているのかを知るのは良いことです.Bentleyはそれをうまく説明しています.
基本的に、ツリーを検索するにはいくつかの方法があります。最も近い N 個の隣接、特定の半径内のすべての隣接、半径内の最も近い N 個の隣接。境界のあるオブジェクトを検索したい場合があります。
アイデアは、kdTree が空間を再帰的に分割するというものです。各ノードは、現在の空間のいずれかの次元で軸に沿って 2 つに分割されます。理想的には、ノードの最長の次元に対して垂直に分割されます。各バケットに約 4 つのポイントが入るまで、スペースを分割し続ける必要があります。
次に、すべてのクエリ ポイントについて、再帰的にノードにアクセスするときに、現在の特定のノードの隔壁までの距離を確認します。隔壁までの距離が検索半径より近いです。壁が半径を超えている場合は、現在いるノードの子を検索するだけです。
バケット (リーフ ノード) に到達したら、そこにあるポイントをテストして、それらが半径内にあるかどうかを確認します。
最も近いポイントが必要な場合は、大規模な半径から始めて、再帰的にポインターまたは参照を渡すことができます。これにより、近いポイントを見つけたときに検索半径を縮小し、最も近いポイントに移動できます。かなり速い。