algorithm - 使用 min-hash 实现局部敏感散列

Question

我已经阅读了很多教程、文档和使用 min-hash 实现 LSH（位置敏感散列）的代码片段。

LSH 试图通过散列随机子集并聚合它们来找到两个集合的 Jaccard 系数。我查看了 code.google.com 中的实现，但也无法理解他们的方法。我了解论文Google 新闻个性化：可扩展的在线协作过滤，但我无法理解其中的任何实现。

有人可以用简单的话解释一下如何用 MinHash 实现 LSH 吗？

Answer 1

您想实现 min-hash 算法，而不是LSH 本身。最小散列是一种 LSH 技术。因此，LSH 通常不近似 Jaccard 系数，最小散列的特定方法可以。

Anand Rajaraman 和 Jeff Ullman 在《海量数据集挖掘》第 3 章中进行了介绍。

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()