Algoritmo apriori

In informatica e in data mining, l'algoritmo Apriori è un classico algoritmo di ricerca delle associazioni. È utilizzato per la generazione degli itemset frequenti, per approssimazioni successive, a partire dagli itemset con un solo elemento. In sintesi, il presupposto teorico su cui si basa l'algoritmo parte dalla considerazione che se un insieme di oggetti (itemset) è frequente, allora anche tutti i suoi sottoinsiemi sono frequenti, ma se un itemset non è frequente, allora neanche gli insiemi che lo contengono sono frequenti (principio di anti-monotonicità).

Un ambito dove questo algoritmo trova grande applicabilità è il market/basket problem. Per ricavare le associazioni viene impiegato un approccio bottom up, dove i sottoinsiemi frequenti sono costruiti aggiungendo un item per volta (generazione dei candidati); i gruppi di candidati sono successivamente verificati sui dati e l'algoritmo termina quando non ci sono ulteriori estensioni possibili. In questo processo, il numero delle iterazioni è $k_{max}+1$, dove $k_{max}$ indica la cardinalità massima di un itemset frequente.

Vi sono altri algoritmi con finalità analoghe (Winepi e Minepi), e che tuttavia sono più diffusi in ambiti dove i dati sono privi di timestamp (ad esempio le sequenze di DNA).

Apriori, anche se storicamente significativo, soffre di alcune inefficienze. In particolare, la generazione dei candidati crea molti sottoinsiemi. Nel processo vengono individuati i sottoinsiemi significativi solo dopo aver trovato tutti i $2^{|S|}-1$ sottoinsiemi propri, dove S è il gruppo di elementi specifico (Supporto) in cui un particolare sottoinsieme di oggetti compare.

Esempi

Insiemi frequenti

I passi dell'algoritmo per trovare gli insiemi frequenti $L$ nel Database $D$:

a. ricerca di insiemi frequenti $L_{k-1}$

b. passo di Join

$C_{k}$ generato con un join di $L_{k-1}$ con se stesso

c. passo di Pruning

qualunque $(k-1)-(itemset)$ non frequente non può essere un sottoinsieme frequente $k-(itemset)$, perciò sarà rimosso

dove $C_{k}$ è il candidato itemset di grandezza $k$ e dove inoltre $L_{k}$ è l'itemset frequente di grandezza $k$

Candidati

Questo esempio mostra il processo di selezione ovvero generazione di una lista ordinata di itemset candidati.
Il compito consiste nella costruzione di un insieme ordinato di $k$ nodi, in modo seriale, a partire da itemset di grandezza $k-1$.
Ad esempio, con $k=4$, supponiamo che ci siano due di tali insiemi di grandezza $k-1$

$A\rightarrow B\rightarrow C$,

e

$A\rightarrow B\rightarrow D$,

ebbene i due itemset candidati generati saranno

$A\rightarrow B\rightarrow C\rightarrow D$

e

$A\rightarrow B\rightarrow D\rightarrow C$.

Pseudocodice

Apriori $(T,\varepsilon )$

$L_{1}\gets \{$ large 1-itemsets $\}$

$k\gets 2$

while $L_{k-1}\neq \varnothing$

$C_{k}\gets$Generate$(L_{k-1})$

for transactions $t\in T$

$C_{t}\gets$Subset$(C_{k},t)$

for candidates $c\in C_{t}$

$\mathrm {count} [c]\gets \mathrm {count} [c]+1$

$L_{k}\gets \{c\in C_{k}|~\mathrm {count} [c]\geq \varepsilon \}$

$k\gets k+1$

return $\bigcup _{k}L_{k}$