Indietro

ⓘ Algoritmo apriori




                                     

ⓘ 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 lalgoritmo parte dalla considerazione che se un insieme di oggetti è frequente, allora anche tutti i suoi sottoinsiemi sono frequenti, ma se un itemset non è frequente, allora neanche gli insiemi che lo contengono sono frequenti.

Un ambito dove questo algoritmo trova grande applicabilità è il market/basket problem. 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 lalgoritmo termina quando non ci sono ulteriori estensioni possibili. In questo processo, il numero delle iterazioni è k m a x + 1 {\displaystyle k_{max}+1}, dove k m a x {\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.

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 {\displaystyle 2^{|S|}-1} sottoinsiemi propri, dove S è il gruppo di elementi specifico Supporto in cui un particolare sottoinsieme di oggetti compare.

                                     

1.1. Esempi Insiemi frequenti

I passi dellalgoritmo per trovare gli insiemi frequenti L {\displaystyle L} nel Database D {\displaystyle D}:

a. ricerca di insiemi frequenti L k − 1 {\displaystyle L_{k-1}} b. passo di Join C k {\displaystyle C_{k}} generato con un join di L k − 1 {\displaystyle L_{k-1}} con se stesso c. passo di Pruning qualunque k − 1 − i t e m s e t {\displaystyle k-1-itemset} non frequente non può essere un sottoinsieme frequente k − i t e m s e t {\displaystyle k-itemset}, perciò sarà rimosso

dove C k {\displaystyle C_{k}} è il candidato itemset di grandezza k {\displaystyle k} e dove inoltre L k {\displaystyle L_{k}} è litemset frequente di grandezza k {\displaystyle k}

                                     

1.2. Esempi 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 {\displaystyle k} nodi, in modo seriale, a partire da itemset di grandezza k − 1 {\displaystyle k-1}. Ad esempio, con k = 4 {\displaystyle k=4}, supponiamo che ci siano due di tali insiemi di grandezza k − 1 {\displaystyle k-1}

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

e

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

ebbene i due itemset candidati generati saranno

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

e

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

1.3. Esempi Pseudocodifica

Apriori T, ε {\displaystyle T,\varepsilon}

L 1 ← { {\displaystyle L_{1}\gets \{} large 1-itemsets } {\displaystyle \}} k ← 2 {\displaystyle k\gets 2} while L k − 1 ≠ ∅ {\displaystyle L_{k-1}\neq \varnothing } C k ← {\displaystyle C_{k}\gets } Generate L k − 1 {\displaystyle L_{k-1}} for transactions t ∈ T {\displaystyle t\in T} C t ← {\displaystyle C_{t}\gets } Subset C k, t {\displaystyle C_{k},t} for candidates c ∈ C t {\displaystyle c\in C_{t}} c o u n t \geq \varepsilon \}} k ← k + 1 {\displaystyle k\gets k+1} return ⋃ k L k {\displaystyle \bigcup _{k}L_{k}}