Minハッシュで局所性に敏感なハッシュ

Question

Min HashでLSH（局所的に敏感なハッシング）を実装するためのチュートリアル、ドキュメント、コードをたくさん読んでいます。

LSHは、ランダムサブセットをハッシングし、それらを積み重ねることによって2セットのJaccard係数を見つけようとします。私はcode.google.comの実装を見てきましたが、その方法も理解できませんでした。私は論文Google news personalization: scalable online collaborative filteringを理解していますが、そこの実装については理解できません。

MinHashでLSHを実装する方法を簡単に説明できますか？

Answer 1

上記の用紙へのリンクがありません。

ではなく、 LSH自体を実装する必要があります。 Min-Hashing は LSHのテクニックです。したがって、LSHは一般的にJaccard係数に近似しない​​が、Min-Hashingの特定の方法はそうである。

紹介はMining of Massive Datasets, Chapter 3 by Anand Rajaraman and Jeff Ullmanです。

Answer 2

セットのMIN-ハッシュ表現は、2分間のハッシュセット間で共有ハッシュの相対数として与えられ、ジャカード類似性を推定する有効な手段である。

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