|
In [[informatica]] e in [[data mining]], l''''''algoritmo Apriori''''' è un classico [[algoritmo]] di ricerca delle associazioni. È utilizzato 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 è 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
:<math>A \rightarrow B \rightarrow D \rightarrow C</math>.
=== PseudocodificaPseudocodice ===
''Apriori'' <math>(T,\varepsilon)</math>
{{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]]
[[fa:الگوریتم آپریوری]]
[[fr:Algorithme APriori]]
[[nl:A-priori algoritme]]
[[pt:Algoritmo apriori]]
[[ru:Алгоритм Apriori]]
[[zh:先验算法]]
| 