8

在浏览了这个网站的类似问题后，我发现了这个： 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库可以做到这一点？

谢谢

4

4 回答 4

2

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
于 2010-07-27T19:22:05.163 回答
2

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

于 2010-07-27T18:13:05.440 回答
1

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

希望这可以帮助！

于 2014-06-12T17:21:41.867 回答
0

如果你只想为一个大小为n的集合中的每个项目推荐有限的项目，例如m个项目，复杂度不必是n^2，而是m*n。由于 m 是一个常数，因此复杂度是线性的。

您可以查看项目 simbase https://github.com/guokr/simbase，它是一个向量相似度 nosql 数据库。

Simbase 使用以下概念：

  • 向量集：一组向量
  • 基：向量的基，一个向量集中的向量具有相同的基
  • 推荐：两个具有相同基的向量集之间的单向二元关系
于 2014-06-12T15:14:53.420 回答