|
In [[informatica]] e in [[data mining]], l''''''algoritmo Apriori''''' è un classico [[algoritmo]] di ricerca delle associazioni. E'È utlizzatoutilizzato per la generazione degli [[Set (informatica)|itemset]] frequenti, per approssimazioni successive, a partire dagli itemset con un solo elemento. In sintesi, il presupposto teorico su cui si basa l’algoritmol'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à]]).<ref>[{{cita testo|url=http://www.na.icar.cnr.it/~mariog/Lucidi/11LSIA-AR.pdf |titolo=Regole associative, CNR pdf]}}</ref><ref>[{{cita testo|url=http://www.ing.unife.it/informatica/SistemiInformativi/03-04/Lucidi/24-regole%20associative.pdf |titolo=Regole associative, UNIFE pdf]|urlarchivio=https://web.archive.org/web/20060514134726/http://www.ing.unife.it/informatica/SistemiInformativi/03-04/Lucidi/24-regole%20associative.pdf }}</ref>
Un ambito dove questo algoritmo trova grande applicabilità è il ''market/basket problem''.<ref>[{{cita testo|url=http://sangi1981.altervista.org/3_associationRulesApriori.html |titolo=DataMining For Dummies]|urlarchivio=https://web.archive.org/web/20101121071937/http://sangi1981.altervista.org/3_associationRulesApriori.html }}</ref> 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 è <math>k_{max}+1</math>, dove <math>k_{max}</math> indica la cardinalità massima di un itemset frequente.<br />
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]]).<ref>[http{{cita testo|url=https://www.cs.helsinki.fi/u/ronkaine/DM/luentomateriaali/DAMI-011031.ppt |titolo=Data Mining, Univ. Helsinki ppt]}}</ref></br>
'''''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 <math>2^{|S|}-1</math> sottoinsiemi propri, dove S e'è il gruppo di elementi specifico (Supporto) in cui un particolare sottoinsieme di oggetti compare.<ref>[{{Cita web |url=http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf |titolo=Agrawal R, Srikant R. "Fast Algorithms for Mining Association Rules", pdf] |accesso=19 agosto 2010 |urlarchivio=https://web.archive.org/web/20150225213708/http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf |urlmorto=sì }}</ref>
== Esempi ==
=== Insiemi frequenti ===
:a. ricerca di insiemi frequenti <math>L_{k-1}</math>
:b. passo di [[''Join]]''
:::<math>C_k</math> generato con un join di <math>L_{k-1}</math> con se stesso
:dc. passo di [[Pruning]]
:::qualunque <math>(k-1)-''(itemset'')</math> non frequente non può essere un sottoinsieme frequente <math>k-''(itemset'')</math>, perciò sarà rimosso
dove <math>C_k</math> è il candidato itemset di grandezza <math>k</math> e dove inoltre <math>L_k</math> è l'itemset frequente di grandezza <math>k</math>
dove
:(<math>C_k</math>: candidato itemset di grandezza <math>k</math>)
e
:(<math>L_k</math>: itemset frequente di grandezza <math>k</math>)
=== Candidati ===
Questo esempio mostra il processo di selezione o diovvero generazione di una lista ordinata di candidati itemset ordinaticandidati.<br />
Il compito consiste nella costruzione di un insieme ordinato di <math>k</math> nodi itemset ordinati, in modo seriale, a partire da itemset di lunghezzagrandezza <math>k-1</math>.<br />
Ad esempio, con <math>k = 4</math>, supponiamo che ci siano due di tali insiemi di lunghezzagrandezza <math>k-1</math>...<br />
:<math>A \rightarrow B \rightarrow C</math>,
e
:<math>A \rightarrow B \rightarrow D</math>,
ebbene i due itemset candidati item sets sono generati saranno
:<math>A \rightarrow B \rightarrow C \rightarrow D</math>
e
:<math>A \rightarrow B \rightarrow D \rightarrow C</math>.
=== PseudocodificaPseudocodice ===
''Apriori'' <math>(T,\varepsilon)</math>
: ''return'' <math>\bigcup_k L_k</math>
== RiferimentiNote ==
<references />
{{portale|informatica|matematica}}
[[Categoria:Algoritmi|Apriori]]
[[Categoria:TeorieTeoria sudelle basebasi di dati]]
[[Categoria:Terminologia informatica]]
[[Categoria:Data mining]]
[[Categoria:Teoria della computazione]]
[[Categoria:Matematica applicata]]
[[de:Apriori-Algorithmus]]
[[en:Apriori algorithm]]
[[es:Algoritmo apriori]]
[[nl:A-priori algoritme]]
[[ru:Apriori]]
| 