現在、バランスの取れた KD ツリー(K=2)のすべてのノードの K Nearest Neighborを見つけようとしています。
私の実装は、ウィキペディアの記事のコードのバリエーションであり、任意のノードO(log N)の KNN を見つけるのはかなり高速です。
問題は、各ノードの KNN を見つける必要があるという事実にあります。 各ノードを反復処理して検索を実行すると、約 O(N log N) になります。
これを行うより効率的な方法はありますか？
質問する
11227 次
4 に答える
5
必要に応じて、近似手法を試してみることができます。詳細については、このテーマに関するArya と Mountの研究をチェックしてください。キーペーパーはこちらです。BigO の複雑さの詳細は、'98 年の論文に記載されています。
作業のグラフィカルな図を以下に示します。
ソース: http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif
私は、数十万の要素を持つ非常に高次元のデータセットで彼らのライブラリを使用しました。私が見つけた何よりも速いです。ライブラリは、正確検索と近似検索の両方を処理します。パッケージには、データセットを簡単に試すために使用できるいくつかの CLI ユーティリティが含まれています。kd ツリーを視覚化することもできます (上記を参照)。
FWIW: R Bindingsを使用しました。
ANNのマニュアルから：
...Arya と Mount [AM93b] および Arya などによって示されています。[AMN+98] ユーザーが検索で少量のエラーを許容する場合 (最近傍点ではない可能性がある点を返すが、真の最近傍点よりもクエリ ポイントから大幅に離れていない点を返す)、実行時間を大幅に改善することができます。ANN は、最近傍クエリに正確かつ近似的に応答するためのシステムです。
于 2010-03-26T17:46:46.417 に答える
2
この問題にはカバーツリーを使用しました。リンクは次のとおりです。http://hunch.net/~jl/projects/cover_tree/cover_tree.html
50M サイズのデータ セット (すべての kNN クエリ、k=100) では、カバー ツリーの作成に 5.5 秒、クエリに 120 秒かかりました。Ann lib は、ツリーの作成に 3.3 秒、クエリに 138 秒かかりました。
更新: 最近隣は対称関係ではありません。これを考えてみましょう: A(0,0) B(1,0) C(3,0)。B は C の最も近いものですが、C は B の最も近いものではありません
于 2011-11-08T03:23:55.933 に答える
1
ノード自体がクエリ ポイントである場合は、検索時間が短くなる可能性があります。バックトラッキング ステージから開始できます。テストされた最初のノードは、既にクエリ ポイントの近くにあります。その後、木の広い領域をすぐに剪定できます。
最近傍は対称関係です (n1 が n2 の最近隣である場合、同じことが n2 にも当てはまります)。そのため、すでに最近隣としてマークされているすべてのノードをスキップして、ノードの半分を検索するだけで済みます。ただのアイデア。
KD-Tree BBF (Best-Bin First) 検索を試すこともできます。これは、最も近いノード (ビン) をより早く検索するのに役立ちます。これを C# で実装したので、ソース コードに興味がある場合は私に連絡してください。
もちろん、実際の実行時間は、次元、KD ツリー構造、およびデータセット内のポイントの分布によって異なります。
ポイントのクラスタリングも適切な場合があります。
于 2010-12-03T15:18:23.493 に答える
0
検索する用語はknn joinです。より正確には、おそらく自己結合を行う必要があります。
おそらく、これらの検索結果が役立つでしょう:
R* ツリーの knn 結合アルゴリズムしか見たことがありません。ただし、私自身の実験では、繰り返しクエリを上回るパフォーマンスは得られませんでした。いくつかの実装のアイデアが欠けている可能性があります。しかし、一般に、ツリー結合のためにデータを適切に保持することは、単一の knn クエリよりもはるかに注意が必要です。
于 2012-12-18T09:04:00.297 に答える