Algoritmi Randomizzati

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Estensioni Iceberg Basso Supporto - Alta Confidenza

I metodi visti sopra sono i migliori quando vogliamo coppie frequenti, che è anche il caso comune.
Se volessimo tutti gli insiemi frequenti massimali, sarebbero necessari troppi passi con gli algoritmi descritti prima.
Sono stati sviluppati molti approcci per ottenere tutti gli insiemi frequenti in due passi o meno.
Questi sono metodi random:

1. Simple Approch:
   
   1. Seleziona un campione random di carrelli.
   2. Applica Apriori al campione.
   Scaliamo la soglia per ottenere più risultati.
2. Savasere, Omiecinski, Navathe:
   
   1. Leggi un sottoinsieme di carrelli in main memory e applica il simple approach per ottenere gli insiemi candidati.
   2. Un insieme è un candidato se è stato identificato come candidato in almeno un sottoinsieme.
   L'idea è che un insieme candidato deve essere frequente in almeno un sottoinsieme per essere un insieme frequente.
3. Toivonen:
   
   1. Seleziona un campione random di carrelli che riempie la memoria. Applica il Simple Approach abbassando la soglia in modo da non perdere insiemi frequenti.
   2. Aggiungi ai candidati la frontiera negativa, cioè quegli insiemi S tali che S non è un insieme frequente ma i suoi sottoinsiemi precedenti sono frequenti.
   3. Controlla i dati, contando gli insiemi candidati e la frontiera negativa. Se nessun membro della frontiera negativa è frequente, allora gli elementi ottenuti sono proprio i candidati.
   4. Se sfortunatamente qualche elemento della frontiera negativa risulta essere candidato, non sappiamo se qualche suo soprainsieme possa essere frequente. Quindi o ripetiamo tutto il processo o accettiamo l'ipotesi di avere qualche falso negativo.

Home Estensioni Iceberg Basso Supporto - Alta Confidenza