使用Min-hash实现局部敏感哈希

Question

我已经阅读了很多关于使用min-hash实现LSH（局部敏感哈希）的教程、文档和代码片段。

LSH通过对随机子集进行哈希并对其进行聚合来查找两个集合的Jaccard系数。我看过code.google.com上的实现，但无法理解它们的方法。我理解Google新闻个性化：可扩展的在线协作过滤这篇论文，但是我无法理解任何其他实现。

有人能否用简单的语言向我解释如何使用MinHash实现LSH呢？

- Majic Johnson

Answer 1

你想实现min-hash算法，但不是LSH本身。Min-hashing是一种LSH技术。因此，通常情况下，LSH不能近似Jaccard系数，而min-hashing方法可以。 《海量数据挖掘》第3章Anand Rajaraman和Jeff Ullman中给出了介绍。

- Stefan

Answer 2

集合的最小哈希表示是一种有效的估计Jaccard相似度的方法，它给出了两个最小哈希集之间共享哈希的相对数量：

import random



def minhash():
    d1 = set(random.randint(0, 2000) for _ in range(1000))
    d2 = set(random.randint(0, 2000) for _ in range(1000))
    jacc_sim = len(d1.intersection(d2)) / len(d1.union(d2))
    print("jaccard similarity: {}".format(jacc_sim))

    N_HASHES = 200
    hash_funcs = []
    for i in range(N_HASHES):
        hash_funcs.append(universal_hashing())

    m1 = [min([h(e) for e in d1]) for h in hash_funcs]
    m2 = [min([h(e) for e in d2]) for h in hash_funcs]
    minhash_sim = sum(int(m1[i] == m2[i]) for i in range(N_HASHES)) / N_HASHES
    print("min-hash similarity: {}".format(minhash_sim))



def universal_hashing():
    def rand_prime():
        while True:
            p = random.randrange(2 ** 32, 2 ** 34, 2)
            if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)):
                return p
    m = 2 ** 32 - 1
    p = rand_prime()
    a = random.randint(0, p)
    if a % 2 == 0:
        a += 1
    b = random.randint(0, p)
    def h(x):
        return ((a * x + b) % p) % m
    return h




if __name__ == "__main__":
    minhash()

- k3f9f2kf2