scala - 如何使用带状技术对具有分布式 MinHash 的集合（用户/文档）进行聚类？

Question

我对使用 MinHash 和 banding 技术对集合进行聚类的方式存在很大疑问。

我假设阅读的每个人都对 MinHash 有很好的了解，所以我不会定义我使用的大多数术语。

我的目标是使用 MinHash 根据签名的相似性对用户进行聚类。在本地的非带状设置中，这将是微不足道的：如果它们的签名哈希相同，则它们进入同一个集群。

如果我们将签名分成带状并独立处理它们，我可以像我之前所说的那样对待一个带，并为每个带生成一组集群。我的问题是：我应该如何聚合这些集群？如果它们至少有一个共同元素，就合并它们？还是我应该做一些不同的事情？

谢谢

Answer 1

MinHash 并不是真正意义上的独立聚类算法。它旨在作为近似重复检测的候选过滤器。

在查找类似文档时，您计算 minhashes 以检索候选者。然后您仍然需要检查这些候选人 - 他们可能是误报！签名越多，它们真正匹配的可能性就越大。

因此，如果您再次考虑近似重复的情况：如果 a 是 b 的近似重复并且 b 是 c 的近似重复，那么 a 也应该是 c 的近似重复。如果这成立，您可以将所有这些匹配项（验证后）放在一起。如果它不考虑合并（或不合并）候选者的分层聚类策略。