java - 更快地计算余弦相似度

我想在我的IR项目中使用余弦相似度，但是由于向量的大小很大，并且必须多次乘以浮点数，因此需要很长时间。

有什么方法可以更快地计算余弦相似度？

这是我的代码：

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));
}

最佳答案

通常，在IR中，一个向量的非零元素要少得多（通常查询向量是稀疏的一个，但即使对于文档向量也是如此）。您可以通过遍历稀疏向量的键（即较小的哈希图）在较大的哈希图中查找来节省时间。

至于pkacprzak关于查找表的建议以及您的内存不足：请意识到可以在进行余弦相似度计算之前进行标准化。对于每个向量，在存储它之前，先计算其范数，然后将每个元素除以该范数。然后，您可以计算点积并得出余弦相似度。

即，余弦相似度通常定义为

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

但这等于

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

其中，/是按元素划分。如果每个都用x替换x / ||x||，则只需要计算x·y。

如果将这两个建议结合起来，则会得到余弦相似度算法，该算法仅对两个输入中较小的一个进行一次循环。

通过使用更智能的sparse vector结构可以进一步改进；哈希表在查找和迭代上都有很多开销。