問題タブ [approximate-nn-searching]

私は実際に高次元データ (〜 50.000-100.000 の機能) に取り組んでおり、最近傍検索を実行する必要があります。次元が大きくなるにつれて KD-Trees のパフォーマンスが低下することを知っています。また、一般に、すべての空間分割データ構造は、高次元データで徹底的な検索を実行する傾向があることも読みました。

さらに、考慮すべき重要な事実が 2 つあります (関連性の高い順に並べてあります)。

• 精度:最近隣を見つける必要があります (近似ではありません)。
• 速度:検索はできるだけ速くする必要があります。(データ構造を作成する時間はそれほど重要ではありません)。

そこで、次のことについてアドバイスが必要です。

1. k-NN を実行するためのデータ構造。
2. 可能な限り正確に設定して、aNN (近似最近傍) アプローチを使用する方が良い場合は?.

近似最近傍アルゴリズムの研究を行っています。

私は最近、KNN を妥当な速度で見つけるという素晴らしい仕事をするAnnoy Libraryを見つけました。より深い分析のために、ミートアップスライドをざっと読むことができます。

スライドを読んでソース コードを調べた後、このアルゴリズムが高次元データで KD-Tree よりもうまく機能する理由がわかりません。

KD-Tree は優れた NN アルゴリズムですが、高次元では総当たり検索 [O(n^2)] とほぼ同じ実行時間を達成するため、多くの隣接する葉をチェックする必要があります。

その理由は、高次元では、単位球の体積がかなり小さくなるためです (ここで見ることができます)。

私が Annoy ライブラリで見つけた唯一の違いは、一度に 1 つの次元を分割するのではなく、超平面を使用して空間を分割することです。

このアルゴリズムを分析して、KD-Tree よりもはるかに高速である理由を説明できる人はいますか?

Locality Sensitive Hashing に関する元の論文を読みました。

複雑さはパラメータ ε の関数ですが、それが何であるかはわかりません。

その意味を教えてください。

LSH に関するこのペーパーのセクション 5. 、特に生成されたハッシュをバケット化する方法を理解しようとしています。リンクされた論文を引用：

それぞれ d ビットで構成されるビット ベクトルが与えられた場合、N = O(n 1/(1+epsilon) ) のビットのランダム順列を選択します。各ランダム置換 σ に対して、σ によって置換されたビットの辞書式順序で、ビット ベクトルのソートされた順序 O σ を維持します。クエリ ビット ベクトル q が与えられると、次の手順を実行して近似最近傍を見つけます。各順列 σ について、O σ でバイナリ検索を実行して、q に最も近い 2 つのビット ベクトルを見つけます (得られた辞書式順序で)。 σ によって並べ替えられたビットによって)。ここで、q に一致する最長のプレフィックスの長さの順に、バイナリ検索によって返された位置の上下の要素を調べて、ソートされた順序 O σ のそれぞれで検索します。これは、ソートされた順序 O σ ごとに 2 つのポインターを維持することによって実行できます (1 つは上に移動し、もう 1 つは下に移動します)。各ステップで、一致するプレフィックスが最も長い要素に対応するポインターの 1 つを上下に移動します。(ここで、O σ で一致する最長のプレフィックスの長さは、σ によって並べ替えられたビットを使用して q に対して計算されます)。このようにして 2N = O(n 1/(1+epsilon) ) ビットベクトルを調べます。調べたすべてのビット ベクトルの中で、q へのハミング距離が最も小さいものを返します。

私はこのアルゴリズムに混乱しており、その仕組みを理解できていないと思います。

トピックに関するこの質問はすでに見つけましたが、コメントの答えがわかりませんでした。また、ポイント2のこの質問でも同じアルゴリズムが説明されていますが、その仕組みがわかりません。

できるだけシンプルにするために、段階的にどのように機能するかを説明してもらえますか?

わからないことをリストにしてみましたが、実際は下手すぎてほとんどの文章がわかりません！

gsamarasの回答後に編集：

私は答えをほとんど理解しましたが、まだいくつかの疑問があります：

1. 順列をそれぞれソートする必要があるため、N順列を実行するための総コストはO(Nnlogn)

2. 上記の順列 + 並べ替えプロセスは、前処理中に 1 回だけ実行されるか、クエリごとにq実行されますか? 前処理でもすでにかなりコストがかかるようO(Nnlogn)です。クエリ時にこれを行う必要がある場合、それは惨事です:D

3. v0とv4を比較する最後のポイントで、qそれらの置換されたバージョンまたは元のバージョン (置換前) を比較します。

マルチラベル分類に FLANN ライブラリを利用したい。FLANN ライブラリが最近傍の計算用であることは知っていますが、それを分類目的で使用する方法がわかりません。Scikit-Learn または他のライブラリにプラグインする方法はありますか。

ユークリッド距離を使用する Python 3 での LSH の効率的な実装を探しています。

「in-python」LSHForest実装がありますが、コサイン距離を使用します。

また、この実装を使用しても、各バスケットのコンテンツを表示する方法が見つかりませんでした。たとえば、クラスタリングに LSH を使用している場合、特定の半径内にある特定の数のおおよそのネイバーのみが返されます。しかし、すべての隣人を見たい場合、それがどのように行われるかわかりません（任意の検索半径を使用したくありません。これを使用して非常に大きなまたは無限の半径の意味が何であるかが本当にわかりません実装）。

どんな洞察にも感謝します。どうもありがとう。

LSH は、ANN の一般的なアルゴリズムです。

kd Tree は、おそらく NN を正確に解くための最も一般的なソリューションです。

ただし、この調査を読んで、これらの構造を見つけましたが、どちらが NN または ANN を解くためのものかわかりません。

• クワッド/オクトツリー
• ボールツリー
• Rツリー
• Mツリー

ANN専用の調査は見当たりませんでしたので、いずれもNNとメートル空間用だと思います（非メートル空間には使えません）。