Algoritmo apriori

Da Wikipedia, l'enciclopedia libera.

In informatica e in data mining, l'Apriori è un classico algoritmo per l'apprendimento di regole d'associazione. L'Apriori opera su database contenenti transazioni (ad esempio, inisiemi di item comprati da utenti, o dettaglio sulla frequenza di visita di un sito web). Altri algoritmi sono stati scritti per la ricerca di regole d'associazione che non operano sulle transazioni (Winepi e Minepi), o privi di timestamp (sequenze di DNA).

Per il mining di regole d'associazione, dato un insieme di itemset (insiemi di item), l'algoritmo cerca di trovare sottoinsiemi di essi che siano presenti nell'insieme delle transazioni almeno S volte (dove S è il supporto definito dall'utente) L'Apriori usa un approccio "bottom up", dove i sottoinsiemi frequenti sono costruiti aggiungendo un item per volta (passo conosciuto come generazione dei candidati), i gruppi di candidati sono successivamente testati sui dati. L'algoritmo termina quando non ci sono ulteriori estensioni.

L'Apriori usa una ricerca breadth-first e una struttura hash tree per il conteggio degli insiemi di item in modo efficiente. Genera itemset candidati di lunghezza k a partire da itemset di lunghezza k − 1. Successivamente si fa pruning dei candidati con sotto-modello non frequente. Seguendo il lemma downward closure, l'insieme dei candidati conterrà tutti gli itemset frequenti di lunghezza k. Fatto ciò, l'algoritmo scansiona il database delle transazioni per determinare gli itemset frequenti fra i candidati. Per determinare gli item frequenti in modo efficiente, l'algoritmo utilizza un hash tree per memorizzare gli itemset. Questo hash tree avrà nelle foglie gli item sets e tabelle hash nei nodi interni (Zaki, 99).

Apriori, anche se storicamente significativo, soffre dimolte 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 2 ^{| S |} − 1 sottoinsiemi propri.

Indice 1 Esempio 2 Algoritmo 2.1 Pseudocodice per l'Apriori 3 Riferimenti

[modifica] 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 k nodi itemset ordinati in modo seriale a partire da itemset di lunghezza k − 1. Ad esempio, con k = 4, supponiamo che ci siano due di tali insiemi di lunghezza k − 1...

,

e

,

i due candidati item sets sono generati

e

.

[modifica] Algoritmo

L'algoritmo Apriori trova gli insiemi frequenti L nel Database D.

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

dove

• (C_k: candidato itemset di lunghezza k)
• (L_k: itemset frequente di lunghezza k)

[modifica] Pseudocodice per l'Apriori

Apriori

large 1-itemsets }

while

Generate(L_{k − 1})

for transactions

Subset(C_k,t)

for candidates

return

[modifica] 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.