Home Introduzione Data Mining Miglioramenti A-Priori
Il market/basket problem descrive una categoria di problemi
nella quale data una grande massa di dati o oggetti generici si
cercano quei dati che compaiono insieme con frequenza
rilevante.
Definiamo supporto il numero di carrelli/transazioni in
cui un particolare sottoinsieme di articoli (itemset)
compare.
Fatta questa importante premessa, diciamo che lo scopo
dell'analisi di associazioni è estrarre delle regole di
associazione del tipo X-->Y, dove Y deve accadere con una
probabilità minima che noi chiamiamo confidenza.
Nelle applicazioni pratiche ci interessano quelle regole che
hanno un alto supporto, cioè si verificano in molti
carrelli/transazioni, perchè sono economicamente
più interessanti.
La confidenza misura l'attendibilità dell'inferenza
prodotta, ed è una sorta di probabilità
condizionata.
Quindi dato un alto supporto e un'alta confidenza, mostriamo
degli algoritmi che hanno lo scopo di estrarre insiemi frequenti
da una famiglia di oggetti.
Il più famoso tra questi è l'A-priori che si basa
sul principio secondo cui se un insieme è frequente,
allora ogni suo sottoinsieme deve essere frequente, detto
principio di monotonicità.
Lo schema dell'algoritmo A-priori è il seguente (si noti
come procede a livelli):