Algoritmo apriori

In informatica e in data mining, l'algoritmo Apriori è un classico algoritmo di ricerca delle associazioni. E' utlizzato 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 monotonicità).^[1][2]

Un ambito dove questo algoritmo trova grande applicabilità è il market/basket problem.^[3] 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 è ${\displaystyle k_{max}+1}$, dove ${\displaystyle 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).^[4]

Apriori, anche se storicamente significativo, soffre di molte inefficienze o trade-off, che hanno influenzato altri algoritmi successivi. La generazione dei candidati crea molti sottoinsiemi. L'esplorazione Bottom-up dei sottoinsiemi (in modo breadth-first trasversale sul reticolo dei sottoinsiemi) trova tutti i sottoinsiemi S massimali solo dopo aver trovato tutti i ${\displaystyle 2^{|S|}-1}$ sottoinsiemi propri.

Esempio

Questo esempio mostra il processo di selezione o di generazione di una lista di candidati itemset ordinati. Il compito consiste nella costruzione di un insieme di ${\displaystyle k}$  nodi itemset ordinati in modo seriale a partire da itemset di lunghezza ${\displaystyle k-1}$ . Ad esempio, con ${\displaystyle k=4}$ , supponiamo che ci siano due di tali insiemi di lunghezza ${\displaystyle k-1}$ ...

${\displaystyle A\rightarrow B\rightarrow C}$ ,

e

${\displaystyle A\rightarrow B\rightarrow D}$ ,

i due candidati item sets sono generati

${\displaystyle A\rightarrow B\rightarrow C\rightarrow D}$ 

e

${\displaystyle A\rightarrow B\rightarrow D\rightarrow C}$ .

Algoritmo

L'algoritmo Apriori trova gli insiemi frequenti ${\displaystyle L}$  nel Database ${\displaystyle D}$ .

• Ricerca di insiemi frequenti ${\displaystyle L_{k-1}}$ .
• Passo di Join.
  • ${\displaystyle C_{k}}$  generato con un join di ${\displaystyle L_{k-1}}$ con se stesso
• Passo di pruning.
  • Qualunque ${\displaystyle (k-1)}$  -itemset non frequente non può essere un sottoinsieme frequente ${\displaystyle k}$ -itemset, perciò sarà rimosso.

dove

• (${\displaystyle C_{k}}$ : candidato itemset di lunghezza ${\displaystyle k}$ )
• (${\displaystyle L_{k}}$ : itemset frequente di lunghezza ${\displaystyle k}$ )

Pseudocodice per l'Apriori

Apriori ${\displaystyle (T,\varepsilon )}$ 

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

${\displaystyle k\gets 2}$ 

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

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

for transactions ${\displaystyle t\in T}$ 

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

for candidates ${\displaystyle c\in C_{t}}$ 

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

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

${\displaystyle k\gets k+1}$ 

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

Riferimenti

• Agrawal R, Imielinski T, Swami AN. "Mining Association Rules between Sets of Items in Large Databases." SIGMOD. June 1993, 22(2):207-16, pdf.
• Agrawal R, Srikant R. "Fast Algorithms for Mining Association Rules", VLDB. Sep 12-15 1994, Chile, 487-99, pdf, ISBN 1-55860-153-8.
• Mannila H, Toivonen H, Verkamo AI. "Efficient algorithms for discovering association rules." AAAI Workshop on Knowledge Discovery in Databases (SIGKDD). July 1994, Seattle, 181-92, ps.

1. ^ Regole associative, CNR pdf
2. ^ Regole associative, UNIFE pdf
3. ^ DataMining For Dummies
4. ^ Data Mining, Univ. Helsinki ppt