Min-Hashing e k-Min-Hashing
Traduzione e Integrazione
delle Lezioni a cura di Sandro Gallo
Home Basso Supporto e Alta Confidenza
Locality Sensitive Hashing(LSH) e
Hamming-LSH
Il Min-Hashing serve a generare le segnature per una matrice
sparsa M. L'idea di base è quella di permutare in maniera
random le righe e per ogni colonna ci computare il valore hash
h(ci) come l'indice della prima riga che contiene valore 1.
In realtà non verrà effettuata nessuna permutazione
delle righe ma semplicemente leggeremo in modo random le righe e
calcoleremo h(ci). Questo verrà fatto in tempo O(m), con m
= numero di colonne. Per ottenere un alto grado di
similarità tra coppie di colonne faremo k permutazioni con
il trucchetto visto sopra. Il tutto in tempo O(mk).
Tutto questo è fattibile perchè possiamo affermare
che per ogni coppia di colonne (ci, cj),
Quindi alla fine avremo costruito una nuova matrice 
con k righe ed m colonne dove
, cioè la
matrice delle segnature.
Dimostreremo, ora, che esprime/è un riassunto ben fatto di M nel
calcolo della similarità tra colonne. Prima definiamo
come la
similarità tra colonne di .
Teorema:
Sia s* la soglia minima di similarità con un limite
inferiore c, cioè s*>=c. Siano 
e 
. Allora per tutte le coppie di colonne ci e cj
noi abbiamo le seguenti due proprietà:
- Se S(ci, cj) >= s*>c, allora >= (1-d)s* con probabilità superiore a
1-e.
- Se S(ci, cj) <=c, allora <= (1+d)c con probabilità superiore a
1-e.
Dimostrazione (a)
Date due colonne ci, cj con S(ci, cj) >= s*. Sia X = X1 + X2 +
... +Xk una variabile aleatoria. Poniamo Xl = 1 se hl(ci) =
hl(cj), zero altrimenti. Sia
quindi E[X] >= ks*.
Applicando il limite di Chernoff a X otteniamo:
Quindi notando che
e quindi
.
CVD
Questo teorema stabilisce che per un k grande se due colonne ci,
cj sono altamente simili (>= s*) in M allora in le corrispondenti colonne
h(ci), h(cj) sarannno altamente simili. Lo stesso vale per la
bassa similarità.
Uno svantaggio del Min-Hashing è iterare k volte la
pseudo-permutazione delle righe e quindi fare k volte l'hash
delle colonne.
Essendo essenziale fare questo per diminuire i
falsi-positivi(cioè le coppie che non sono realmente
simili) e i falsi-negativi(cioè le coppie simili che non
entrano nella lista dei candidati), è stato sviluppato il
K-Min-Hashing che applica una sola volta l'hash prendendo
però i primi k valori per colonna.
Home Basso Supporto e Alta Confidenza
Locality Sensitive Hashing(LSH) e
Hamming-LSH