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à).^[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 alcune inefficienze. In particolare, la generazione dei candidati crea molti sottoinsiemi. Nel processo vengono individuati i sottoinsiemi significativi solo dopo aver trovato tutti i ${\displaystyle 2^{|S|}-1}$ sottoinsiemi propri, dove S è il gruppo di elementi specifico (Supporto) in cui un particolare sottoinsieme di oggetti compare.^[5]

Esempi

Insiemi frequenti

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

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

b. passo di Join

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

c. 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}}$ è il candidato itemset di grandezza ${\displaystyle k}$ e dove inoltre ${\displaystyle L_{k}}$ è l'itemset frequente di grandezza ${\displaystyle 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 ${\displaystyle k}$ nodi, in modo seriale, a partire da itemset di grandezza ${\displaystyle k-1}$.
Ad esempio, con ${\displaystyle k=4}$, supponiamo che ci siano due di tali insiemi di grandezza ${\displaystyle k-1}$

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

e

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

ebbene i due itemset candidati generati saranno

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

e

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

Pseudocodice

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}}$

Note

Portale Informatica

Portale Matematica