向量的余弦相似度，< O(n^2) 复杂度

发布于 2024-09-11 11:17:47 字数 525 浏览 10 评论 0 原文

浏览此网站是否有类似问题，我发现： http://math.nist.gov/javanumerics /jama/ 和这个： http ://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html

但是，这些运行时间似乎为 O(n^2)。我一直在进行一些文档聚类，并注意到即使处理小型文档集，这种复杂程度也是不可行的。鉴于，对于点积，我们只需要两个向量中包含的向量项，应该可以将向量放入树中，从而计算具有 n log n 复杂度的点积，其中 n 是2 个文档中的 1 个。

我错过了什么吗？有没有一个java库可以做到这一点？

谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

谁把谁当真 2024-09-18 11:17:47

如果将向量元素存储在哈希表中，那么查找只是 log n ，不是吗？循环遍历较小文档中的所有键，看看它们是否存在于较大文档中..？

回复收藏 0 原文

简单气质女生网名 2024-09-18 11:17:47

Hashmap 很好，但它可能会占用大量内存。

如果向量存储为按键排序的键值对，则向量乘法可以在 O(n) 内完成：您只需并行迭代两个向量（例如在合并排序算法中使用相同的迭代）。乘法的伪代码：

i = 0
j = 0
result = 0
while i < length(vec1) && j < length(vec2):
  if vec1[i].key == vec2[j].key:
    result = result + vec1[i].value * vec2[j].value
  else if vec1[i].key < vec2[j].key:
    i = i + 1
  else
    j = j + 1

Hashmap is good, but it might take a lot of memory.

If your vectors are stored as key-value pairs sorted by key then vector multiplication can be done in O(n): you just have to iterate in parallel over both vectors (the same iteration is used e.g. in merge sort algorithm). The pseudocode for multiplication:

i = 0
j = 0
result = 0
while i < length(vec1) && j < length(vec2):
  if vec1[i].key == vec2[j].key:
    result = result + vec1[i].value * vec2[j].value
  else if vec1[i].key < vec2[j].key:
    i = i + 1
  else
    j = j + 1

回复收藏 0 原文

黎歌 2024-09-18 11:17:47

如果您计划使用余弦相似度作为查找相似文档集群的方法，您可能需要考虑研究局部敏感哈希，一种基于哈希的方法，专门考虑到这一点而设计。直观上，LSH 对向量进行哈希处理的方式是，很可能将相似的元素放入同一个桶中，而将相距较远的元素放入不同的桶中。有些 LSH 方案使用余弦相似度作为其基础距离，因此要查找集群，您可以使用 LSH 将事物放入桶中，然后仅计算同一桶中元素的成对距离。在最坏的情况下，这将是二次的（如果一切都落在同一个桶中），但更有可能的是你的工作会大幅下降。

希望这有帮助！