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 è $k_{m a x} + 1$ , dove $k_{m a x}$ 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 $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 $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) - (i t e m s e t)

non frequente non può essere un sottoinsieme frequente

k - (i t e m s e t)

, 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 \to B \to C

,

e

A \to B \to D

,

ebbene i due itemset candidati generati saranno

A \to B \to C \to D

e

A \to B \to D \to C

.

Pseudocodice

Apriori $(T, ε)$

L_{1} \leftarrow {

large 1-itemsets

}

k \leftarrow 2

while

L_{k - 1} \neq \emptyset

C_{k} \leftarrow

Generate

(L_{k - 1})

for transactions

t \in T

C_{t} \leftarrow

Subset

(C_{k}, t)

for candidates

c \in C_{t}

c o u n t [c] \leftarrow c o u n t [c] + 1

L_{k} \leftarrow {c \in C_{k} | c o u n t [c] \geq ε}

k \leftarrow k + 1

return

⋃_{k} L_{k}

Note

↑ Regole associative, CNR pdf (PDF).
↑ Regole associative, UNIFE pdf (PDF) (archiviato dall'url originale il 14 maggio 2006).
↑ DataMining For Dummies (archiviato dall'url originale il 21 novembre 2010).
↑ Data Mining, Univ. Helsinki ppt (PPT).
↑ Agrawal R, Srikant R. "Fast Algorithms for Mining Association Rules", pdf (PDF), su rakesh.agrawal-family.com. URL consultato il 19 agosto 2010 (archiviato dall'url originale il 25 febbraio 2015).

Portale Informatica

Portale Matematica

[1] Regole associative, CNR pdf (PDF).

[2] Regole associative, UNIFE pdf (PDF) (archiviato dall'url originale il 14 maggio 2006).

[3] DataMining For Dummies (archiviato dall'url originale il 21 novembre 2010).

[4] Data Mining, Univ. Helsinki ppt (PPT).

[5] Agrawal R, Srikant R. "Fast Algorithms for Mining Association Rules", pdf (PDF), su rakesh.agrawal-family.com. URL consultato il 19 agosto 2010 (archiviato dall'url originale il 25 febbraio 2015).

[1]

[2]

[3]

[4]

[5]