Hashing sensibile al contesto con Min Hash

Question

Ho letto un sacco di tutorial, documenti e codici sull'implementazione di LSH (hashing localmente sensibile) con Min Hash.

LSH tenta di trovare il coefficiente Jaccard di due set sottoponendo a sottoinsiemi casuali e aggrandendosi su quelli. Ho esaminato le implementazioni in code.google.com ma non sono riuscito a capire il loro metodo. Capisco il documento Google news personalization: scalable online collaborative filtering, ma non riesco a capire nessuna delle implementazioni là fuori.

Qualcuno può spiegarmi in parole semplici come implementare LSH con MinHash?

Answer 1

Manca un collegamento alla suddetta carta.

Si desidera implementare l'algoritmo min-hash ma non LSH di per sé. Min-Hashing è una tecnica LSH. Quindi, l'LSH in generale non si avvicina al coefficiente di Jaccard, lo fa il metodo particolare di Min-Hashing.

Un'introduzione è fornita in Mining of Massive Datasets, Chapter 3 by Anand Rajaraman and Jeff Ullman.

Answer 2

La rappresentazione min-hash di un insieme è un mezzo efficace per stimare la somiglianza Jaccard, dato come il numero relativo di hash condivise tra i set hash due minimo:

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