Min Hash를 이용한 지역성에 민감한 해싱

Question

Min Hash를 사용하여 LSH (로컬에 민감한 해싱) 구현에 대한 많은 자습서, 문서 및 코드를 읽었습니다.

LSH는 무작위 부분 집합을 해싱하고 그 부분 집합을 해싱하여 두 세트의 Jaccard 계수를 찾으려고 시도합니다. code.google.com에서 구현을 살펴 보았지만 메소드를 이해할 수 없었습니다. 나는 논문 Google news personalization: scalable online collaborative filtering을 이해하지만, 거기에있는 구현을 이해하는 데 실패합니다.

누군가 MinHash와 함께 LSH를 구현하는 방법을 간단히 설명해 주시겠습니까?

Answer 1

언급 된 용지에 대한 링크가 없습니다.

이 아닌 최소 해시 알고리즘을 구현하려는 경우 LSH 그 자체입니다. 최소 해싱 은 LSH 기법 인입니다. 따라서, LSH는 일반적으로 Jaccard 계수를 근사하지 않으며, Min-Hashing의 특정 방법은이를 수행합니다.

소개는 Mining of Massive Datasets, Chapter 3 by Anand Rajaraman and Jeff Ullman입니다.

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