java - 运行时数千个庞大数据集的 Jaccard 相似度算法

Question

我需要什么

我正在寻找非常快速和准确的方法来找到多个庞大数据集之间的 Jaccard 相似性。我最多可以进行 10.000-20.000 次计算 Jaccard 相似度的操作。由于需要在转储该数据集后立即计算所有 Jaccard 相似性，我无法在安静的冬夜使用缓慢的算法在后台计算它们。

我看到两种可能的解决方案:

解决方案 #1

使用MinHash算法。这个解决方案的问题是它非常慢。要获得 10% 的错误，您需要使用 100 个哈希函数。我在这里看到的唯一解决方法是使用单个“昂贵”哈希函数对所有内容进行哈希处理，而不是对哈希结果使用 100 个“廉价”哈希函数。但是我没有足够的数学背景来自己选择它们。

问题#1

如何为 MinHash 选择速度高效的哈希函数集以获得最大误差 10%？

解决方案 #2

使用 HyperLogLog 或 BitSet 计算 Jaccard 相似度。
这种方法的问题是 for some reasons I get too big errors in some cases . BitSet 的问题(即使它是稀疏数据结构)也在于它在更大的数据集上占用过多的 RAM。

我的算法:

1. 选择概率基数估计算法(HyperLogLog 或 BitSet)
2. 计算set1的可能基数
3. 计算set2的可能基数
4. 计算 set1 union set2 的可能基数。 HyperLogLog和BitSet都支持合并操作。
5. set2 和 set1 之间的相似性 = (cardinality(set1) + cardinality(set2) - cardinality(set1 union set2))/cardinality(set2)

问题#2

为什么我在 BitSet 和 HyperLogLog 上得到相同的 Jaccard 相似性估计偏差？ BitSet prove better cardinality precision than HLL .我虽然认为如果 BitSet 占用更多空间它应该有更高的准确性，我错了吗？

问题 #3

用 BitSet 和 HyperLogLog 不可能实现小于 5% 的 Jaccard 相似度偏差吗？我做错了什么？

附言

Hope this test results would be helpful for you!

Answer 1

1) minwise 哈希有一种变体，称为单置换哈希(参见 http://papers.nips.cc/paper/4778-one-permutation-hashing.pdf)，它仅使用单个哈希函数。对于元素数量与 bin 数量相比较小的小集合，估计可能会以某种方式不准确。然而，在这种情况下，可以使用 https://arxiv.org/pdf/1406.4784.pdf 中描述的技术“加密”集合的哈希签名。 .

2) 位集实际上是 HyperLogLog 草图的特例，如 https://arxiv.org/pdf/1702.01284.pdf 中所述。 .本文还介绍了一种最大似然法，该方法可以更准确地估计两个 HyperLogLog 草图的并集和交集大小，最终可用于估计 Jaccard 相似度。