Approccio sperimentale
5.5 Regole di associazione
Le regole di associazione[6] permettono di estrarre in modo esaustivo patterns frequenti da un database transazionale. Ogni transazione è composta da un insieme di oggetti non ordinati. Un classico esempio di transazione è uno scontrino, che contiene l’insieme di prodotti comprati. L’insieme di questi oggetti è detto itemset.
Una regola di associazione si presenta nel formato:
A ⇒ B
con A e B itemsets, ovvero un insieme composto da uno o più oggetti. A è chiamato corpo della regola, mentre B è nominata Testa della regola. La regola così composta indica che, in un dataset transazionale, quando si trova A, si trova anche B. Si presti particolare attenzione al fatto che il simbolo ⇒ non indica causalità, bensì il fatto che corpo e testa della regola occorrono assieme. Ad ogni regola possono essere associati alcuni indici di qualità:
5.5 – Regole di associazione
• Supporto: percentuale di transazioni contenenti sia A che B.
supporto = #(A, B)
#T
con #(A, B) numero di transazioni contenenti sia A che B, e #T numero totale di transazioni. Indica quanto la regola è frequente, ovvero quanto è supportata dai dati.
• Confidence: frequenza di B in transazioni contenenti A.
conf idence = supporto(A, B) supporto(A)
Indica la "forza" della regola, ovvero qual è la probabilità di avere la testa della regola avendo il corpo della regola.
• Lift: indica il grado di correlazione del corpo e della testa della regola.
Lif t = supporto(A, B) supporto(A)supporto(B)
In particolare, lift=1 indica indipendenza statistica, ovvero la regola non è significa-tiva; se il lift è maggiore di 1 si ha una correlazione positiva, mentre se è minore di 1 si ha correlazione negativa, ovvero l’occorrenza di A implica una non-occorrenza di B.
Per famigliarizzare con gli indici di qualità della regola, si propone un esempio:
ID Items
1 Pane, Cola, Latte 2 Birra, Pane
3 Birra, Cola, Pannolini, Latte 4 Birra, Pane, Pannolini, Latte 5 Cola, Pannolini, Latte
Tabella 5.1: Esempio di dataset transazionale Estraiamo alcune regole e ne calcoliamo gli indici:
• La regola Latte ⇒ P annolini ha
supporto = #{Latte, P annolini}
#trans = 3/5 = 60%
conf idenza = #{Latte, P annolini}
#{Latte} = 3/4 = 75%
Lif t = supporto{Latte, P annolini}
supporto{Latte}supporto{P annolini} = 3/5
4/5 ∗ 3/5 = 15/12 = 1,25
• La regola P annolini ⇒ Latte ha
supporto = #{P annolini, Latte}
#trans = 3/5 = 60%
conf idenza = #{P annolini, Latte}
#{P annolini} = 3/3 = 100%
Lif t = supporto{P annolini, Latte}
supporto{P annolini}supporto{Latte} = 3/5
3/5 ∗ 4/5 = 15/12 = 1,25 Per utilizzare le regole di associazione bisogna quindi convertire un normale dataset in un dataset transazionale: ogni record del dataset diventa una transazione dove ogni oggetto è rappresentato nel formato nome_attributo = valore_attributo.
A questo punto viene usato un algoritmo di estrazione delle regole di associazione, impo-stando delle soglie per supporto e confidenza, in modo da estrarre solo regole significative e ridurre il tempo di computazione delle regole. Inoltre, le regole ottenute vengono in genere filtrate anche per vaalori di lift maggiori di 1, o comunque ordinate per valori decrescenti di esse, così da individuare le regole più importanti.
Sono presenti più algoritmi di estrazione di regole di associazione che operano in maniera diversa producendo risultati differenti. Tra questi, i migliori e più utilizzati sono l’algoritmo Apriori, che si basa sul concetto degli itemset frequenti, e l’algoritmo FP-Growth, che utilizza una struttura ad albero in modo da ridurre il numero di letture del database.
Nel nostro caso, viene utilizzato l’algoritmo Apriori, che viene approfondito nella prossima sezione.
5.5.1 Algoritmo Apriori
Per poter estrarre le regole di associazione, bisogna per prima cosa individuare gli itemset frequenti, ovvero quegli insiemi di elementi che superano la soglia di supporto impostata.
Il metodo più intuitivo per calcolare quali siano gli itemset più frequenti è quello di cal-colare tutte le possibili combinazioni di elementi e calcal-colare la loro frequenza all’interno del dataset. Ciò però è molto dispendioso, in quanto con d item disponibile, si hanno 2d itemset disponibili.
L’algoritmo a priori si propone di ridurre il numero di itemset da generare basandosi sul principio Apriori, che dice che "se un itemset è frequente, allora anche tutti i sui sottoinsiemi devono essere frequenti". Infatti il supporto di un itemset non può mai essere maggiore del supporto dei suoi subset.
Si ha un approccio a livelli: a ogni iterazione si estraggono itemset di lunghezza k. Ogni livello p composto da due passi principali:
• Generazione dei candidati: si generano i candidati di lunghezz k+1 unendo i vari itemset frequenti di lunghezza k, e poi si eliminano i candidati di lunghezza k+1 che contengono almeno un k-itemset che non è frequente.
• Generazione degli itemset frequenti: si scandisce il dataset per contare il supporto dei candidati di lunghezza k+1 rimasti, eliminando quelli che non superano la soglia.
5.5 – Regole di associazione
Il numero degli itemset frequenti può però essere molto elevato, e quindi oltre ad es-sere molto lenta la generazione dei candidati, anche il numero di accessi al dataset per il conteggio del supporto è elevato. In particolare il numero è elevato se si usa una soglia di supporto molto bassa e se il database è molto grande.
Alcune tecniche per velocizzare l’operazione è quella di alzare la soglia di supporto, rischiando di perdere però delle regole interessanti, usare funzioni statistiche per predire le frequenze invece di calcolarle e l’uso di tabelle di hash per velocizzare la ricerca dei candidati.
5.5.2 Implementazione in Python dell’algoritmo Apriori
In Python è presente una libreria che mette a disposizione delle funzioni per generare le regole di associazione a partire da un Dataframe di Pandas. La libreria si chiama mlxtend, in particolare si usano i moduli mlxtend.preprocessing per la conversione dela dataframe in database transazionale e mlxtend.frequent_patterns per estrarre le regole.
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules
dataset = [[’Milk’, ’Onion’, ’Nutmeg’, ’Kidney Beans’, ’Eggs’, ’Yogurt’], [’Dill’, ’Onion’, ’Nutmeg’, ’Kidney Beans’, ’Eggs’, ’Yogurt’], [’Milk’, ’Apple’, ’Kidney Beans’, ’Eggs’],
[’Milk’, ’Unicorn’, ’Corn’, ’Kidney Beans’, ’Yogurt’],
[’Corn’, ’Onion’, ’Onion’, ’Kidney Beans’, ’Ice cream’, ’Eggs’]]
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset) df = pd.DataFrame(te_ary, columns=te.columns_)
frequent_itemsets = apriori(df, min_support=0.6, use_colnames=True)
association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7) Il codice riportato[3] permette l’estrazione delle regole di associazione utilizzando Py-thon.
In particolare, dopo aver importato Pandas e i pacchetti necessari di Mlxtend, viene creato un Dataframe, che rappresenta il nostro dataset. Ogni riga è una rilevazione, e ogni colonna un oggetto. Con TransactionEncoder si trasforma il dataset in forma transazio-nale, in cui ogni riga è un insieme di oggetti del tipo nome_colonna=valore. Dopo aver convertito il nuovo dataset in un dataframe (poichè la funzione successiva richiede in input un oggetto del genere), si chiama la funzione apriori, che calcla il supporto di tutti gli itemset restituendo solo quelli con supporto maggiore di min_threshold.
A questo punto, con la funzione association_rules sono estratte tutte le regole, a partire dagli itemset frequenti prima calcolati, che superano la soglia min_threshold riferita alla metrica indicata in metric, che può essere una tra supporto, confidence e lift.