Algoritmo apriori

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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 è , dove 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 sottoinsiemi propri, dove S è il gruppo di elementi specifico (Supporto) in cui un particolare sottoinsieme di oggetti compare.[5]

Esempi[modifica | modifica wikitesto]

Insiemi frequenti[modifica | modifica wikitesto]

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

a. ricerca di insiemi frequenti
b. passo di Join
generato con un join di con se stesso
c. passo di Pruning
qualunque non frequente non può essere un sottoinsieme frequente , perciò sarà rimosso

dove è il candidato itemset di grandezza e dove inoltre è l'itemset frequente di grandezza

Candidati[modifica | modifica wikitesto]

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 nodi, in modo seriale, a partire da itemset di grandezza .
Ad esempio, con , supponiamo che ci siano due di tali insiemi di grandezza

,

e

,

ebbene i due itemset candidati generati saranno

e

.

Pseudocodice[modifica | modifica wikitesto]

Apriori

large 1-itemsets
while
Generate
for transactions
Subset
for candidates
return

Note[modifica | modifica wikitesto]

  1. ^ Regole associative, CNR pdf
  2. ^ Regole associative, UNIFE pdf Archiviato il 14 maggio 2006 in Internet Archive.
  3. ^ DataMining For Dummies Archiviato il 21 novembre 2010 in Internet Archive.
  4. ^ Data Mining, Univ. Helsinki 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).