2

10k から 100k のような非常に膨大な次元の k-NN 探索問題に関する記事はありますか?

実際のデータでのテストを含む記事のほとんどは、10 ～ 50 の範囲で動作し、100 ～ 500 の範囲で動作する記事もいくつかあります。

私の場合、最大 100k の特徴次元に最大 10^9 ポイントあり、次元数を効果的に削減する方法はありません。

UPD .: 現時点では、VP ツリーを適応させて実装しようとしていますが、この次元のツリー構造がうまく機能しないことは明らかです。

2 つ目のアプローチは LSH ですが、データの分布によっては精度に大きな問題が生じる可能性があります。

4

2 に答える 2

2

FLANNライブラリを見てください。

このホワイトペーパーでは、データの次元性が最近傍照合のパフォーマンスに大きな影響を与える要因の 1 つであることと、FLANN で採用されているソリューションについての論文を紹介します。

于 2013-06-19T13:27:57.757 に答える
1

最近隣検索に kd-tree を使用していますか? kd-tree は、高次元でほぼ網羅的な検索に劣化します。

高次元では、通常、近似最近傍検索を使用することをお勧めします。元の論文へのリンクは次のとおりです: http://cvs.cs.umd.edu/~mount/Papers/dist.pdf。それが少し重すぎる場合は、これを試してください: dimacs.rutgers.edu/Workshops/ MiningTutorial/pindyk-slides.ppt </p>

最近傍探索に関しては、決定の選択に影響を与える多くの要因があります。ポイントを完全に一次メモリにロードする必要があるかどうか、または二次メモリを使用できるかどうかも、決定を左右する必要があります。

于 2013-06-19T12:58:25.783 に答える