使用Jaccard相似度和MinHash查找近似重复文档

问题背景

假设我们有一个大型文档集合，希望识别哪些文档彼此大致相同。例如，我们可能在一段时间内爬取了网页，期望多次获取"相同页面"，但会看到元数据的细微差异，或者看到经过小编辑后的多个页面版本。

Jaccard相似度

Jaccard指数（又称Jaccard相似系数）是一种在多个领域广泛使用的相似度度量方法，包括大规模文本处理。

Jaccard指数是比较集合的函数，将两个有限集的相似性表征为其交集大小与并集大小的比率：

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

这个计算在直觉上很有道理：如果两个集合相似，它们应该具有大部分相同的元素。这意味着集合大小相似，它们的并集只稍大一些，交集只稍小一些。

扩展Jaccard相似度

对于非常小的语料库，我们可以直接应用这个定义。但是考虑每对文档的复杂度为$O(n^2)$，随着语料库大小的增加，这很快变得不可行。

对于查找精确重复，我们通过哈希避免二次成本；我们对文档进行哈希处理并按哈希值分组，这将相同的文档（并且，在良好的概率下，只有相同的文档）放入相同的哈希桶中。我们想要为近似重复找到类似的快捷方式；在该领域的术语中，我们想要一个局部敏感哈希。

近似Jaccard相似度

MinHash签名

Jaccard相似度是两个大小的比率：两个输入集合的交集和并集。要估计这样的面积比率，一个经典策略是采样。

首先，我们假设特征是在某个有限范围内的整数$0 \leq f_i \leq F$，然后选择$\mathbb{Z}_F$上的随机排列。称该排列为$P(x)$。现在，我们可以通过选择在我们集合中在此排列下具有最小值的特征来选择随机元素：

$$x_{\textrm{random}} \leftarrow{} \argmin_{x\in{}A\cup{}B}{P(x)}$$

使用真正随机排列实际上不可行，但我们可以使用好的哈希函数来近似一个。这也避免了需要将特征表示为固定范围整数的需求；通过接受极小的碰撞风险并仅存储哈希值，我们可以将任何合理的特征空间映射到固定大小的哈希值：

$$x_{\textrm{sig}} \leftarrow{} \min_{x\in{}A\cup{}B}{H(x)}$$

接下来，我们利用min是关联的这一事实，并将上述重写为单独预处理每个集合：

$$\begin{align*} a_{\textrm{min}} &\leftarrow{} \min_{x\in{}A}H(x) \ b_{\textrm{min}} &\leftarrow{} \min_{x\in{}B}H(x) \ x_{\textrm{sig}} &\leftarrow{} \min(a_\textrm{min},b_\textrm{min}) \end{align*}$$

使用更多哈希函数

该概率是在$\mathbb{Z}_F$的排列宇宙上进行的（带有一些注意事项，“对我们哈希函数的选择”）。使用单个哈希函数和单个min-hash，我们每对只有一个布尔估计 - “相等"或"不相等”。

我们可以通过选择$k$个来自某个适当哈希族的不同哈希函数来改进这一点，并将每个文档总结为一个$k$元素向量：

$$A_\textrm{sig} = \begin{pmatrix} \displaystyle\min_{x\in{}A}H_1(x) & \displaystyle\min_{x\in{}A}H_2(x) & \cdots{} & \displaystyle\min_{x\in{}A}H_k(x) \end{pmatrix}$$

给定两个这样的签名，我们可以通过计算有多少哈希匹配来近似Jaccard相似度：

$$J(A,B) \approx{} \frac{1}{k}\sum_{i=1}^{k} (A_\textrm{sig}[i] = B_\textrm{sig}[i])$$

比较所有文档

我们现在已将每个文档压缩为$k$元素哈希值指纹，这允许有效近似Jaccard相似度。

下一个问题是在整个语料库中查找近似重复项 - 具有高相似度的文档 - 而不考虑每对文档。如上所述，我们的策略是定义一组键，我们可以按这些键对文档进行分组，然后仅在每组内执行完整比较。

使用完整签名

最简单的选择是简单地将所有$k$个MinHash值一起用作分组键，并且当且仅当它们的所有MinHash值匹配时，考虑两个文档为"近似重复"。

这种方法的最强优势是其简单性和效率。按单个高基数字节串对文档进行分组是一种高效操作，易于水平扩展，并且作为基本原语在任何数据处理工具包中提供。

更模糊的匹配

如果我们想要检测"更模糊"的重复项呢？也许经过一些实证研究后，我们确定想要查找相似度高于0.8或0.7的对，而不仅仅是"接近1"。

通过使用我们的$k$个MinHash哈希的子集作为分组键，我们可以增加在较低相似度值下碰撞的可能性，然后在每个桶内比较完整签名以消除误报。例如，我们可能按前4个MinHash值分组，然后 - 在每个碰撞组内 - 使用我们所有的MinHash值来估计真实相似度。

附录：将文档表示为集合

n-grams又称"shingles"

我们可以将文档表示为文档中出现的所有n-gram的集合，选择某个适当的n值。在大规模文本处理领域，文献中经常使用"shingle"而不是"n-gram"。

分词

我们可以尝试将输入拆分为"单词"或"标记"，并将这些用作我们的特征。GPT-3论文摘录提到了"Spark的标准分词器"，我相信这是指此类，它只是将输入小写然后在空白处拆分。

我们可以使用更复杂的分词器，或者通过分词然后使用标记的n-gram来混合方法。在这种情况下，我们将使用较小的n值，因为单个标记应该比字节或字符具有更高的熵。