基于采样的 Jaccard 包含度和相似性估计-计算机科学-机器学习-算法.pdfVIP

基于采样的Jaccard包含度和相似性估计

PranavJoshi∗

2025年7月20日

摘要

我们研究在仅能访问均匀采样的子集和的情况下，估计两个集合和之间

本的Jaccard包含的问题。虽然存在几种基于草图的方法来近似集合相似性，但

译我们考虑的是已知集合大小且不使用草图的情况。我们推导出观察到的样本重叠的

中确切似然，并证明由稀疏采样所启发的二项式近似在该情况下不仅理论上可行而且经验上准确。

我们将此二项式模型与先前工作中使用的基于联合的似然性进行比较，并通过实验展示它们

2

v之间的差异。我们还分析了在均匀先验下的交集大小的后验分布，推导出后验均方

9

1误差（MSE）的紧上界，并提供了实现所需误差和置信度阈值的样本复杂度保证。

0此外，我们扩展了我们的框架以使用相同的采样模型估计Jaccard相似性。

0

1我们推导出的分数误差界限，表明其按规模缩放，并提出了当MinHash应用于采

7.样子集时的校正估计方案。这些结果提供了一种从样本中进行相似性估算的统一方法，对于完

0整数据的草图昂贵或不可用的大规模数据系统具有重要意义。

5

2

:

v1介绍

i

x

r

a估计集合相似性度量是数据分析中的一个基本问题，具有在信息检索、数据库系统和流算法等

方面的应用。在这些度量中，两个集合的Jaccard包含度—定义为

当将视作参考集时—在非对称比较任务（如检测近重复项或基于包含的连接）中尤为重要。

在大规模设置中，精确计算可能不可行，因为它需要两组的全部知识。当大小已知

时，例如在甲骨文数据库中，可以使用基于采样的估计器作为可扩展的替代方案，这些估计器采用

小的随机子集和。

本文提出了基于随机样本的Jaccard包含的概率模型和估计策略的理论分析，重点关注了其实

证性能和统计保证。具体来说，我们：

•在温和的假设下推导出对真实似然性的二项式近似。

∗Email:pranav.joshi@iitgn.ac.in

1

•比较这个近似值与一个精确的组合公式以及之前工作中的基于并集的模型。

•使用经验抽样来验证不同似然模型及其相关估计量的准确性。

•分析在均匀先验下的后验分布，并推导出高概率下有界误差的条件。

虽然我们的主要关注点是Jaccard包含度，我们也讨论了广泛使用的度量Jaccard相似度，定

义为

估计在文档相似性、去重和聚类等应用中至关重要，尤其是在无法访问完整数据时。我们展示了

如何利用基于采样的交集大小估计器来构建对的准确估计，并提供了由于采样引入

的误差的理论界限。我们还提出了当MinHash应用于采样子集时的一种校正方案。

先前工作

众多方法被提