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 之间的相似性 = (基数(set1) + 基数(set2) - 基数(set1 union set2))/基数(set2)

问题#2

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

问题 #3

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

附注

Hope this test results would be helpful for you!

Answer 1

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

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