最小哈希
在计算机科学领域，最小哈希（或最小哈希式独立排列局部性敏感哈希）方法是一种快速判断两个集合是否相似的技术。这种方法是由Andrei Broder （1997）,[1]发明的，最初在AltaVista搜索引擎中用于在搜索结果中检测并消除重复Web页面。[2]
雅可比相似度与最小哈希值
雅可比相似度系数通常用来表示两个集合的相似度，定义U 是一个集合，A 和 B 是 U的子集。雅可比相似度定义如下：[3]
它是一个0到1之间的数值上，当其为0时表示两个集合不相交，当其为1时表示两个集合相等，其他的情况则在0和1之间。它广泛地用于两集合间相似性的判断：当雅可比系数趋向于1时，两个集合更相似；反之，当雅可比系数趋向于0时，两个集合更不相似。
定义h是一个将U中的元素映射到一些不相交整数的哈希函数，perm 是集合 U中元素的排列排列，对于任意集合S，定义hmin(S)为S集合中具有最小h(x)函数值的元素x，对应h ∘ perm（集合S的元素x是h(perm(x))的最小值）。将hmin应用于 集合A 和 B，假定没有发生哈希碰撞。有hmin(A) = hmin(B)，当且仅当最小哈希值的并集A ∪ B依赖于交集A ∩ B时。 因此，
- Pr[hmin(A) = hmin(B)] = J(A,B).
也就是说，hmin(A) = hmin(B)是真的概率等于J(A,B) 另一方面来说，如果r是一个当hmin(A) = hmin(B)时值为1，其它情况下值为0的随机变量，那么r可认为是J(A,B)的无偏估计。尽管r的方差很高时，不能很好的估计雅可比相似度，因为 总是0或1。最小哈希思想通过以相同方式构造的几个变量，将其平均在一起来减少这种方差
算法
多哈希函数的变种
最简单的最小哈希方法是使用k个不同的哈希函数，其中k是固定的整数参数，使用这k个函数所对应的k个hmin(S)值来描述每个集合S。 使用这种最简单的版本来判断J(A,B)，假定y是使得hmin(A) = hmin(B)的哈希函数个数，使用y/k作为估计。则此估计是k个不同的0-1随机变量的平均值，其中每个随机变量当hmin(A) = hmin(B)值为1，反之为0，并且是J(A,B)的无偏估计。因此，该平均值同样也是一个无偏估计，而且通过0-1随机变量之和的标准Chernoff上界可得知，其期望误差是O(1/√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) ∪ h(k)(B)) = h(k)(A ∪ B)是A ∪ B的k个元素的集合，如果h是随机变量并且k个元素的任意子集等可能地被选择。也就是说，X是A ∪ B的简单随机样本。Y = X ∩ h(k)(A) ∩ h(k)(B)是集合X中属于A ∩ B交集的元素。因此，|Y|/k是J(A,B)的无偏估计。单一哈希函数的估计与多个哈希函数产生的估计的不同在于X总是有k个元素，而多个哈希函数由于两个不同的哈希函数可能会产生相同的最小值，因此可能会产生更少的样本元素。然而，当k相对集合大小来说很小时，该区别可忽略不计。
通过不重复取样的标准Chernoff上界，该估计的期望误差为O(1/√k)，其性能与多个哈希函数方法相匹配。
耗时分析
|Y|/k估计通过给定集合的两个签名能够在O(k)能够计算出来，因此，当ε and k为常数时，从签名中计算相似度估计的时间也为常数，这样当众多两两相似度需要计算时，该方法在运行时间上与每个集合中元素的完全比较相比，能够有实质性的优化。
最小哈希式独立排列
为了实现上述的最小哈希方法，哈希函数h需要定义n元素上的一个随机排列，这里的n是指待比较的所有集合并集中不相交元素的总数。 但是由于存在n!个不同的排列，仅仅指定一个真正随机的排列就需要Ω(n log n)位，即使n一般时，这个数值也很大。基于这样的事实，与全域哈希相类似的理论，有大量的研究工作寻找“最小哈希式独立的”一簇排列，意指针对域的任意子集，任何元素都与其最小值是等可能的。已经证明，最小哈希式独立的排列簇至少必须包含: 个不同的排列，因此它需要Ω(n)位来指定一个排列，这个数值仍然很大。[2]
由于实践上不可行，引入了最小哈希式独立的两个变型概念：严格最小哈希式独立排列簇和近似最小哈希式独立排列簇。 严格的最小哈希式独立是指最小哈希式独立属性被限制在集合基数至多为k的一些集合中。[4] 近似最小哈希式独立最多有一个固定的概率ε变化为完全独立。[5]
应用
最小哈希的最初应用包括在Web文档中聚类并消除近似重复，这通过在那些文档中出现的词语集合来描述。[1][2] 相似的技术也应用于其他类型数据的聚类和近似重复消除，如图片：在图片数据中，一张图片可以通过分割用很多更小的子图片集合或更多复杂图片特征的描述集合来表示。[6]
Schleimer，Wilkerson & Aiken (2003)使用最小哈希技术作为数字文档剽窃检测方法的一部分，他们的方法将文档表示成给定长度的子串集合，将文档划分成更大固定长度的窗口，然后使用子串的最小哈希值作为每个窗口的描述值。如果文本的拷贝部分比两倍窗口尺寸还要长，则该描述值将肯定匹配保存在数据库中众多描述值中的一个，这样那个窗口就可以用来检查有多少内容是拷贝的。[7]
在数据挖掘领域，Cohen 等人 (2001)使用最小哈希技术作为关联规则学习的工具。给定一个数据库，其中每一项都有多个属性（可看作是每行为一个数据库项， 每列为一个属性的0-1矩阵），他们将最小哈希的近似度方法应用于Jaccard系数，用来辨别频繁共同出现的属性候选对，然后仅计算这些候选对的确切系数值，以确定哪些项目共同出现的频度低于一个给定的严格阈值。[8]
相关主题
最小哈希方法可看作是局部性敏感哈希的一个实例。局部性敏感哈希是使用哈希将大集合的数据对象映射到更小的哈希值的技术集合，通过这样的方法当两个对象距离相近时，它们的哈希值也可以相同。在最小哈希方法实例中，一个集合的签名可看作是它的哈希值。其它局部性敏感哈希技术还有针对集合间的海明距离，以及向量间的余弦距离等。另外，局部性敏感哈希还在最近邻搜索算法有着重要的应用。[9]
参考文献
- ^ 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), New York, NY, USA: 计算机协会: 327–336, 1998, doi:10.1145/276698.276781.
- ^ 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, 2000, 73 (1–2): 29–32, doi:10.1016/S0020-0190(99)00163-5.
- ^ 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.