Apri il menu principale

Algoritmo apriori

algoritmo informatico di ricerca delle associazioni

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]

Indice

EsempiModifica

Insiemi frequentiModifica

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  

CandidatiModifica

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

 .

PseudocodificaModifica

Apriori  

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

NoteModifica