algorithm - 如何优化查找相似性？

Question

我有一组由浮点向量表示的 30 000 个文档。所有向量都有 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)

score 3 · Accepted Answer

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

score 2 · Accepted Answer

有一篇论文How to Approximate the Inner-product: Fast Dynamic Algorithms for Euclidean Similarity描述了如何快速逼近内积。如果这不够好或不够快，我建议建立一个包含所有文档的索引。类似于四叉树但基于测地线网格的结构可能会非常有效，请参阅使用分层三角形网格索引球体。

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

score 2 · Accepted Answer

如果您的向量被归一化，则余弦与欧几里得距离有关：||a - b||² = (a - b)² = ||a||² + ||b||² - 2 ||a|| ||b|| cos(t) = 1 + 1 - 2 cos(t)。因此，您可以根据欧几里得最近邻重铸您的问题。

一个很好的方法是 kD 树，一种概括二分搜索的空间数据结构（http://en.wikipedia.org/wiki/K-d_tree）。无论如何，已知 kD 树在高维度（您的情况）中效率低下，因此首选所谓的 best-bin-first-search（http://en.wikipedia.org/wiki/Best-bin-first_search）。

3 回答 3