Algoritmo apriori: differenze tra le versioni

Versione delle 18:04, 24 ott 2011

Versione delle 18:56, 24 mag 2012

Riga 1:

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’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>[http://www.na.icar.cnr.it/~mariog/Lucidi/11LSIA-AR.pdf Regole associative, CNR pdf]</ref><ref>[http://www.ing.unife.it/informatica/SistemiInformativi/03-04/Lucidi/24-regole%20associative.pdf Regole associative, UNIFE pdf]</ref>

Un ambito dove questo algoritmo trova grande applicabilità è il ''market/basket problem''.<ref>[http://sangi1981.altervista.org/3_associationRulesApriori.html DataMining For Dummies]</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 />