在计算机科学领域，最小哈希（或最小哈希式独立排列）方法是一种快速判断两个集合是否相似的技术。这种方法是由,
它同样也应用于大规模聚类问题，比如通过文档间包含的词语相似性进行聚类。
雅可比相似度与最小哈希值
雅可比相似度系数通常用来表示两个集合的相似度，定义 是一个集合， 和 是 的子集。雅可比相似度定义如下：
: J(A,B) = {\over}.
它是一个0到1之间的数值上，当其为0时表示两个集合不相交，当其为1时表示两个集合相等，其他的情况则在0和1之间。它广泛地用于两集合间相似性的判断：当雅可比系数趋向于1时，两个集合更相似；反之，当雅可比系数趋向于0时，两个集合更不相似。
定义h是一个将中的元素映射到一些不相交整数的哈希函数， 是集合 中元素的排列排列，对于任意集合S，定义为S集合中具有最小h(x)函数值的元素x，对应（集合的元素是的最小值）。将应用于 集合 和 ，假定没有发生哈希碰撞。有，当且仅当最小哈希值的并集依赖于交集时。
因此，
:
也就是说，是真的概率等于
另一方面来说，如果是一个当时值为1，其它情况下值为0的随机变量，那么可认为是的无偏估计。尽管的方差很高时，不能很好的估计雅可比相似度，因为r总是0或1。最小哈希思想通过以相同方式构造的几个变量，将其平均在一起来减少这种方差
算法
多哈希函数的变种
最简单的最小哈希方法是使用个不同的哈希函数，其中是固定的整数参数，使用这个函数所对应的个值来描述每个集合。
使用这种最简单的版本来判断，假定y是使得的哈希函数个数，使用作为估计。则此估计是个不同的0-1随机变量的平均值，其中每个随机变量当值为1，反之为0，并且是的无偏估计。因此，该平均值同样也是一个无偏估计，而且通过0-1随机变量之和的标准可得知，其期望误差是。所以，针对任意给定的常数，存在另一常数，其估计的期望误差不超过。例如，使用400个哈希函数值来估计，其期望误差将小于或等于.05。
单一哈希函数的变种
计算多个哈希函数的代价是相当昂贵的，因此有关最小哈希方法的另一种实现方法是仅使用单一的哈希函数来避免这个问题。对于每个集合，使用这个单一的哈希函数选出其中的多个值，而不是每个哈希函数选择一个值。假定是一个哈希函数，是一个固定整数。如果是域上或更多元素的集合，则定义为中具有最小值的个元素所组成的子集。该子集可用作集合的一个签名，任意两个集合间的相似度可通过比较它们的签名来计算。
特别地，假定A and B为任意两个集合，是的k个元素的集合，如果h是随机变量并且k个元素的任意子集等可能地被选择。也就是说，是的。是集合中属于交集的元素。因此，||/是的无偏估计。单一哈希函数的估计与多个哈希函数产生的估计的不同在于总是有个元素，而多个哈希函数由于两个不同的哈希函数可能会产生相同的最小值，因此可能会产生更少的样本元素。然而，当相对集合大小来说很小时，该区别可忽略不计。
通过不重复取样的标准，该估计的期望误差为，其性能与多个哈希函数方法相匹配。
耗时分析
||/估计通过给定集合的两个签名能够在能够计算出来，因此，当 and 为常数时，从签名中计算相似度估计的时间也为常数，这样当众多两两相似度需要计算时，该方法在运行时间上与每个集合中元素的完全比较相比，能够有实质性的优化。
最小哈希式独立排列
为了实现上述的最小哈希方法，哈希函数需要定义元素上的一个随机排列，这里的是指待比较的所有集合并集中不相交元素的总数。
但是由于存在个不同的排列，仅仅指定一个真正随机的排列就需要位，即使一般时，这个数值也很大。基于这样的事实，与相类似的理论，有大量的研究工作寻找“最小哈希式独立的”一簇排列，意指针对域的任意子集，任何元素都与其最小值是等可能的。已经证明，最小哈希式独立的排列簇至少必须包含:lcm(1, 2, ..., n) \ge e^{n-o(n)}个不同的排列，因此它需要位来指定一个排列，这个数值仍然很大。
近似最小哈希式独立最多有一个固定的概率变化为完全独立。
应用
最小哈希的最初应用包括在Web文档中聚类并消除近似重复，这通过在那些文档中出现的词语集合来描述。
使用最小哈希技术作为数字文档剽窃检测方法的一部分，他们的方法将文档表示成给定长度的子串集合，将文档划分成更大固定长度的窗口，然后使用子串的最小哈希值作为每个窗口的描述值。如果文本的拷贝部分比两倍窗口尺寸还要长，则该描述值将肯定匹配保存在数据库中众多描述值中的一个，这样那个窗口就可以用来检查有多少内容是拷贝的。
在数据挖掘领域，使用最小哈希技术作为关联规则学习的工具。给定一个数据库，其中每一项都有多个属性（可看作是每行为一个数据库项， 每列为一个属性的0-1矩阵），他们将最小哈希的近似度方法应用于Jaccard系数，用来辨别频繁共同出现的属性候选对，然后仅计算这些候选对的确切系数值，以确定哪些项目共同出现的频度低于一个给定的严格阈值。
相关主题
最小哈希方法可看作是的一个实例。局部性敏感哈希是使用哈希将大集合的数据对象映射到更小的哈希值的技术集合，通过这样的方法当两个对象距离相近时，它们的哈希值也可以相同。在最小哈希方法实例中，一个集合的签名可看作是它的哈希值。其它局部性敏感哈希技术还有针对集合间的海明距离，以及向量间的余弦距离等。另外，局部性敏感哈希还在最近邻搜索算法有着重要的应用。
参考文献
评论 (0)