Basso Supporto - Alta
Confidenza
Traduzione e Integrazione
delle Lezioni a cura di Sandro Gallo
Home Algoritmi Randomizzati
Min-Hashing
Partendo dal modello market-basket, possiamo dire che è
frequente e importante dovere estrarre regole da dati che hanno
un basso supporto.
Noi vedremo i nostri dati come una matrice M di 0/1 con n righe
ed m colonne, dove le righe sono i carrelli e le colonne sono gli
articoli.
Possiamo dire che:
- Poiché siamo in un sistema a basso supporto, la
matrice M sarà sparsa cioè conterrà molti
zero.
- Il numero di colonne è tale che in main memory
possiamo memorizzare qualcosa per ogni colonna, ma non possiamo
memorizzare qualcosa per coppie di articoli.
- Il numero di righe è talmente alto che non entrano in
main memory.
Definiamo la densità di una colonna ci come
dove Ci è l'insieme delle righe che hanno un 1. La
similarità tra due colonne ci, cj è definita
come:
cioè la similarità è la percentuale di righe
che contengono un 1 sia in una che nell'altra colonna.
Lo scopo degli algoritmi proposti è trovare quelle
colonne, cioè quegli articoli con una similarità
superiore a una certa soglia s*.
Definiamo, inoltre, la segnature di una colonna c, sig(c), come
una hash di c tale che:
- sig(c) entra in main memory per ogni colonna c.
- Due colonne c1, c2 sono altamente simili se e solo se le loro
segnature sig(c1), sig(c2) sono altamente simili.
Home Algoritmi Randomizzati
Min-Hashing