1

IR プロジェクトでコサイン類似度を使用したいのですが、ベクトルのサイズが大きく、float を何度も乗算する必要があるため、時間がかかります。

コサイン類似度をより速く計算する方法はありますか?

ここに私のコードがあります: 

private double diffrence(HashMap<Integer, Float> hashMap,
 HashMap<Integer, Float> hashMap2 ) {
    Integer[] keys = new Integer[hashMap.size()];
    hashMap.keySet().toArray(keys);

     float ans = 0;

    for (int i = 0; i < keys.length; i++) {
        if (hashMap2.containsKey(keys[i])) {
             ans += hashMap.get(keys[i]) * hashMap2.get(keys[i]);

        }
    }

     float hashLength = 0;
    for (int i = 0; i < keys.length; i++) {
         hashLength += (hashMap.get(keys[i]) * hashMap.get(keys[i]));
    }
     hashLength = (float) Math.sqrt(hashLength);

    Integer[] keys2 = new Integer[hashMap2.size()];
    hashMap2.keySet().toArray(keys2);

     float hash2Length = 0;
    for (int i = 0; i < keys2.length; i++) {

         hash2Length += hashMap2.get(keys2[i]) * hashMap2.get(keys2[i]);

    }
     hash2Length = (float) Math.sqrt(hash2Length);

    return (float) (ans /(hash2Length*hashLength));
}
4

5 に答える 5

9

通常、IR では、一方のベクトルは他方のベクトルよりもゼロ以外の要素がはるかに少なくなります (通常、クエリ ベクトルはより疎なベクトルですが、これはドキュメント ベクトルにも当てはまります)。疎なベクトル、つまり小さいハッシュ マップのキーをループして、大きいハッシュ マップで検索することにより、時間を節約できます。

ルックアップ テーブルに関する pkacprzak の提案とメモリ不足については、コサイン類似度計算の前に正規化を実行できることを認識してください。各ベクトルについて、保存する前にそのノルムを計算し、それですべての要素を除算します。次に、ドット積を計算してコサイン類似度を取得できます。

つまり、コサイン類似度は通常、次のように定義されます。

x·y / (||x|| × ||y||)

しかし、それは等しい

(x / ||x||) · (y / ||y||)

/要素ごとの除算はどこにありますか。それぞれを で置き換えるxとx / ||x||、 を計算するだけで済みますx·y。

これら 2 つのアドバイスを組み合わせると、2 つの入力のうち小さい方のループを 1 回だけ実行するコサイン類似度アルゴリズムが得られます。

よりスマートな疎ベクトル構造を使用することで、さらに改善することができます。ハッシュ テーブルには、ルックアップと反復の両方で多くのオーバーヘッドがあります。

于 2013-06-26T19:52:14.567 に答える
1

通常、ベクトルが多すぎて各ペアのコサイン類似度を事前計算できませんが、すべてのベクトルの長さを事前計算し、ルックアップ テーブルを使用して格納することができます。これにより、2 つのベクトルのコサイン類似度を計算する定数が減少します。実際には、浮動小数点演算が多いため、かなりの時間を節約できます。

ベクトルにゼロを格納することでメモリを浪費していないと仮定しています。

于 2013-06-26T19:45:40.830 に答える
1

他の人がすでに提案したようにベクトルを事前に正規化し、ベクトルのリストが変更されていないと仮定することに加えて、それらを一度配列のペアに変換し（類似関数の外で）、キーインデックスで並べ替えます。

Integer[] keys = new Integer[hashMap.size()];
Float values[] = new Float[keys.size()];
int i = 0;
float norm = ...;    
for (Map.Entry<Integer, Float> entry : new TreeMap<Integer, Float>(hashMap).entrySet())
{
   keys[i] = entry.getKey();
   values[i++] = entry.getValue() / norm;
}

次に、実際の類似度計算を行うために (次に、 twoの代わりにkeys1, values,を渡すと仮定します)、最も内側のループは次のように縮小されます。keys2values2HashMaps

float ans = 0;
int i,j = 0;
while (i < keys1.length && j < keys2.length)
{
  if (keys1[i] < keys2[j])
    ++i;
  else if (keys1[i] > keys2[j])
    ++j;
  else
    // we have the same key in 1 and 2
    ans += values1[i] * values2[j];
}

keysすべてのベクトルとすべてのベクトルをとvaluesの大きな配列に連続して格納し、インデックスを持つ別の配列を最初の位置に保持することを検討することもできます。intfloat

int sumOfAllVectorLengths = ...;
int allKeys[] = new int[sumOfAllVectorLengths];
float allValues[] = new float[sumOfAllVectorLengths];
int firstPos = new int[numberOfVectors + 1]; 
firstPos[numberOfVectors] = sumOfAllVectorLengths;

int nextFirstPos = 0;
int index = 0;

for (HashMap<Integer, Float> vector : allVectors)
{
   firstPos[index] = nextFirstPos;

   float norm = ...;    
   for (Map.Entry<Integer, Float> entry : new TreeMap<Integer, Float>(hashMap).entrySet())
   {
      keys[nextFirstPos] = entry.getKey();
      values[nextFirstPos++] = entry.getValue() / norm;
   }

   ++index; 
}

次に、配列とベクトルのインデックスを比較関数に渡します。

于 2013-06-26T20:21:55.123 に答える
0

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

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

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

書き込み操作はベースごとに 1 つのスレッドで処理され、任意の 2 つのベクトル間の比較が必要なため、書き込み操作は O(n) でスケーリングされます。

i7-cpu Macbook で高密度ベクトルの非最終パフォーマンス テストを行いました。0.14 秒未満で各書き込み操作で 100k の 1k 次元ベクトルを簡単に処理できます。線形スケール比が維持できる場合、Simbase は 1 秒未満で各書き込み操作で 700k の密なベクトルを処理できることを意味します。

于 2014-06-12T15:18:31.097 に答える
-2

少なくとも 1 つの場所がはっきりとわかります。ここでは、単に CPU サイクルを浪費しています。

for (int i = 0; i < keys.length; i++) {
    if (hashMap2.containsKey(keys[i])) {
         ans += hashMap.get(keys[i]) * hashMap2.get(keys[i]);
    }
}

float hashLength = 0;
for (int i = 0; i < keys.length; i++) {
     hashLength += (hashMap.get(keys[i]) * hashMap.get(keys[i]));
}

ここでは、同じ 2 つの hashMap に同じ境界の 2 つのサイクルがあります。なぜあなたはそれを1サイクルでやらないのですか:

float hashLength = 0;
int hm = 0;
for (int i = 0; i < keys.length; i++) {
    hm = hashMap.get(keys[i])*hashMap2.get(keys[i]);
    hashLength += hm;
    if (hashMap2.containsKey(keys[i])) {
         ans += hm;
    }
}

ところで、hashMap を使う特別な理由はありますか? または、より単純な種類の配列で行うことができますか?

于 2013-06-26T19:28:25.723 に答える