Introduzione

La lezione si focalizza sulla seconda parte dell'argomento "frequent item set", un problema centrale nel data mining per identificare regolarità o schemi di co-occorrenza nei dati. Verranno trattati diversi algoritmi tra cui:

• Algoritmo a priori

• Algoritmo PCY (Park Cheng You)

• Algoritmi multi stage

• Algoritmi multi-hash

• Frequent Item Set con numero di passaggi minori uguali a 2

Algoritmo a Priori

Descrizione generale

L'algoritmo a priori è uno dei più influenti e ampiamente adottati metodi per l'identificazione di frequent item set. La sua semplicità deriva dall'approccio iterativo e dal principio di monotonicità (o "downward closure property"). Il costo principale è legato ai molteplici accessi al disco (I/O), ovvero i passaggi effettuati sui dati memorizzati, che possono diventare onerosi per dataset molto grandi. Si tratta di un algoritmo a passaggi iterativi (tipicamente 2 o più), mirato all'individuazione di item set frequenti di dimensioni crescenti.

Caratteristiche

• Passaggi: Tipicamente 2 o più, a seconda della dimensione massima degli item set cercati.

• Obiettivo: Individuare item set (elementi singoli, coppie, terne, ecc.) frequenti.

• Monotonicità: Il principio di monotonicità (o "apriori property") è fondamentale:

  • Se un item set è frequente (cioè ha un supporto maggiore o uguale alla soglia $s$), allora tutti i suoi sottoinsiemi devono essere anch'essi frequenti.

  • Inversamente, se un item set non è frequente, allora qualsiasi suo superset (insieme che lo include) non può essere frequente. Questo principio permette di potare efficacemente lo spazio di ricerca dei candidati.

Passaggio 1: Identificazione degli elementi frequenti

Nel primo passaggio, si esegue una scansione completa del dataset (leggendo tutti i basket) per identificare gli elementi singoli (1-itemset) che soddisfano la soglia di supporto minimo $s$.

• Obiettivo: Contare le occorrenze di ogni singolo elemento.

• Accesso al disco: Richiede un accesso completo al disco per leggere tutti i basket.

• Memoria richiesta: Proporzionale al numero di elementi distinti presenti nel dataset per memorizzare i loro conteggi.

• Risultato: Viene generata una lista $L_1$ contenente tutti gli elementi singoli che sono risultati frequenti. Gli elementi non frequenti vengono scartati.

Passaggio 2: Conto delle coppie frequenti

Nel secondo passaggio, utilizzando la lista $L<em>1$ di elementi frequenti ottenuta nel Passaggio 1, si generano i candidati 2-itemset ($C</em>2$). Questi candidati sono tutte le possibili coppie formate dagli elementi in $L_1$.

• Generazione dei candidati: Vengono considerate solo le coppie composte da elementi che sono risultati frequenti individualmente, sfruttando il principio di monotonicità.

• Accesso al disco: Richiede una seconda scansione completa del dataset per contare le occorrenze di questi candidati 2-itemset.

• Memoria richiesta: Per gestire i conteggi dei candidati 2-itemset, la memoria richiesta può essere proporzionale al quadrato del numero di elementi frequenti in $L_1$, dato che si devono tenere i conteggi per ogni possibile coppia.

Rappresentazione dello stato della memoria

Un diagramma può rappresentare il passaggio attraverso la memoria principale, indicando le operazioni effettuate durante ciascun passaggio. Un approccio comune per rappresentare i conteggi dei frequent item set, specialmente per le coppie (2-itemset), è l'uso di una matrice triangolare superiore. Invece di una matrice sparsa completa, dove gran parte delle celle sarebbero vuote, una matrice triangolare riduce lo spazio di memoria poiché la coppia $(i, j)$ è la stessa della coppia $(j, i)$, e gli elementi non vengono abbinati con sé stessi. Questo è particolarmente utile per gruppi di item poco densi.

Estensione a dimensioni superiori

L'algoritmo a priori è di natura iterativa e può essere esteso per identificare frequent item set di qualsiasi dimensione (k > 2). Il processo si articola in fasi successive:

1. Generazione dei candidati $C<em>k$: Basandosi sulla lista $L</em>{k-1}$ di item set frequenti di dimensione $(k-1)$, si generano i candidati di dimensione $k$ ($C_k$). Questa fase di "join" e "prune" crea tutte le possibili combinazioni che potrebbero essere frequenti, usando il principio di monotonicità per eliminare i candidati che contengono sottoinsiemi non frequenti.

2. Conteggio: Si esegue una scansione del dataset per contare il supporto di ciascun candidato in $C_k$.

3. Selezione dei frequenti $L<em>k$: Si selezionano da $C</em>k$ gli item set che superano la soglia di supporto $s$, formando la lista $L_k$.

Questo processo si ripete fino a quando non si trovano più frequent item set o la lista dei candidati diventa vuota.

Algoritmo PCY

Descrizione e innovazioni

L'algoritmo PCY (Park-Chen-Yu) è un miglioramento dell'algoritmo a priori progettato per affrontare il problema del bottleneck della memoria nel secondo passaggio di Apriori, quando il numero di candidati 2-itemset è molto elevato. L'innovazione principale consiste nell'utilizzo più efficiente della memoria disponibile in RAM durante il primo passaggio.

Passaggio 1

Nel primo passaggio di PCY, mentre si conteggiano gli elementi singoli (come in Apriori), si effettua anche un'operazione aggiuntiva. Si prendono tutte le possibili coppie di elementi (anche non frequenti individualmente) presenti in un basket e per ciascuna coppia si calcola un valore hash. Questo valore hash viene utilizzato per indirizzare la coppia a un bucket in una tabella hash mantenuta in memoria.

• Scansione: Si scansiona il dataset una volta.

• Conteggio elementi: Si contano le occorrenze di ogni singolo item (come in Apriori $L_1$).

• Tabella hash (bucket count): Contemporaneamente, per ogni coppia $(i, j)$ in un basket, si calcola hash(i, j) \to \text{bucket_index} e si incrementa un contatore per quel bucket_index. La tabella hash non memorizza le coppie effettive, ma solo il conteggio di quante coppie diverse sono mappate a quel bucket.

Passaggio 2: Conteggio delle coppie frequenti

Dopo il primo passaggio, la tabella hash viene analizzata. Se un bucket della tabella hash ha un conteggio superiore alla soglia $s$, quel bucket viene etichettato come "frequente". Questo significa che è probabile che contenga almeno una coppia frequente. Al contrario, se un bucket non è frequente, sappiamo con certezza che nessuna coppia in quel bucket può essere frequente.

Nel secondo passaggio, si generano i candidati 2-itemset. Una coppia $(i, j)$ viene considerata un candidato solo se:

1. Ambedue gli elementi $i$ e $j$ sono frequenti individualmente (cioè appartengono a $L_1$).

2. La coppia $(i, j)$ mappa a un bucket nella tabella hash che è stato etichettato come "frequente".

Questa strategia riduce drasticamente il numero di candidati 2-itemset da contare nella seconda scansione, migliorando l'efficienza rispetto ad Apriori.

Gestione della memoria

Per ottimizzare ulteriormente la gestione della memoria, dopo il primo passaggio, la tabella hash (che conteneva i conteggi dei bucket) viene spesso convertita in una bitmap. Ogni bit nella bitmap corrisponde a un bucket: un 1 indica che il bucket è frequente, un 0 che non lo è. Questo consente di rappresentare le informazioni sulla frequenza dei bucket utilizzando molta meno memoria rispetto ai conteggi interi, liberando spazio per altri scopi o per dataset più grandi.

Algoritmo Multi-Stage

Descrizione generale

L'algoritmo Multi-Stage è un'evoluzione dell'algoritmo PCY che introduce più passaggi hash (o "stage") tra la prima e la seconda scansione del dataset. L'obiettivo principale è quello di ridurre progressivamente il numero di candidati "falsi positivi" prima del conteggio finale delle coppie.

Innovazioni chiave

L'idea è di applicare diverse funzioni hash (o ripetizioni della stessa funzione hash) in passaggi intermedi sulla stessa scansione dei dati. Ad esempio, dopo il primo passaggio, si potrebbe avere una prima tabella hash che indica i bucket frequenti (come PCY). Poi, in una fase intermedia, si può applicare una seconda funzione hash a tutte le coppie che hanno superato il primo filtro (ovvero che mappano a un bucket frequente nella prima tabella hash). Questi ulteriori filtri riducono ulteriormente i candidati: una coppia deve soddisfare non solo le condizioni di PCY, ma anche essere mappata a un bucket frequente in tutte le tabelle hash intermedie. Questo processo iterativo di "hashing e pruning" consente di minimizzare i falsi positivi (coppie che mappano a un bucket frequente ma non sono frequenti esse stesse) e di ridurre significativamente il carico computazionale della scansione finale per il conteggio.

Algoritmo Multi-Hash

Descrizione

L'algoritmo Multi-Hash può essere visto come un'estensione o una variazione degli algoritmi PCY e Multi-Stage, progettata per migliorare l'efficienza nel rilevamento degli item set frequenti. Si distingue per l'utilizzo di più funzioni hash indipendenti e contemporanee già nel primo passaggio, invece di funzioni hash sequenziali o "multi-stage".

Innovazioni

L'algoritmo Multi-Hash mira a raggiungere l'efficienza in termini di passaggi sul disco. Utilizzando, ad esempio, due (o più) tabelle hash (ciascuna con la propria funzione hash e bitmap) in parallelo durante il primo accesso al disco, si può filtrare in modo più aggressivo il set di candidati 2-itemset.

• Nel Passaggio 1, si scansiona il dataset, si contano gli item singoli ($L<em>1$) e, per ogni coppia $i, j$, si calcola $h</em>1(i, j)$ e $h_2(i, j)$, incrementando i rispettivi bucket-count nelle due tabelle hash separate. Dopo la scansione, si convertono entrambi i conteggi in bitmap.

• Nel Passaggio 2, una coppia $(i, j)$ è considerata candidata solo se $i \in L<em>1$, $j \in L</em>1$, e se $h<em>1(i, j)$ punta a un bucket frequente E $h</em>2(i, j)$ punta a un bucket frequente. Questa condizione congiunta permette di ottenere un filtro più selettivo riducendo ancora di più i falsi positivi rispetto a PCY, mantenendo comunque soli due passaggi sul dataset.

Algoritmi a Passaggi Minori o Uguali a 2

Random Sampling

Il Random Sampling (campionamento casuale) è una tecnica per ridurre il numero di passaggi sul disco, o addirittura tentare di eseguire l'analisi in un singolo passaggio, processando solo una piccola frazione del dataset totale.

• Funzionamento: Si seleziona un sottoinsieme casuale (campione) dei basket originali. Su questo campione ridotto, si possono applicare algoritmi come Apriori o PCY con soglie di supporto relative al campione.

• Vantaggi: Significativa riduzione dei tempi di I/O e computazionali, specialmente per dataset molto grandi.

• Svantaggi e imprecisioni: Poiché si lavora su un sottoinsieme, si introducono margini di errore:

  • Falsi positivi: Un item set può essere frequente nel campione ma non nel dataset completo.

  • Falsi negativi: Un item set può essere frequente nel dataset completo ma non essere rilevato nel campione, a causa della sua scarsa rappresentazione.

Per mitigare questi errori, si possono usare soglie di supporto più basse per il campione o tecniche di stima statistica, ma l'accuratezza rimane una sfida.

Algoritmo SON

L'Algoritmo SON (Savasere-Omiecinski-Navathe), spesso associato al paradigma MapReduce, è un algoritmo a due passaggi progettato per trovare frequent item set su dataset distribuiti o molto grandi che non possono essere contenuti in un'unica macchina.

• Passaggio 1 (Map): Il dataset viene logicamente diviso in $p$ partizioni (chunk). Per ogni partizione, si esegue in parallelo una versione modificata dell'algoritmo Apriori (o un altro algoritmo come PCY) per trovare tutti gli item set che sono localmente frequenti in quella partizione. Un item set è localmente frequente se il suo supporto nella partizione supera una soglia ridotta ($s/p$). Questi candidati locali vengono raccolti.

• Passaggio 2 (Reduce): Tutti i candidati locali ottenuti da tutte le partizioni vengono aggregati per formare un insieme globale di candidati. Si esegue una seconda scansione completa del dataset (o delle partizioni) per contare il supporto reale di tutti questi candidati globali in relazione all'intero dataset. Solo gli item set che superano la soglia globale $s$ sono dichiarati frequenti.

• Vantaggi: Adatto per ambienti distribuiti, evita la necessità di mantenere tutti i dati in un'unica posizione o di fare numerosi I/O su un singolo disco.

Domande Riepilogative

Alla fine della lezione, vengono sollevate domande legate ai concetti chiave per favorire la comprensione finale. Alcuni esempi includono:

• Qual è l'idea principale dell'algoritmo a priori?

• Come possono gli algoritmi PCY e multistage migliorare la gestione della memoria?

• Quali sono i vantaggi e gli svantaggi di random sampling e SON nel contesto delle analisi di mercato?