最小哈希

在计算机科学领域，最小哈希（或最小哈希式独立排列局部性敏感哈希（英语：locality sensitive hashing））方法是一种快速判断两个集合是否相似的技术。这种方法是由Andrei Broder （1997）,^[1]发明的，最初在AltaVista搜索引擎中用于在搜索结果中检测并消除重复Web页面。^[2]

它同样也应用于大规模聚类问题，比如通过文档间包含的词语相似性进行聚类。^[1]

雅可比相似度与最小哈希值

雅可比相似度系数通常用来表示两个集合的相似度，定义 $U$ 是一个集合， $A$ 和 $B$ 是 $U$ 的子集。雅可比相似度定义如下：^[3]

J(A,B)={{|A\cap B|} \over {|A\cup B|}}.

它是一个0到1之间的数值上，当其为0时表示两个集合不相交，当其为1时表示两个集合相等，其他的情况则在0和1之间。它广泛地用于两集合间相似性的判断：当雅可比系数趋向于1时，两个集合更相似；反之，当雅可比系数趋向于0时，两个集合更不相似。

定义h是一个将 $U$ 中的元素映射到一些不相交整数的哈希函数， $perm$ 是集合 $U$ 中元素的排列排列，对于任意集合S，定义 $h min (S)$ 为S集合中具有最小h(x)函数值的元素x，对应 $h \circ perm$ （集合 $S$ 的元素 $x$ 是 $h (perm (x))$ 的最小值）。将 $h min$ 应用于集合 $A$ 和 $B$ ，假定没有发生哈希碰撞。有 $h min (A) = h min (B)$ ，当且仅当最小哈希值的并集 $A \cup B$ 依赖于交集 $A \cap B$ 时。因此，

Pr[h min (A) = h min (B)] = J (A, B).

也就是说， $h min (A) = h min (B)$ 是真的概率等于 $J (A, B)$ 另一方面来说，如果 $r$ 是一个当 $h min (A) = h min (B)$ 时值为1，其它情况下值为0的随机变量，那么 $r$ 可认为是 $J (A, B)$ 的无偏估计。尽管 $r$ 的方差很高时，不能很好的估计雅可比相似度，因为 $r$ 总是0或1。最小哈希思想通过以相同方式构造的几个变量，将其平均在一起来减少这种方差

算法

多哈希函数的变种

最简单的最小哈希方法是使用 $k$ 个不同的哈希函数，其中 $k$ 是固定的整数参数，使用这 $k$ 个函数所对应的 $k$ 个 $h min (S)$ 值来描述每个集合 $S$ 。使用这种最简单的版本来判断 $J (A, B)$ ，假定y是使得 $h min (A) = h min (B)$ 的哈希函数个数，使用 $y / k$ 作为估计。则此估计是 $k$ 个不同的0-1随机变量的平均值，其中每个随机变量当 $h min (A) = h min (B)$ 值为1，反之为0，并且是 $J (A, B)$ 的无偏估计。因此，该平均值同样也是一个无偏估计，而且通过0-1随机变量之和的标准Chernoff上界（英语：Chernoff bound）可得知，其期望误差是 $O(1/\sqrt k)$ 。所以，针对任意给定的常数 $ε > 0$ ，存在另一常数 $k = O(1/ε 2)$ ，其估计的期望误差不超过 $ε$ 。例如，使用400个哈希函数值来估计 $J (A, B)$ ，其期望误差将小于或等于.05。

单一哈希函数的变种

计算多个哈希函数的代价是相当昂贵的，因此有关最小哈希方法的另一种实现方法是仅使用单一的哈希函数来避免这个问题。对于每个集合，使用这个单一的哈希函数选出其中的多个值，而不是每个哈希函数选择一个值。假定 $h$ 是一个哈希函数， $k$ 是一个固定整数。如果 $S$ 是 $h$ 域上 $k$ 或更多元素的集合，则定义 $h (k) (S)$ 为 $S$ 中具有最小 $h$ 值的 $k$ 个元素所组成的子集。该子集 $h (k) (S)$ 可用作集合 $S$ 的一个签名，任意两个集合间的相似度可通过比较它们的签名来计算。

特别地，假定A and B为任意两个集合， $X = h (k) (h (k) (A) \cup h (k) (B)) = h (k) (A \cup B)$ 是 $A \cup B$ 的k个元素的集合，如果h是随机变量并且k个元素的任意子集等可能地被选择。也就是说， $X$ 是 $A \cup B$ 的简单随机样本（英语：simple random sample）。 $Y = X \cap h (k) (A) \cap h (k) (B)$ 是集合 $X$ 中属于 $A \cap B$ 交集的元素。因此，| $Y$ |/ $k$ 是 $J (A, B)$ 的无偏估计。单一哈希函数的估计与多个哈希函数产生的估计的不同在于 $X$ 总是有 $k$ 个元素，而多个哈希函数由于两个不同的哈希函数可能会产生相同的最小值，因此可能会产生更少的样本元素。然而，当 $k$ 相对集合大小来说很小时，该区别可忽略不计。

通过不重复取样的标准Chernoff上界（英语：Chernoff bound），该估计的期望误差为 $O(1/\sqrt k)$ ，其性能与多个哈希函数方法相匹配。

耗时分析

| $Y$ |/ $k$ 估计通过给定集合的两个签名能够在 $O(k)$ 能够计算出来，因此，当 $ε$ and $k$ 为常数时，从签名中计算相似度估计的时间也为常数，这样当众多两两相似度需要计算时，该方法在运行时间上与每个集合中元素的完全比较相比，能够有实质性的优化。

最小哈希式独立排列

为了实现上述的最小哈希方法，哈希函数 $h$ 需要定义 $n$ 元素上的一个随机排列，这里的 $n$ 是指待比较的所有集合并集中不相交元素的总数。但是由于存在 $n!$ 个不同的排列，仅仅指定一个真正随机的排列就需要 $Ω(n log n)$ 位，即使 $n$ 一般时，这个数值也很大。基于这样的事实，与全域哈希（英语：universal hashing）相类似的理论，有大量的研究工作寻找“最小哈希式独立的”一簇排列，意指针对域的任意子集，任何元素都与其最小值是等可能的。已经证明，最小哈希式独立的排列簇至少必须包含: $lcm(1,2,...,n)\geq e^{n-o(n)}$ 个不同的排列，因此它需要 $Ω(n)$ 位来指定一个排列，这个数值仍然很大。^[2]

由于实践上不可行，引入了最小哈希式独立的两个变型概念：严格最小哈希式独立排列簇和近似最小哈希式独立排列簇。严格的最小哈希式独立是指最小哈希式独立属性被限制在集合基数至多为 $k$ 的一些集合中。^[4] 近似最小哈希式独立最多有一个固定的概率 $ε$ 变化为完全独立。^[5]

应用

最小哈希的最初应用包括在Web文档中聚类并消除近似重复，这通过在那些文档中出现的词语集合来描述。^[1]^[2] 相似的技术也应用于其他类型数据的聚类和近似重复消除，如图片：在图片数据中，一张图片可以通过分割用很多更小的子图片集合或更多复杂图片特征的描述集合来表示。^[6]

Schleimer, Wilkerson & Aiken (2003)使用最小哈希技术作为数字文档剽窃检测方法的一部分，他们的方法将文档表示成给定长度的子串集合，将文档划分成更大固定长度的窗口，然后使用子串的最小哈希值作为每个窗口的描述值。如果文本的拷贝部分比两倍窗口尺寸还要长，则该描述值将肯定匹配保存在数据库中众多描述值中的一个，这样那个窗口就可以用来检查有多少内容是拷贝的。^[7]

在数据挖掘领域，Cohen et al. (2001)使用最小哈希技术作为关联规则学习的工具。给定一个数据库，其中每一项都有多个属性（可看作是每行为一个数据库项，每列为一个属性的0-1矩阵），他们将最小哈希的近似度方法应用于Jaccard系数，用来辨别频繁共同出现的属性候选对，然后仅计算这些候选对的确切系数值，以确定哪些项目共同出现的频度低于一个给定的严格阈值。^[8]

参考文献

^ ^1.0 ^1.1 ^1.2 Broder, Andrei Z., On the resemblance and containment of documents, Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, 电气电子工程师学会: 21–29, 1997, doi:10.1109/SEQUEN.1997.666900 .
^ ^2.0 ^2.1 ^2.2 Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael, Min-wise independent permutations, Proc. 30th ACM Symposium on Theory of Computing (STOC '98)（英语：Symposium on Theory of Computing）, New York, NY, USA: 计算机协会: 327–336, 1998, doi:10.1145/276698.276781Proc. 30th ACM Symposium on Theory of Computing (STOC '98)（英语：-{Symposium on Theory of Computing}-）&rft.date=1998&rft.genre=bookitem&rft.pages=327-336&rft.place=New York, NY, USA&rft.pub=计算机协会&rft_id=info:doi/10.1145/276698.276781&rft_val_fmt=info:ofi/fmt:kev:mtx:book" class="Z3988"> .
^ Jaccard, Paul, étude comparative de la distribution florale dans une portion des Alpes et des Jura, Bulletin de la Société Vaudoise des Sciences Naturelles, 1901, 37: 547–579 .
^ Matou?ek, Ji?í; Stojakovi?, Milo?, On restricted min-wise independence of permutations, Random Structures and Algorithms, 2003, 23 (4): 397–408, doi:10.1002/rsa.10101 .
^ Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D., Low discrepancy sets yield approximate min-wise independent permutation families, Information Processing Letters（英语：Information Processing Letters）, 2000, 73 (1–2): 29–32, doi:10.1016/S0020-0190(99)00163-5Information Processing Letters（英语：-{Information Processing Letters}-）&rft.pages=29-32&rft.volume=73&rft_id=info:doi/10.1016/S0020-0190(99)00163-5&rft_val_fmt=info:ofi/fmt:kev:mtx:journal" class="Z3988"> .
^ Chum, Ond?ej; Philbin, James; Isard, Michael; Zisserman, Andrew, Scalable near identical image and shot detection, Proceedings of the 6th ACM International Conference on Image and Cideo Retrieval (CIVR'07), 2007, doi:10.1145/1282280.1282359 ; Chum, Ond?ej; Philbin, James; Zisserman, Andrew, Near duplicate image detection: min-hash and tf-idf weighting, Proceedings of the British Machine Vision Conference (PDF) 3: 4, 2008 [2012-05-18], （原始内容存档 (PDF)于2021-02-24） .
^ Schleimer, Saul; Wilkerson, Daniel S.; Aiken, Alex, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (SIGMOD '03): 76–85, 2003, doi:10.1145/872757.872770 .
^ Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C., Finding interesting associations without support pruning, IEEE Transactions on Knowledge and Data Engineering, 2001, 13 (1): 64–78, doi:10.1109/69.908981 .
^ Andoni, Alexandr; Indyk, Piotr, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, ACM通讯, 2008, 51 (1): 117–122, doi:10.1145/1327452.1327494 .

[b97-1] 1.0 ^1.1 ^1.2 Broder, Andrei Z., On the resemblance and containment of documents, Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, 电气电子工程师学会: 21–29, 1997, doi:10.1109/SEQUEN.1997.666900 .

[bcfm-2] 2.0 ^2.1 ^2.2 Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael, Min-wise independent permutations, Proc. 30th ACM Symposium on Theory of Computing (STOC '98)（英语：Symposium on Theory of Computing）, New York, NY, USA: 计算机协会: 327–336, 1998, doi:10.1145/276698.276781Proc. 30th ACM Symposium on Theory of Computing (STOC '98)（英语：-{Symposium on Theory of Computing}-）&rft.date=1998&rft.genre=bookitem&rft.pages=327-336&rft.place=New York, NY, USA&rft.pub=计算机协会&rft_id=info:doi/10.1145/276698.276781&rft_val_fmt=info:ofi/fmt:kev:mtx:book" class="Z3988"> .

[3] Jaccard, Paul, étude comparative de la distribution florale dans une portion des Alpes et des Jura, Bulletin de la Société Vaudoise des Sciences Naturelles, 1901, 37: 547–579 .

[4] Matou?ek, Ji?í; Stojakovi?, Milo?, On restricted min-wise independence of permutations, Random Structures and Algorithms, 2003, 23 (4): 397–408, doi:10.1002/rsa.10101 .

[5] Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D., Low discrepancy sets yield approximate min-wise independent permutation families, Information Processing Letters（英语：Information Processing Letters）, 2000, 73 (1–2): 29–32, doi:10.1016/S0020-0190(99)00163-5Information Processing Letters（英语：-{Information Processing Letters}-）&rft.pages=29-32&rft.volume=73&rft_id=info:doi/10.1016/S0020-0190(99)00163-5&rft_val_fmt=info:ofi/fmt:kev:mtx:journal" class="Z3988"> .

[6] Chum, Ond?ej; Philbin, James; Isard, Michael; Zisserman, Andrew, Scalable near identical image and shot detection, Proceedings of the 6th ACM International Conference on Image and Cideo Retrieval (CIVR'07), 2007, doi:10.1145/1282280.1282359 ; Chum, Ond?ej; Philbin, James; Zisserman, Andrew, Near duplicate image detection: min-hash and tf-idf weighting, Proceedings of the British Machine Vision Conference (PDF) 3: 4, 2008 [2012-05-18], （原始内容存档 (PDF)于2021-02-24） .

[7] Schleimer, Saul; Wilkerson, Daniel S.; Aiken, Alex, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (SIGMOD '03): 76–85, 2003, doi:10.1145/872757.872770 .

[8] Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C., Finding interesting associations without support pruning, IEEE Transactions on Knowledge and Data Engineering, 2001, 13 (1): 64–78, doi:10.1109/69.908981 .

[9] Andoni, Alexandr; Indyk, Piotr, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, ACM通讯, 2008, 51 (1): 117–122, doi:10.1145/1327452.1327494 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]