更快地计算余弦相似度

Question

我想在我的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));
}

Answer 1

通常在IR中,一个向量的非零元素远少于另一个向量(通常查询向量是较稀疏的元素,但即使对于文档向量也是如此).您可以通过循环遍历稀疏矢量的键(即较小的哈希映射)来节省时间,在较大的哈希映射中查找它们.

至于pkacprzak建议的查找表和你的内存不足:意识到可以在余弦相似度计算之前进行归一化.对于每个向量,在存储之前,计算其范数并将每个元素除以该范数.然后,您可以计算点积并获得余弦相似度.

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

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

但那等于

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

/元素划分在哪里.如果每个都替换x为x / ||x||,那么您只需要计算x·y.

如果将这两个建议组合在一起,就会得到一个余弦相似度算法,该算法在两个输入中较小的一个上只需要一个循环.

通过使用更智能的稀疏矢量结构可以进一步改进; 哈希表在查找和迭代中都有很多开销.