algorithm - 在一组向量中寻找最佳余弦相似度

Question

我有 n 个向量，每个向量有 m 个元素(实数)。我想找到所有对中余弦相似度最大的对。

直接的解决方案需要 O(n²m) 时间。

有没有更好的解决方案？

更新

Cosine similarity / distance and triangle equation启发我可以用“弦长”代替“余弦相似度” 失去精度但大大提高了速度。 (有许多解决度量空间中最近邻的现有解决方案，如ANN)

Answer 1

余弦相似度 sim(a,b) 是 related to Euclidean distance |a - b| 作者:

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

对于单位向量 a 和 b。

这意味着欧几里得距离最小时余弦相似度最大，经L2范数归一化后，问题简化为closest pair of points problem , 可以在 O(n lg n) 时间内解决。