Big Data: tecnologie, metodologie e applicazioni per l'analisi ......Dati due insiemi S e T, una...

LSH - Locality Sensitive Hashing

Big Data: tecnologie, metodologie e applicazioniper l’analisi dei dati massivi

Ministero Dello Sviluppo EconomicoIstituto Superiore delle Comunicazioni e delle Tecnologie dell’Informazione

Seminario ISCOM

Simone AngeliniFondazione Ugo Bordoni

Francesca CapriUniversita di Roma Tor Vergata

6 marzo 2017

Big Data: tecnologie, metodologie e applicazioni per l’analisi dei dati massivi Simone Angelini - Francesca Capri 1 / 27

Table of Contents

1 LSH - Locality Sensitive HashingIntroduzioneLSH per similarita tra documentiBenchmarking: Hadoop vs SparkLSH per analisi statistiche su grafiBenchmarking: Spark GraphX

IntroduzioneLSH per similarita tra documentiBenchmarking: Hadoop vs SparkLSH per analisi statistiche su grafiBenchmarking: Spark GraphX

Introduzione

Problema

La ricerca della similarita tra documenti e uno dei task piu complessi inambito Big Data.

Obiettivo

Si vogliono esaminare n documenti in modo da raggruppare gli elementisimili negli stessi sottoinsiemi (bucket)

Possibile soluzione

Riduzione della complessita del problema utilizzando funzioni hash cherappresentino i documenti con una firma di interi (signature)

Introduzione

Problema

Obiettivo

Possibile soluzione

Introduzione

Problema

Obiettivo

Possibile soluzione

Alcuni campi di applicazione

La ricerca della similarita tra documenti e un problema ricorrente in uncontesto di Data Mining, e puo essere ritrovato in molti ambiti:

Near-duplicate detection (Ricerca dei duplicati, problemi di plagio)

Entity Resolution (Ricerca di profili simili in contesti differenti es.Twitter/Facebook)

Community Detection (Ricerca di comunita di utenti, in base ainteressi comuni)

Suggerimento di Sinonimi

Locality Sensitive Hashing

Cos’e

Algoritmo di riduzione dello spazio vettoriale in un insieme di n documenti

Come funziona

3 fasi:

Shingling

MinHashing

Definizione

Dati due insiemi S e T, una misura della similarita dei due insiemi e datadal coefficiente di Jaccard:

SIM(S,T) = |S∩T ||S∪T |

Cos’e

Come funziona

3 fasi:

Shingling

MinHashing

Definizione

SIM(S,T) = |S∩T ||S∪T |

Cos’e

Come funziona

3 fasi:

Shingling

MinHashing

Definizione

SIM(S,T) = |S∩T ||S∪T |

LSH: Pipeline

LSH: Shingling (1/3)

Obiettivo

Scomporre ogni documento in k-grammi, ossia in raggruppamenti di ktoken

Esempio

Documento: ”Oggi e una bella giornata, non piovera”

1-grammi: Oggi, e, una, bella, giornata, non, piovera

2-grammi: Oggi e, e una, una bella, bella giornata, giornata non,non piovera

3-grammi: Oggi e una, e una bella, una bella giornata, bella giornatanon, giornata non piovera

LSH: Shingling (1/3)

Obiettivo

Scomporre ogni documento in k-grammi, ossia in raggruppamenti di ktoken

Esempio

Documento: ”Oggi e una bella giornata, non piovera”

1-grammi: Oggi, e, una, bella, giornata, non, piovera

2-grammi: Oggi e, e una, una bella, bella giornata, giornata non,non piovera

3-grammi: Oggi e una, e una bella, una bella giornata, bella giornatanon, giornata non piovera

LSH: Minhashing(2/3)

Obiettivo

Costruire una firma (signature) di h interi associata ad ogni documento,in base a una famiglia H di funzioni hash casuali e indipendenti e aik-grammi individuati al passo precedente.

Algoritmo

1 Si applica una funzione hash a tutti gli shingle di un documento

2 Di tutti i valori ricavati dalle funzioni hash, viene selezionato ilminimo

3 Si ripete il procedimento per tutte le funzioni hi ∈ H

4 Al termine si avra un vettore di k interi, che rappresentano la firmadel documento

LSH: Minhashing(2/3)

Obiettivo

Costruire una firma (signature) di h interi associata ad ogni documento,in base a una famiglia H di funzioni hash casuali e indipendenti e aik-grammi individuati al passo precedente.

Algoritmo

1 Si applica una funzione hash a tutti gli shingle di un documento

2 Di tutti i valori ricavati dalle funzioni hash, viene selezionato ilminimo

3 Si ripete il procedimento per tutte le funzioni hi ∈ H

4 Al termine si avra un vettore di k interi, che rappresentano la firmadel documento

LSH: Locality Sensitive Hashing(3/3)

Obiettivo

Raggruppare i documenti simili in base alle firme ottenute dal Minhashing

Algoritmo

1 La matrice delle firme viene divisa in b bande di r righe ciascuna

2 I numeri b e r sono scelti in modo tale che b ∗ r = h

3 I documenti che avranno corrispondenza totale in almeno una delle bbande rispettano la regola di similarita, per cui verranno raggruppatinegli stessi bucket

LSH: Locality Sensitive Hashing(3/3)

Obiettivo

Raggruppare i documenti simili in base alle firme ottenute dal Minhashing

Algoritmo

1 La matrice delle firme viene divisa in b bande di r righe ciascuna

2 I numeri b e r sono scelti in modo tale che b ∗ r = h

3 I documenti che avranno corrispondenza totale in almeno una delle bbande rispettano la regola di similarita, per cui verranno raggruppatinegli stessi bucket

LSH: Matrice delle firme

LSH: raggruppamenti in bucket

LSH: Scelta dei valori b ed r

Obiettivo

Scelta ottimale dei parametri b e r in base all’obiettivo

Scelta

In base all’obiettivo che si vuole raggiungere, si sceglieranno dei valori dib e r piu o meno alti

aumentando la larghezza di una banda (r), si avra una similarita piurestrittiva (duplicate o near-duplicate)

aumentando il numero di bande (b), si avra una similarita piu lasca

si dimostra che la probabilita di collisione dei valori hash di duedocumenti distinti e uguale al coefficiente di Jaccard dei duedocumenti

LSH: Scelta dei valori b ed r

Obiettivo

Scelta ottimale dei parametri b e r in base all’obiettivo

Scelta

In base all’obiettivo che si vuole raggiungere, si sceglieranno dei valori dib e r piu o meno alti

aumentando la larghezza di una banda (r), si avra una similarita piurestrittiva (duplicate o near-duplicate)

aumentando il numero di bande (b), si avra una similarita piu lasca

si dimostra che la probabilita di collisione dei valori hash di duedocumenti distinti e uguale al coefficiente di Jaccard dei duedocumenti

LSH: Curva S-Shaped

Implementazione LSH - Hadoop / Spark

Dettagli implementativi

Implementazione in Java di LSH a 2 fasi (algoritmo originale)

Implementazione in Java di LSH a 4 fasi per migliorare la precisionedell’algoritmo

Ricerca di similarita tra documenti (tweet)

Ricerca di similarita tra utenti, in base al contenuto dei loro tweet

Implementazioni sia in ambiente Hadoop, sia in ambiente Spark

Comparazione tempi - Hadoop vs Spark 1/2

Comparazione tempi - Hadoop vs Spark 2/2

Grafi - Qualche definizione 1/2

Distanza tra nodi

Dato un grafo G = (V,E) di n nodi e m archi, la distanza d(u, v) tradue nodi u, v ∈ V e la lunghezza del cammino minimo da u verso v.

Diametro di un grafo

Il diametro d(G) e la distanza massima tra due nodi u, v ∈ V . In altreparole e il cammino minimo piu lungo all’interno del grafo.

Distanza tra nodi

Diametro effettivo

Il diametro effettivo deff(G) e definito come la distanza minima per cuisono raggiungibili il 90% di tutte le coppie di nodi u, v ∈ V .

Firma di un nodo

La firma sig(u) di un nodo u ∈ V e definita come una sequenza di kinteri che identifica il nodo u.

Hop-plot

Dato un grafo G = (V,E), l’hop plot di G descrive la quantita di coppiedi nodi raggiungibili in al piu h passi.

Diametro effettivo

Firma di un nodo

Hop-plot

Diametro effettivo

Firma di un nodo

Hop-plot

Stima del diametro effettivo di un grafo

Obiettivo

Dato un grafo G = (V,E), si vuole avere una stima del suo diametroeffettivo.

Assegnare una firma ad ogni nodo del grafo, per poi utilizzare la tecnicadel minhashing per stimarne il diametro effettivo.

Stima del diametro effettivo di un grafo

Obiettivo

Dato un grafo G = (V,E), si vuole avere una stima del suo diametroeffettivo.

Assegnare una firma ad ogni nodo del grafo, per poi utilizzare la tecnicadel minhashing per stimarne il diametro effettivo.

Fase 1: Signature dei nodi del grafo

Obiettivo

Costruire una firma (signature) per ogni nodo u ∈ V di k interi,utilizzando una famiglia H di k funzioni hash indipendenti.

Pseudo Codice

foreach u ∈ V doforeach hk ∈ H do

SIGk(u) := hk(u)endSIG(u) := [SIG1(u), ..., SIGk(u)]

Fase 1: Signature dei nodi del grafo

Obiettivo

Costruire una firma (signature) per ogni nodo u ∈ V di k interi,utilizzando una famiglia H di k funzioni hash indipendenti.

Pseudo Codice

foreach u ∈ V doforeach hk ∈ H do

SIGk(u) := hk(u)endSIG(u) := [SIG1(u), ..., SIGk(u)]

Fase 2: Signature del grafo

Obiettivo

Costruire la firma SIG(G) del Grafo G, prendendo il valore minimo diogni funzione hash, ∀u ∈ V .

Pseudo Codice

foreach u ∈ V doforeach k (funzione hash ) do

if SIGk(u) < SIGk(G) thenSIGk(G) := SIGk(u) ;

endSIG(G) := [SIG1(G), ..., SIGk(G)]

Fase 2: Signature del grafo

Obiettivo

Costruire la firma SIG(G) del Grafo G, prendendo il valore minimo diogni funzione hash, ∀u ∈ V .

Pseudo Codice

foreach u ∈ V doforeach k (funzione hash ) do

if SIGk(u) < SIGk(G) thenSIGk(G) := SIGk(u) ;

endSIG(G) := [SIG1(G), ..., SIGk(G)]

Fase 3: Aggiornamento della firma dei nodi

Obiettivo

Si vuole aggiornare la firma SIG(u) di ogni nodo u ∈ V , calcolando ilminhash di ogni elemento della firma del nodo, con i corrispettivi dei nodiadiacenti.

Pseudo Codice

foreach u doforeach u→ v ∈ E do

SIG(u) := Merge(SIG(u), SIG(v))end

dove la funzione Merge agisce come di seguito:

foreach k (funzione hash ) doSIGk(u) := min{SIGk(u), SIGk(v)}

Fase 3: Aggiornamento della firma dei nodi

Obiettivo

Si vuole aggiornare la firma SIG(u) di ogni nodo u ∈ V , calcolando ilminhash di ogni elemento della firma del nodo, con i corrispettivi dei nodiadiacenti.

Pseudo Codice

foreach u doforeach u→ v ∈ E do

SIG(u) := Merge(SIG(u), SIG(v))end

dove la funzione Merge agisce come di seguito:

foreach k (funzione hash ) doSIGk(u) := min{SIGk(u), SIGk(v)}

Analisi

Obiettivo

Si vuole avere una stima del numero di coppie raggiungibili nel grafo|N(G))| in al piu un passo.

Algoritmo

|N(u))| = n · Jaccard(SIG(G), SIG(u));|N(G))| = n ·

∑u Jaccard(SIG(G), SIG(N(u));

Costruzione Hop Plot

Iterando questo procedimento h volte, e possibile ottenere una stima delnumero di coppie raggiungibili del grafo in al piu h passi, permettendo dicostruire l’hop plot del grafo.

Analisi

Obiettivo

Algoritmo

Analisi

Obiettivo

Algoritmo

Conclusioni

Riepilogo statistiche

L’algoritmo presentato rende possibili diverse analisi statistiche sul grafodi input:

|N(u, h))| ∀u ∈ V,∀h|N(h))| ∀hd ≤ dMAX(G)

deff(G)

davg(G)

Benchmarking dell’algoritmo con Spark GraphX

Alcuni dettagli implementativi

Implementazione dell’algoritmo nel linguaggio Scala, nativo di Spark

Utilizzo della libreria GraphX per la gestione dei grafi

Implementazione delle funzioni hash mediante la libreria Guava diGoogle (murmur 32)

Dataset utilizzati

Black Friday World Series Italian sample

Nodi 2.7E+06 4.74E+05 2.54E+06Archi 3.8E+06 8.40E+05 1.37E+07

Alcuni dettagli implementativi

Implementazione dell’algoritmo nel linguaggio Scala, nativo di Spark

Utilizzo della libreria GraphX per la gestione dei grafi

Implementazione delle funzioni hash mediante la libreria Guava diGoogle (murmur 32)

Dataset utilizzati

Black Friday World Series Italian sample

Nodi 2.7E+06 4.74E+05 2.54E+06Archi 3.8E+06 8.40E+05 1.37E+07

Risultati

Average Diametro Diametro CoppieDistance Effettivo 90% raggiungibili

World SeriesValori esatti 8,463 11,205 27 2, 577 · 109

Stima 8,480 11,174 25 2, 562 · 109

Italian SampleValori esatti 6,398 9,315 62 3, 877 · 1011

Stima 6,419 9,318 54 3, 894 · 1011

Black FridayValori esatti 16,124 22,722 70 11, 300 · 109

Stima 16,369 22,824 66 11, 703 · 109

Ringraziamenti

Tutti gli studi e i lavori di analisi sono stati effettuati all’interno delLaboratorio Big Data di ISCOM.

Big Data: tecnologie, metodologie e applicazioni per l'analisi ......Dati due insiemi S e T, una...

Documents

Transcript of Big Data: tecnologie, metodologie e applicazioni per l'analisi ......Dati due insiemi S e T, una...