16

100 次元空間に 500,000 点のデータベースがあり、最も近い 2 点を見つけたいと考えています。どうすればいいのですか？

更新: スペースはユークリッドです。申し訳ありません。そして、すべての答えに感謝します。ところで、これは宿題ではありません。

4

5 に答える 5

17

Introduction to Algorithmsには、2 次元空間で O(n*logn) 時間で最も近い 2 つの点を見つけることに専念する章があります。Google ブックスで確認できます。実際、この問題に分割統治法を適用する方法は非常にシンプルでエレガントで印象的であるため、すべての人にそれをお勧めします.

問題に直接拡張することはできませんが (定数7は に置き換えられる2^101 - 1ため)、ほとんどのデータセットでは問題ありません。したがって、合理的にランダムな入力がある場合、ポイントの数と次元の数がO(n*logn*m)複雑になります。nm

編集
ユークリッド空間があると仮定すると、これですべてです。すなわち、ベクトルの長さvは ですsqrt(v0^2 + v1^2 + v2^2 + ...)。ただし、メトリックを選択できる場合は、アルゴリズムを最適化するための他のオプションがある可能性があります。

于 2010-10-10T05:39:57.543 に答える
7

kd ツリーを使用します。あなたは最近傍問題を見ており、この正確なクラスの問題を処理するために高度に最適化されたデータ構造があります。

http://en.wikipedia.org/wiki/Kd-tree

PS楽しい問題！

于 2010-10-10T06:05:16.773 に答える
6

データに対して PCA を実行して、ベクトルを 100 次元から 20 次元に変換します。次に、K-Nearest Neighbor ツリー (KD-Tree) を作成し、ユークリッド距離に基づいて最も近い 2 つの近傍を取得します。

通常、いいえの場合。次元が非常に大きい場合は、ブルート フォース アプローチ (並列 + 分散/マップ削減) またはクラスタリング ベースのアプローチを実行する必要があります。

于 2010-10-10T06:00:07.900 に答える
6

ANN ライブラリを試すこともできますが、信頼できる結果は最大 20 次元までしか得られません。

于 2010-10-10T05:50:21.630 に答える
4

KD-TREE と呼ばれるデータ構造を使用します。大量のメモリを割り当てる必要がありますが、データに基づいて途中で最適化が 1 つまたは 2 つ見つかる場合があります。

http://en.wikipedia.org/wiki/Kd-tree。

私の友人は、数年前に博士論文に取り組んでいたときに、同様の問題に遭遇しました。彼の作品は、10 次元にわたって 1M ポイントのオーダーでした。それを解決するために kd-tree ライブラリを構築しました。オフラインでご連絡いただく場合は、コードを掘り下げることができる場合があります。

彼の公開論文はこちら: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf

于 2010-10-10T06:19:02.683 に答える