Locality-Sensitive Hashing mit Min Hash

Question

Ich habe viele Tutorials, Dokumente und Codes über die Implementierung von LSH (lokal-sensitive Hashing) mit Min Hash gelesen.

LSH versucht den Jaccard-Koeffizienten von zwei Mengen zu finden, indem zufällige Teilmengen hasiert und über diese verteilt wird. Ich habe Implementierungen in code.google.com angeschaut, konnte aber deren Methode nicht verstehen. Ich verstehe das Papier Google news personalization: scalable online collaborative filtering, aber ich verstehe keine der Implementierungen da draußen.

Kann mir bitte jemand in einfachen Worten erklären, wie man LSH mit MinHash implementiert?

Answer 1

Ein Link zu dem erwähnten Papier fehlt.

Sie möchten den Min-Hash-Algorithmus aber nicht LSH per se implementieren. Min-Hashing ist eine LSH-Technik. Somit approximiert LSH im Allgemeinen nicht den Jaccard-Koeffizienten, die spezielle Methode von Min-Hashing.

Eine Einführung ist in Mining of Massive Datasets, Chapter 3 by Anand Rajaraman and Jeff Ullman gegeben.

Answer 2

Die min-Hash-Darstellung eines Satzes ist ein effizientes Mittel, um die Ähnlichkeit Jaccard Abschätzen, als die relative Zahl der gemeinsam genutzten Hashes zwischen den zwei Sätzen Hash min gegeben:

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