9

n 個のベクトルがあり、それぞれに m 個の要素 (実数) があります。すべてのペアの中でコサイン類似度が最大になるペアを見つけたいです。

簡単な解決策には、O(n 2 m) の時間が必要です。

より良い解決策はありますか？

アップデート

コサイン類似度/距離と三角形の方程式「コサイン類似度」を「コード長」に置き換えると、精度は失われますが速度が大幅に向上することに気づきました。( ANNのように、メトリック空間で最近傍法を解く既存のソリューションが多数あります)

4

2 に答える 2

15

コサイン類似度sim(a,b)は、ユークリッド距離 |a - b|に関連しています。

|a - b|² = 2(1 - sim(a,b))

単位ベクトルaおよびの場合b。

これは、L2 ノルムで正規化した後にユークリッド距離が最小のときにコサイン類似度が最大になることを意味し、問題は O(n lg n) 時間で解決できる最も近い点のペア問題 に縮小されます。

于 2012-12-01T17:58:31.837 に答える
0

プロジェクト simbase https://github.com/guokr/simbaseで確認できます。これはベクトル類似の nosql データベースです。

Simbase は以下の概念を使用します。

  • ベクトル セット: ベクトルのセット
  • 基底: ベクトルの基底、1 つのベクトル セット内のベクトルは同じ基底を持つ
  • 推奨事項: 同じ基準を持つ 2 つのベクトル セット間の一方向のバイナリ関係

管理タスクに redis-cli を直接使用することも、プログラミング方法で別の言語で redis クライアント バインディングを直接使用することもできます。ここにPythonの例があります

    import redis

    dest = redis.Redis(host='localhost', port=7654)
    schema = ['a', 'b', 'c']
    dest.execute_command('bmk', 'ba', *schema)
    dest.execute_command('vmk', 'ba', 'va')
    dest.execute_command('rmk', 'va', 'va', 'cosinesq')
于 2014-06-12T15:10:12.233 に答える