minhash算法中需要多少个哈希函数

Question

我很想尝试实现minhashing以找到接近重复的内容.http://blog.cluster-text.com/tag/minhash/有一个很好的写作,但是有一个问题是你需要在文档中的带状符号中运行多少哈希算法才能获得合理的结果.

上面的博客文章提到了200个散列算法.http://blogs.msdn.com/b/spt/archive/2008/06/10/set-similarity-and-min-hash.aspx将100列为默认值.

显然,随着哈希数量的增加,准确度会有所提高,但有多少哈希函数是合理的？

引用博客

很难让我们的相似性估计误差小于[7%]因为统计采样值上的误差条缩放 - 将误差条减半,我们需要四倍的样本.

这是否意味着将哈希数减少到12(200/4/4)之类的结果会导致错误率为28%(7*2*2)？

Answer 1

生成200个哈希值的一种方法是使用良好的哈希算法生成一个哈希值,并通过对具有与良好哈希值相同长度的199组随机查找位对良好哈希值进行异或运算来廉价地生成199个值(即,如果您的良好的散列是32位,构建199个32位伪随机整数的列表,并且每个良好的散列与199个随机整数中的每一个进行异或.

难道不如果你使用无符号整数(有符号整数很好),只需旋转位就可以便宜地生成哈希值 - 这通常会反复选择相同的木瓦.将位向下旋转1与将2除以并将旧的低位复制到新的高位位置相同.大约50%的良好散列值在低位中将具有1,因此它们将具有巨大的散列值,而当低位旋转到高位位置时不会成为最小散列.当你移位一位时,另外50%的好哈希值将简单地等于它们的原始值除以2.除以2不会改变哪个值最小.所以,如果给出具有良好散列函数的最小散列的shingle恰好在低位中具有0(50%的可能性),则当你移位一位时它将再次给出最小散列值.作为一个极端的例子,如果具有来自良好散列函数的最小散列值的木瓦恰好具有散列值0,则无论您旋转多少位,它总是具有最小散列值.有符号整数不会出现此问题,因为最小哈希值具有极端负值,因此它们往往在最高位后跟零,后跟零(100 ...).因此,在向下旋转一位后,只有最低位为1的哈希值才有可能成为新的最低哈希值.如果具有最小散列值的木瓦在最低位中具有1,则在向下旋转一位之后它将看起来像1100 ...,

Answer 2

差不多......但是28%将是"误差估计",这意味着报告的测量结果通常不准确+/- 28%.

这意味着报告的78%的测量结果很容易只有50%的相似性.或者50%的相似性很容易被报告为22%.对我而言,听起来不够准确,无法满足商业期望.

在数学上,如果你报告两位数,那么第二位应该是有意义的.

为什么要将哈希函数的数量减少到12？"200哈希函数"的真正含义是,为每个木瓦/字符串计算一次体面质量的哈希码 - 然后应用200个廉价和快速的变换,以强调某些因素/将某些位带到前面.

我建议结合按位旋转(或混洗)和XOR运算.每个散列函数可以组合旋转一定数量的位,然后通过随机生成的整数进行异或.

这两者都"扩展"min()函数对位的选择性,以及min()最终选择的值.

旋转的基本原理是"min(Int)"将是256次中的255次,仅在8个最高有效位中选择.只有当所有顶部位都相同时,较低的位才会在比较中产生任何影响.因此,扩展可能有助于避免过度强调木瓦中的一个或两个字符.

XOR的基本原理是,就其本身而言,按位旋转(ROTR)可以在50%的时间内(当0位从左侧移入时)收敛到零,这将导致"单独"散列函数显示不合需要的倾向于一起向零重合 - 因此他们最终倾向于选择相同的木瓦,而不是独立的带状疱疹.

有一个非常有趣的"按位"有符号整数的怪癖,其中MSB是负数但后面的所有位都是正数,这使得旋转收敛的趋势对于有符号整数更不可见- 这对于无符号整数来说是显而易见的.无论如何,仍然必须在这些情况下使用XOR.

Java内置了32位哈希码.如果您使用Google Guava库,则可以使用64位哈希码.

感谢@BillDimm的投入和坚持,指出XOR是必要的.

Answer 3

您可以通过通用散列轻松获得所需内容.像Corman等人这样的流行教科书在第11.3.3页第265-268页中作为非常易读的信息.简而言之,您可以使用以下简单公式生成哈希函数族:

h(x,a,b) = ((ax+b) mod p) mod m

• x是您想要哈希的关键
• a是您可以在1到p-1之间选择的任何奇数.
• b是您可以在0到p-1之间选择的任何数字.
• p是一个大于x的最大可能值的素数
• m是哈希码+ 1所需的最大可能值

通过选择a和b的不同值,您可以生成许多彼此独立的哈希码.

该公式的优化版本可以在C/C++/C#/ Java中实现如下:

(unsigned) (a*x+b) >> (w-M)

这里,-w是机器字的大小(通常为32) - M是您想要的位的哈希码的大小 - a是适合机器字的任何奇数 - b是小于2 ^(wM)的任何整数

以上工作用于散列数字.要散列字符串,请使用内置函数(如GetHashCode)获取可以获得的哈希码,然后在上面的公式中使用该值.

例如,假设您需要200个16位哈希码用于字符串s,那么下面的代码可以写成实现:

public int[] GetHashCodes(string s, int count, int seed = 0)
{
    var hashCodes = new int[count];
    var machineWordSize = sizeof(int);
    var hashCodeSize = machineWordSize / 2; 
    var hashCodeSizeDiff = machineWordSize - hashCodeSize;
    var hstart = s.GetHashCode();
    var bmax = 1 << hashCodeSizeDiff;
    var rnd = new Random(seed);     

    for(var i=0; i < count; i++) 
    {
        hashCodes[i] = ((hstart * (i*2 + 1)) + rnd.Next(0, bmax)) >>  hashCodeSizeDiff;
    }
}

笔记:

1. 我使用哈希码字大小作为机器字大小的一半,在大多数情况下是16位.这不太理想,碰撞的可能性更大.这可以通过将所有算术升级到64位来使用.
2. 通常,您希望在上述范围内随机选择a和b.