Oggi voglio analizzare ed illustrare uno dei task maggiormente ricorrenti quando si ha a che fare con operazioni di Data Mining, l' Association Mining. Farò riferimento sia all' implementazione fornita all' interno della suite di algoritmi di Data Mining inclusi in SSAS che ad ulteriori approcci maggiormente efficienti.Defiamo innanzitutto che cosa sia l'Association Mining con riferimento a possibili contesti applicativi.

Un algoritmo di Association Mining permette di identificare all' interno di un insieme di prodotti (itemset) delle regole che correlano la presenza di un insieme di prodotti con quella di un altro insieme; vengono quindi dapprima estratti dei pattern frequenti e successivamente create delle regole di associazione che descrivono come i vari item (item) co-occorrano all' interno ad esempio di un database transazionale. Chiariamo meglio il concetto con un esempio autoesplicativo; supponiamo di dover effettuare data mining su un database transazionale di un supermercato (scusate l'originalità!!!); gli acquisti dei clienti del supermercato vengono quindi memorizzati come transazione nel database transazionale; ogni transazione conterrà quindi una lista di item (latte,birra,mele....) acquistati da un cliente in una visita al supermercato

Lo schema precedente illustra le due fasi principali che caratterizzano un algoritmo di Association Mining. La fase computazionalmente più onerosa e critica per le prestazione dell' intero sistema è la prima ovvero quella in cui si cerca di estrarre i pattern frequenti( itemset con supporto maggiore della soglia di supporto minimo). Per comprendere meglio la terminologia presente nello schema dobbiamo dare alcune definizioni che ci permettono di descrivere lo scenario di mining in termini maggiormente appropriati; gli elementi che entrano in gioco sono:

• Un insieme I= i1,i2,i3....iN di item distinti
• Una transazione T vista come sottoinsieme di I, T c I
• Una regole associativa espressa nella forma A-->B dove A e B sono itemset tali che AcT, BcT ed A intersezione B={insieme vuoto}

Per eseguire l'estrazione dei pattern frequenti e delle regole di associazione si utilizzano due indici che vanno sotto il nome di Supporto e Confidenza(Probabilità)

• Supporto (Support)
  • Misura statistica che fornisce la popolarità di un itemset, viene quindi definito per un itemset A come numero di transazioni checontengono A rapportato al numero di transazioni totali
    • Support(A)= NumTransazione(A)
• Confidenza (Conf)
  • Misura statistica legata ad un regola di associazione, indicata talvolta come probabilità condizionata, rappresenta la probabilità condizionale che una transazione che include un itemset A ne includa anche un altro B
    • Conf(A-->B) = Probabilità(B|A) = Support(A,B)/Support(A)

Come al solito un semplice esempio con riferimento alla tabella transazionale mostrata nello schema precedente ci farà prendere confidenza con gli indici di Supporto e Confidenza. Supponiamo di voler calcolare le due grandezze per la regola di associazione che ha come antecedente l' itemset composto da {Pannolini,Latte} e come conseguente {Birra}

Pannolini,Latte --> Birra

Cominciamo calcolando il supporto dell' itemset composto da {Pannolini,Latte,Birra} per poi utilizzarlo all'interno del calcolo della confidenza della regole

Support(Pannolini,Latte,Birra) =NumTransazioni(Pannolini,Latte,Birra)/NumTotaleTransazioni=2/5

Conf(Pannolini,Latte-->Birra) = Support(Pannolini,Latte,Birra)/Support(Pannolini,Latte) = 2/3 = 0.66 = 66%

La regola di associazione sopra esposta ci dice quindi che con buona probabilità (66%) un cliente che compra dei pannolini e del latte comprerà anche la birra. Per avere un'analisi qualitativa di un certo rilievo tutti i vari algoritmi di frequent pattern mining ricevono quindi come parametri di input due soglie relative al supporto ed alla confidenza minima ammissibili. Voglio evidenziare come anche all' interno di Sql Server Analysis Service sia possibile specificare il supporto e la confidenza minima anche se non è possibile assegnare valori arbitrariamente bassi in quanto SSAS effettua una stima in base alla potenza di calcolo presente sulla macchina definendo dei valori limite. Solitamente ad esempio in scenari commerciali non si scende al di sotto del' 1% di supporto. Riassumendo quanto visto finora gli algoritmi di association mining fungono da vero e proprio motore di conteggio di correlazione.

Nel prossimo post verranno analizzati gli approcci che si possono adottare nel determinare gli itemset frequenti...