如何优化查找相似性？

Question

我有一组由浮点向量表示的30000个文档。所有向量都有100个元素。我可以通过使用向量之间的余弦度量来比较两个文档来找到相似性。问题是找到最相似的文档需要很多时间。有什么算法可以帮助我加快速度吗？

编辑

现在，我的代码只计算第一个向量和所有其他向量之间的余弦相似度。大约需要3秒钟。我想加快速度；)算法不一定要精确，但应该给出与全搜索相似的结果。

每个向量的元素之和等于1。

start = time.time()

first = allVectors[0]
for vec in allVectors[1:]:
    cosine_measure(vec[1:], first[1:])

print str(time.time() - start)

Answer 1

如果向量被归一化，则余弦与欧几里得距离有关：||a-b||²=（a-b）²=||a||²||b|||²-2||a| ||b| | cos（t）=11-2cos（t）。所以你可以用欧几里得最近邻来重新定义你的问题。

kD树是一种很好的方法，kD树是一种概括二分搜索法的空间数据结构(http://en . Wikipedia . org/wiki/K-d _ tree)。反正kD树在高维度(你的情况)效率低是众所周知的，所以首选所谓的Best-bin-first-search(http://en . Wikipedia . org/wiki/Best-bin-first _ search)。

Answer 2

有一篇论文《如何逼近内积：欧几里德相似性的快速动态算法》描述了如何执行内积的快速逼近。如果这还不够好或不够快，我建议建立一个包含所有文档的索引。一个类似于四叉树但基于测地线网格的结构可能会非常有效，参见使用分层三角网格索引球体。

更新：我完全忘记了你在处理100维。对高维数据进行索引是出了名的困难，我不确定对一个球体进行索引将如何推广到100维。

Answer 3

局部敏感散列（LHS）会有帮助吗？在LHS的情况下，散列函数根据您选择的概率将相似的项目映射到彼此附近。据称它特别适合高维相似性搜索/最邻近搜索/接近重复检测，在我看来，这正是您正在努力实现的。

参见 如何理解局部性敏感哈希？