4

我试图在 python 中理解/实现基于 minHash 的 jaccard 相似性。主要目标是在 MapReduce 中使用它。但是我不清楚哈希函数和签名长度的选择如何影响计算jaccard相似度的错误率。从维基百科中，我发现与计算的 jaccard 相似度相关的签名 (K) 和错误 (e) 的一般长度是 k = O(1/e^2)。我尝试在 python 中实现 minHash：

import random
import sys

#ERROR_THRESHOLD = 0.05
#SIG_LENGTH = int(1/(ERROR_THRESHOLD**2))
_memomask = {}

def hash_values(n, x):
    """Compute n different hash values"""
    values = []
    for i in range(n):
        mask = _memomask.get(i)
        if mask is None:
            random.seed(i)
            mask = _memomask[i] = random.getrandbits(32)
        values.append((hash(str(x)) % mask))
    return values


def compare_signatures(x, y):
    """Compare MinHash Signatures"""
    size = len(x)

    if size != len(y): raise Exception("Different signature length")
    if size == 0: raise Exception("signature length is zero")

    counter = 0
    for i in range(size): counter += int(x[i] == y[i])
    return counter/float(size)

items = [['A',3], ['A',6], ['A',9], ['B',2], ['B',4], ['B',6], ['B',8]]

for SIG_LENGTH in [1, 10, 100, 400, 1000]:
    #Step 1: Compute Hash Signature for each token
    data = []
    for item in items:
        values = hash_values(SIG_LENGTH, item[1])
        key = item[0]    
        data.append((key, values))

    #Step 2: Group by Key and compute MinHash for each index
    signatures = {}
    for item in data:
        key = item[0]
        values = item[1]
        if key not in signatures: signatures[key] = [-1.0]*SIG_LENGTH
        cur_signature = signatures[key]   

        signatures[key] = [(values[i] if cur_signature[i] == -1.0 else min(values[i], cur_signature[i])) for i in range(SIG_LENGTH)]

    #Step 3: Compute Probability of minHash signature to be same
    keys = signatures.keys()
    key_length = len(keys)
    print "Jaccard Similarity based on signature of length {0}".format(SIG_LENGTH)
    for i in range(key_length):
        x_key = keys[i]
        x_sig = signatures[x_key]
        for j in range(i+1,key_length):
            y_key = keys[j]
            y_sig = signatures[y_key]
            print "J({0},{1}) = {2}".format(x_key, y_key, compare_signatures(x_sig, y_sig))

在我的测试中，我发现准确度随着签名长度的增加而增加，但随后它开始下降（或保持稳定）。我想知道是不是因为选择了哈希函数。如果是，有人可以建议使用一个好的散列函数。

我找到了一些相关的帖子，但仍然不清楚： minhash 算法中需要多少个哈希函数

4

3 回答 3

1

md5 和 sha 工作得很好：

import random
import hashlib
import sys

k = int(sys.argv[1])
salts = [random.getrandbits(32) for i in range(k)]

def h(value, salt):
    m = hashlib.md5() #or hashlib.sha1()
    m.update(str(value))
    m.update(str(salt))
    return m.digest()

def get_signatures(A):
    return [min([h(x, salt) for x in A]) for salt in salts]

def compare_signatures(A, B):
    """Compare MinHash Signatures"""
    sigA = get_signatures(A)
    sigB = get_signatures(B)
    return sum(map(lambda x: int(sigA[x] == sigB[x]), range(k)))/float(k)

A = [3,6,9]
B = [2,4,6,8]

print compare_signatures(A, B)

和一些测试：

$ for((i=10;i<2000;i*=10)); do python minhash.py $i; done
0.2
0.14
0.163
于 2014-02-02T15:05:52.737 回答
0

生成大量散列函数的一种方法是使用不同的种子。喜欢在createHashFunctions 这里。

于 2014-02-20T02:02:57.053 回答
0

您问 1）minhash 算法的最佳哈希数是多少，以及 2）您是否使用了正确的哈希函数。

1) 你提到：k = O(1/e^2)。如果 e 指的是错误，这是正确的。您也可以将其表示为订单上的预期错误 (epsilon) (1/k**0.5)。请记住，这是该算法将收敛的平均预期误差，不一定是特定比较的预期误差。

2）您可以使用任何随机散列函数，只要每个散列的盐分不同。64 位哈希可能是我推荐的最小的。我会避免使用 MD5 或 SHA，因为您不需要这里的开销。请务必根据操作系统的大小取散列的模数，例如。Python 中的 sys.maxsize()。如果您不这样做，那么您将遇到算法行为不正确的情况。

于 2015-01-13T22:58:54.950 回答