3

新しいベクトルが与えられた場合、n個のベクトルの膨大な（数百万）リストがあるとしましょう。セットからかなり近いものを見つける必要がありますが、最も近いものである必要はありません。（最近傍は最も近いものを見つけてn時間で実行されます）

精度を犠牲にして最近傍を非常に迅速に近似できるアルゴリズムはありますか？

編集：おそらく役立つので、データはほとんどの場合非常にスムーズであり、ランダムな次元でのスパイクの可能性はわずかです。

4

4 に答える 4

3

任意の距離で最も近い要素を検索するO（n）よりも高速なアルゴリズムが存在します。詳細については、 http：//en.wikipedia.org/wiki/Kd-treeを確認してください。

于 2011-02-18T19:43:22.810 に答える
2

SIFT や SURF、またはマルチメディア セクターで使用される記述子などの高次元ベクトルを使用している場合は、LSH を検討することをお勧めします。

Wei Dong の博士論文 ( http://www.cs.princeton.edu/cass/papers/cikm08.pdf ) は、KNN 検索の更新されたアルゴリズム、つまり LSH を見つけるのに役立つかもしれません。MIT の研究者によって以前に公開されたE2LSH ( http://www.mit.edu/~andoni/LSH/ ) などの従来の LSH とは異なり、彼のアルゴリズムはマルチプローブを使用して、再現率とコストのトレードオフのバランスをとっています。

于 2013-07-10T10:35:17.710 に答える
1

おおよその最近傍の場合、最も速い方法は、ローカリティ センシティブ ハッシュ (LSH) を使用することです。LSH には多くのバリアントがあります。データの距離メトリックに応じていずれかを選択する必要があります。LSH のクエリ時間の大部分は、データセットのサイズとは無関係です (出力結果の時間を考慮していません)。だから本当に速いです。このLSH ライブラリは、L2 (ユークリッド) 空間用のさまざまな LSH を実装しています。

データの次元が 10 未満の場合、正確な結果が必要な場合はkd ツリーが優先されます。

于 2016-01-22T03:50:11.407 に答える
1

「最近傍」lsh ライブラリを Web 検索すると、 http: //www.mit.edu/~andoni/LSH/ http://www.cs.umd.edu/~mount/ANN/ http://msl.csが見つかります。 .uiuc.edu/~yershova/MPNN/MPNN.htm

于 2011-02-18T05:38:01.240 に答える