2

float のベクトルで表される 30,000 個のドキュメントのセットがあります。すべてのベクトルには 100 個の要素があります。ベクトル間のコサイン測定を使用して比較することにより、2 つのドキュメントの類似性を見つけることができます。問題は、最も類似したドキュメントを見つけるのに時間がかかることです。これを高速化するのに役立つアルゴリズムはありますか?

編集

今、私のコードは、最初のベクトルと他のすべてのベクトルの間のコサイン類似度を数えるだけです。約3秒かかります。私はそれをスピードアップしたいと思います ;) アルゴリズムは正確である必要はありませんが、完全な検索と同様の結果が得られるはずです。

各ベクトルの要素の合計は 1 です。

start = time.time()

first = allVectors[0]
for vec in allVectors[1:]:
    cosine_measure(vec[1:], first[1:])

print str(time.time() - start)
4

3 に答える 3

3

ローカリティ センシティブ ハッシュ(LHS) は役に立ちますか? LHS の場合、ハッシュ関数は、選択した確率で類似のアイテムを互いに近くにマップします。高次元の類似性検索/最近傍検索/重複検出に特に適していると主張されており、まさにあなたが達成しようとしていることのように思えます。

Locality Sensitive Hashing を理解する方法も参照してください。

于 2014-04-16T20:47:55.430 に答える
2

内積を近似する方法: ユークリッド類似性のための高速動的アルゴリズム内積の高速近似を実行する方法を説明する論文があります。これが十分でない、または高速でない場合は、すべてのドキュメントを含むインデックスを作成することをお勧めします。四分木に似ているが、測地線グリッドに基づく構造は、おそらく非常にうまく機能します。階層三角形メッシュによる球体のインデックス作成を参照してください。

更新: 100 次元を扱っていることを完全に忘れていました。高次元データのインデックス作成は非常に難しいことで有名であり、球体のインデックス作成が 100 次元にどの程度一般化されるかはわかりません。

于 2014-04-16T17:32:25.723 に答える