前言
MinHash 算法属于局部敏感哈希（Locality Sensitive Hashing, LSH）算法。是近似最近邻搜索算法中最流行的一种，主要应用于从海量的数据中挖掘出相似的数据，常应用于文本相似度检测、网页搜索等领域。
以下是论文《On the resemblance and containment of documents》的阅读笔记。
摘要
给定两个文档 A 和 B，我们定义了两个数学概念：相似度（resemblance）r(A, B) 和包含度（containment）c(A, B)，这两个概念很好地捕捉了“大致相同”和“大致包含”的非正式概念。
基本思想是将这些问题转化为集合交集问题，通过随机抽样的过程来进行评估，每个文档可以独立地进行。此外，可以使用固定大小的样本来评估相似度。
本文讨论了这些度量的数学属性以及使用 Rabin 指纹高效实现抽样过程的方法。
1 Introduction
随着在线信息的爆炸式增长，特别是万维网的发展，出现了大量相同或几乎相同的文档。在许多情况下，我们需要确定两个文档是“大致相同”还是“大致包含”在对方之中。
这些非正式的概念似乎没有被任何标准的字符串距离（如汉明距离、莱文斯坦距离等）很好地捕捉到。此外，这些距离的计算通常需要对整个文档进行成对比较。
对于非常大量的文档集合来说，这是不可行的，因此需要为每个文档设计一个抽样机制。
为了解决这个问题，我们使用了下面将详细定义的两个数学概念相似度和包含度。
两个文档 A 和 B 的相似度 r(A, B) 是一个介于 0 到 1 之间的数字，当相似度接近 1 时，文档很可能大致相同。同样，A 在 B 中的包含度 c(A, B) 是一个介于 0 到 1 之间的数字，当接近 1 时，表明 A 大致包含在 B 中。相似度还具有一个额外的性质，即 d(A, B)=1 − r(A, B) 是一个度量（满足三角不等式），这对于设计旨在将文档集合聚类成相似文档集的算法非常有用。
为了计算两个文档的相似度和/或包含度，只需为每个文档保留一个相对较小的草图（sketch）（做降维）。这些草图可以相当快速地计算（与文档大小线性相关），并且给定两个草图，可以在草图大小的线性时间内计算出相应文档的相似度或包含度。对于计算相似度，只需保留一个固定大小的草图。对于计算包含度，我们需要一个与底层文档大小成比例的草图。
基本方法有两个方面：首先，相似度和包含度被表述为集合交集问题；其次，通过可以独立为每个文档完成的随机抽样过程来评估这些交集的相对大小。这种估测集合交集相对大小的过程可以应用于任意集合。
2 Definitions As Set Intersection Problems
我们将每个文档视为一个标记（token）序列。这些标记可以是字母、单词或行。假设我们有一个解析器程序，它可以将任意文档转化为一个规范的标记序列。因此，从现在开始，文档指的是一个规范的标记序列。
我们的直接目标是将每个文档 $D$ 关联到一组令牌子序列 $S(D, w)$，其中 $w$ 是下面定义的参数。在文档 $D$ 中包含的连续子序列称为 shingle。给定一个文档 $D$，我们可以将其关联到其 $w$-shingling，定义为 $D$ 中包含的所有长度为 $w$ 的 shingle 的 bag（多重集合）。例如序列 (a, rose, is, a, rose, is, a, rose) 的 4-shingling 结果是 {(a, rose, is, a), (rose, is, a, rose), (is, a, rose, is), (a, rose, is, a), (rose, is, a, rose)}。
相似度与包含度的计算
- 选项A：通过标记每个 w-shingling 元素的出现次数，得到 labelled w-shingling.。$S(D, w)$ 定义为这个集合。例如 {(a,rose,is,a,1), (rose,is,a,rose,1), (is,a,rose,is,1), (a,rose,is,a,2), (rose,is,a,rose,2)}
- 选项B：$S(D, w)$ 被定义为 $D$ 中的 shingle 集合。例如 {(a,rose,is,a), (rose,is,a,rose), (is,a,rose,is)}
一旦我们确定了 shingle 大小和 option ，文档 A 和 B 的相似度 $r$ 定义为：
\[r_{w}(A,B)={\frac{|S(A,w)\cap S(B,w)|}{|S(A,w)\cup S(B,w)|}},\]A 在 B 中的包含度 $c$ 定义为：
\[c_{w}(A,B)={\frac{|S(A,w)\cap S(B,w)|}{|S(A,w)|}}.\]相似度与包含度的性质
- 相似度：相似度是 0 到 1 之间的数，r(A, A) = 1，即任何大小的A与其自身的相似度为100%。
- 包含度：包含度也是 0 到 1 之间的数，如果 A 是 B 的连续子序列，则 c(A, B) = 1。
- 计算复杂度：计算相似度和包含度归结为评估集合交集的相对大小。
为了使相似度对排列变化更敏感，我们需要选择更大的 $w$；另一方面，较大的 $w$ 可能对小的变动过于敏感，因为一个标记的改变会影响到 $w$ 个 shingle。另外，定义为 $d_w(A, B)=1 − r_w(A, B)$ 的相似性距离是一种度量，在选择聚类算法时可能会很有用。
3 Estimating the resemblance and the containment
固定一个 shingle 大小 $w$，用 $\Omega$ 表示所有标记的（Option A）或未标记的（Option B）大小为 $w$ 的 shingle 的集合。可以假设 $\Omega$ 是完全有序的。固定一个参数 $s$，对于一个集合 $W \subseteq Ω$，定义 $MIN_s(W)$ 为 $W$ 中最小的 $s$ 个元素的集合（如果 $| W | \geq s$)；否则为 $W$ 本身：
\[\operatorname{MIN}_{s}(W)=\left\{\begin{array}{l l}\mathrm{the~set~of~the~smallest~}s\mathrm{~elements~in~}W,&{\mathrm{if~}|W|\geq s;}\\{W,}&{\mathrm{otherwise.}}\end{array}\right.\]其中“最小”是指在 $\Omega$ 上定义的顺序。对于一个集合 $I \subseteq \mathcal{N}$，定义
\[MOD_m(I) = \text{the set of elements of W that are 0 mod m.}\]设 $g: \Omega \rightarrow \mathcal{N}$ 是任意单射，$\pi: \Omega \rightarrow \Omega$ 是从 $\Omega$ 中均匀随机选择的排列，令 $M(A) = MIN_s(\pi(S(A, w)))$ 和 $L(A) = MOD_m(g(π(S(A, w))))$ 。$M(B)$ 和 $L(B)$ 的定义类似。
\[\frac{|MIN_s(M(A)\cup M(B))\cap M(A)\cap M(B)|}{|MIN_s(M(A)\cup M(B))|}\]的值是 A 和 B 相似度的无偏估计。
\[\frac{|L(A)\cap L(B)|}{|L(A)\cup L(B)|}\]的值是 A 和 B 相似度的无偏估计。
\[\frac{|L(A)\cap L(B)|}{L(A)}\]是 A 在 B 中包含程度的无偏估计。
证明：
\[\begin{aligned}MIN_s(M(A) \cup M(B)) &= MIN_s(\pi(S(A, w)) \cup \pi (S(B, w)))\\ &= MIN_s(\pi(S(A, w) \cup S(B, w))\end{aligned}\]用 $\alpha$ 表示 $\pi(S(A, w) \cup S(B, w))$ 中的最小元素。则：
\[\begin{aligned}\Pr(\alpha \in M(A) \cap M(B))&=\Pr(\pi^{-1}(\alpha)\in S(A,w) \cap S(B,w)) \\ &=\frac{|S(A,w)\cap S(B,w)|}{|S(A,w)\cup S(B,w)|}=r_w(A,B)\end{aligned}\]由于我们可以对 $MIN_s(\pi(S(A, w) \cup S(B, w)))$ 中的每个元素重复这个论证，这证明了第一个结论。
因此可以选择一个随机排列，为每个文档 $D$ 保留一个仅包含集合 $M(D)$ 和/或$L(D)$ 的草图（sketch）。这些草图足以估计任意一对文档的相似度或包含程度，而无需原始文件。
集合 $M(D)$ 具有固定的大小优势，但只能用于估测相似度。$L(D)$ 的大小随着 $D$ 的增长而增长，但可以用于估测相似度和包含程度。
为了限制 $L(D)$ 的大小，我们可以按照以下方式进行：对于大小在（假设）$100 * 2^i$ 和 $100 * 2^{i+1}$之间的文档，我们存储集合 $L_i(D) = MOD_{2^i}(g(\pi(S(D))))$。$L_i(D)$ 的预期大小始终在 50 到 100 之间。另一方面，我们可以轻松地从 $L_i(D)$ 计算 $L_{i+1}(D)$（只保留那些可以被 $2^{i+1}$ 整除的元素）。因此，如果我们有两个文档 A 和 B，并且较长的文档使用了 $2^i$ 作为模数，我们将使用 $L_i(A)$ 和 $L_i(B)$ 进行估计。这种方法的缺点是，由于样本的稀缺性，对非常短的文档嵌入到大得多的文档中的包含程度的估计容易出现错误。
4 Implementation issues
4.1 选择随机排列和样本
Shingle 的总大小相对较大。例如，如果 shingle 由 7 个（英语）单词组成，那么一个 shingle 平均将包含大约 40-50 个字节。因此，为了减少存储，我们首先为每个 shingle 关联一个较短的 $\ell$ 位ID，然后使用集合 {0, 1,…,$2^{\ell}$} 的随机排列 $\pi$。这里存在一个权衡：如果我们取 $\ell$ 较大，那么我们可以确保大多数/所有 ID 是唯一的，但我们将不得不占用更多存储。另一方面，大量的冲突会降低我们的估测。
设 $f: \Omega \rightarrow \{ 0,…,2^\ell − 1\}$ 是产生此 ID 的函数。一旦 $f$ 固定，我们估测的是
\[r_{w,f}(A,B)=\frac{|f(S(A,w))\cap f(S(B,w))|}{|f(S(A,w))\cup f(S(B,w))|}\]而不是
\[r_w(A,B)=\frac{|S(A,w)\cap S(B,w)|}{|S(A,w)\cup S(B,w)|}\]固定一个任意的大小为 $n$ 的集合 $S \in \Omega$。如果 $f$ 是均匀随机选择的，则：
\[\mathbf{E}(|f(S)|) = 2^\ell(1-(1-\frac{1}{2^\ell})^n) = n - \binom{n}{2}\frac{1}{2^\ell} + \binom{n}{3}\frac{1}{2^{2\ell}} + ...\]如果 $\ell$ 远大于 $\log n$，则
\[\mathbf{E}(|f(S)|)\approx n-{\binom{n}{2}}{\frac{1}{2^{\ell}}}\]换句话说，在这种情况下，我们可以忽略多次冲突的影响。
在实际实现中，$f$ 不是完全随机的，冲突的概率可能会更高。一个好的选择是使用 Rabin 的指纹函数，其两个字符串 $s_1$ 和 $s_2$ 的冲突概率可以在对抗模型中为 $max(|s_1| , |s_2|)/2^\ell−1$ 所限制。Rabin 指纹的优点是基于随机不可约多项式，其冲突概率是很好理解的。此外，Rabin 指纹可以在软件中非常高效地计算，并且我们可以在计算“滑动窗口”的指纹时利用它们的代数属性。
为了进一步提高效率，而不是保持集合 $MIN_s(\pi(S(A, w)))$，我们可以保持模 m 余数为 0 的指纹集合的 $MIN_s$（即构造集合 $MIN_s(MOD_m(\pi(S(A, w))))$）。
对于选项A，集合 $MIN_s$ 应该保存在一个堆中，最大值在根节点。每当有一个新的指纹比当前根节点小时，应该替换当前根节点，然后我们应该重新堆化。这种情况发生的预期次数是 $O(s \log(n/m))$，其中 $n$ 是文档中的标记数，$m$ 是上面讨论的模数，因为随机排列的第k个元素必须进入堆的概率是 $s/k$。每次堆操作的成本是 $O(\log s)$，因此堆操作的预期总成本是 $O(s \log s \log(n/m))$。对于选项B，我们需要保持一个平衡的二叉搜索树。一些可能性是红黑树、随机搜索树和跳表。成本仍然是 $O(s \log s \log(n/m))$，但常数因子可能更大。另一种可能性是堆加上一个哈希表来检查重复，成本相同。
4.2 样本大小
样本越大，结果可能越准确。但是，更大的样本会带来更高的存储成本。样本中共同 shingle 的数量服从超几何分布。由于样本的大小通常比文档的大小小得多，我们可以通过二项分布来近似超几何分布。在这种近似下，如果 $r$ 是相似度，那么我们的估计在 $[r−ε, r+ε]$ 范围内的概率由以下公式给出：
\[p(s,r,\epsilon)=\sum_{s(r-\epsilon)\leq k\leq s(r-\epsilon)}{\binom{s}{k}}r^{k}(1-r)^{s-k}.\]对于固定的 $s$，如果 $r$ 接近 0.5，我们的估测可能会更差，但我们通常只关心 $r$ 更大的情况。对于实际应用来说，100 个样本似乎是合理的，200 个样本似乎绰绰有余。根据选择的指纹长度，这意味着草图应该在 300 到 800 字节长。对于整个网络来说，估测相对偏离的文档对数量当然可能很大。然而，即使对于整个网络，任何相似度低于 50% 的文档对被估计为相似度超过 90% 的可能性也很小（概率小于0.1%）。
4.3 计算指纹
计算指纹的过程相当快速，即使我们对每个 shingle 都从头开始计算。这种情况下的总成本是 $O(wn)$，其中 $O$ 表示法隐藏了 token 的宽度。
然而，对于 Rabin 指纹，如果利用我们正在计算”滑动窗口”的指纹这一事实，我们可以获一个 $w$ 因子的优势，特别是如果窗口的字节宽度是固定的或在狭窄范围内。如果 token 具有固定宽度，这是自动的。否则，我们可以定义 token 有一个小的最大宽度，并在必要时填充它们以达到这种效果。
例如，我们可以定义一个单词最多有 8 个字节。较长的单词将被视为几个单词的连接。当我们计算指纹时，我们可以将较短的单词填充到8个字节。
如果我们采用选项A，那么我们必须检查每个 shingle 之前遇到了多少次。这可以通过对其进行指纹识别然后在哈希表中搜索来完成。一旦决定了适当的标签，就需要计算第二个指纹。需要小心避免同一 shingle 的不同标签的指纹之间过多的依赖。选项B完全避免了这些计算，但如上所述，我们必须保持一个二叉搜索树而不是堆，以确保我们不会插入相同的值两次。尽管如此，选项B在实践中似乎更快。
4.4 评估相似度
我们将每个草图存储为一个按递增顺序排序的列表。然后我们只需要进行归并排序并删除重复项，计算在前 $s$ 个输出中遇到了多少重复项。这个过程的时间复杂度是 $O(s)$。
我们可能对两个以上的文档感兴趣。对于 $r$ 个文档，评估所有相似度需要 $O(r^2s)$ 的时间。然而，我们可以尝试进行”贪心聚类”，具体步骤如下：保持一个当前簇的集合（初始为空），依次处理草图。对于每个簇，保持一个代表草图。如果一个新的草图与当前簇足够相似，则将该草图添加到其中（并可能重新计算代表草图）；否则，开始一个新的簇。在实践中，每个指纹很可能只属于几个不同的簇。在这个假设下，如果我们记住每个遇到的指纹属于哪些簇，并将指纹存储在一个哈希表中，那么整个过程可以实现在 $O(rs)$ 时间内完成。作为代表草图，我们可以取簇中最受欢迎的s个指纹，或者简单地取簇中的第一个成员。
对于非常大的文档集合，其中r需要外部存储，就需要采取不同的方法。更多细节见 Syntactic clustering of the web。
附录
可以阅读以下文章（提供了图例方便理解）：
