5.2 Alberi di Decisione
5.2.1 Costruzione di un albero di decisione
Partendo da un dato insieme di attributi in linea di principio potrebbe- ro essere costruiti un numero esponenziale di alberi di decisione; dato che l’obiettivo `e quello di ottenere un albero di decisione che sia pi`u accurato possibile `e necessario un metodo per identificare l’albero ottimale. Purtrop- po tale metodo non `e disponibile, data la natura esponenziale del problema; nonostante ci`o sono stati sviluppati algoritmi in grado di produrre alberi di decisione con un buon grado di accuratezza pur mantenendo il costo com- putazionale in termini di tempo ragionevole. Questi algoritmi seguono una strategia greedy, che permette di costruire l’albero tramite un insieme otti- mo di decisioni su quale attributo utilizzare per partizionare i dati; il pi`u conosciuto di essi, nonch`e la base da cui sono stati derivati la stragrande maggioranza degli algoritmi pi`u diffusi, `e noto come Algoritmo di Hunt.
L’algoritmo di Hunt `e un algoritmo ricorsivo che permette di costruire un albero di decisione partizionando i record di allenamento in sottoinsiemi sempre pi`u omogenei, con il fine di far si che ognuno di essi contenga record aventi la medesima classe; definiamo con Dtl’insieme di record di allenamento
associati ad un nodo t e con y = y1, y2, ..., ycl’insieme delle classi da assegnare
ai record. L’albero di decisione viene costruito secondo i seguenti passi:
Passo 1: Se tutti i record in Dt appartengono alla stessa classe yt, allora t
`e un nodo foglia con classe yt.
Passo 2: Se Dt contiene record appartenenti a pi`u di una classe viene sele-
zionata una condizione di test sugli attributi in modo da partizionare l’insieme stesso in pi`u sottoinsiemi con cardinalit`a minore; un nuovo nodo figlio verr`a creato in corrispondenza di ogni possibile esito del- la condizione di test, e conterr`a ovviamente i record contenuti in Dt
che hanno dato quel risultato al test. L’algoritmo viene ricorsivamente applicato per ogni nodo figlio.
CAPITOLO 5. DATA MINING
attributi `e presente nei dati di allenamento, e contemporaneamente i record aventi la stessa combinazione di valori degli attributi devono essere associati ad un’unica classe; queste assunzioni risultano troppo stringenti nella mag- gior parte dei casi e pertanto si rendono necessarie condizioni addizionali per gestire le seguenti situazioni:
• `e possibile che alcuni nodi creati al passo 2 non contengano record. In questo caso il nodo `e una foglia con associata la stessa classe della classe pi`u frequente dei record associati al suo nodo padre;
• nel passo 2, se tutti i record associati all’insieme Dt hanno valori degli
attributi identici, eccetto per la classe, non sar`a possibile suddividerli ulteriormente; in questo caso il nodo `e dichiarato come foglia con classe associata uguale a quella della maggioranza dei record appartenenti al dato nodo.
E’ evidente che i punti chiave da affrontare per una corretta ed efficiente costruzione di un albero di decisione sono rispettivamente la scelta di come effettuare la suddivisione dei record associati ad un nodo, legata quindi a come definire le condizioni di test sugli attributi, e stabilire una condizione di stop per tale procedura di split.
5.2.2
Metodi per esprimere condizioni di test sugli at-
tributi
Il processo di costruzione di un albero di decisione deve offrire un metodo per esprimere efficientemente le condizioni di test sugli attributi per ogni pos- sibile tipo di attributo e per ogni possibile esito; i principali tipi di attributo sono i seguenti:
Attributo Binario: Una condizione di test per un attributo binario pu`o generare solo due possibili esiti, pertanto vengono generati due nodi figlio.
CAPITOLO 5. DATA MINING
Attributo Nominale: Dato che un attributo nominale pu`o avere molti va- lori, una condizione di test per un attributo nominale pu`o essere espres- sa sia generando un nodo per ogni possibile valore (multiway split ), sia generando due nodi (binary split ) ed associando ogni esito ad uno dei due raggruppando i valori in due sottoinsiemi.
Attributo Ordinale: Anche gli attributi ordinali possono avere numerosi valori, pertanto vale lo stesso ragionamento esposto per gli attributi nominali, con la differenza che, nel caso si opti per uno split binario, i raggruppamenti non devono violare l’ordine inplicito dei valori; ad esempio, se l’attributo in questione `e la ‘dimensione della t-shirt’ ed i possibili valori sono ‘small’, ‘medium’, ‘large’ ed ‘extralarge’, `e ovvio che non possiamo raggruppare nello stesso nodo i valori ‘small’ ed ‘ex- tralarge’ e nell’altro i valori ‘medium’ e ‘large’, ma ad esempio possiamo raggruppare i valori ‘small’ e ‘medium’ ed i valori ‘large’ ed ‘extralarge’.
Attributo Continuo: Per gli attributi continui la condizione di test pu`o essere espressa tramite un confronto, del tipo A > v oppure A ≤ v, con esito binario, oppure pu`o essere espressa come una query per stabilire a quale intervallo il dato valore appartiene, nella forma vi ≤ A < vi+i, i =
1, ..., k, con esito multiplo; nel caso binario viene cercato il valore di v che permetta la suddivisione migliore e vengono generati due nodi, nel caso multiplo l’algoritmo deve considerare ogni possibile intervallo di valori continui, stabilire quali e quanti intervalli definire in modo da avere la suddivisione migliore, e generare un nodo per ogni intervallo definito.
5.2.3
Metodi per selezionare i migliori split
Esistono numerosi metodi per valutare il miglior modo per effettuare la suddivisione dei record; tali metodi sono definiti in funzione della distribu- zione delle classi associate ai record prima e dopo lo split.
CAPITOLO 5. DATA MINING
Definiamo come p(i|t) la frazione di record appartenenti alla classe i in un dato nodo t. La distribuzione delle classi in un dato nodo pu`o essere espressa come (p0, p1, ..., pn−1, pn); se prendiamo ad esempio un problema di
classificazione binario, la distribuzione delle classi pu`o essere espressa come (p0, p1) dove p1 = 1 − p0.
Per la precisione, i metodi sviluppati per selezionare il miglior split soli- tamente prendono in esame il grado di impurit`a dei nodi figli; pi`u basso `e il grado di impurit`a migliore `e la suddivisione. Ad esempio, un nodo con distri- buzione delle classi uguale a (0.5, 0.5) ha impurit`a massima, mentre uno con distribuzione delle classi uguale a (0, 1) ha impurit`a uguale a zero; i metodi pi`u utilizzati per calcolare il grado di inpurit`a sono:
Entropy(t) = −
c−1
X
i=0
p(i|t) log2p(i|t), Gini(t) = 1 −
c−1
X
i=0
[p(i|t)]2, Classification Error(t) = 1 − max
i [p(i|t)],
dove c rappresenta il numero di classi e 0 log20 = 0 per il calcolo dell’entropia. Per determinare la bont`a di una condizione di test dobbiamo quindi com- parare il grado di impurit`a del nodo padre con quello dei nodi figli; maggiore `e la differenza e migliore sar`a la condizione di test. Il guadagno pu`o essere espresso come: ∆ = I(parent) − k X j=1 N (vj) N I(vj),
dove I(.) `e il grado di impurit`a di un dato nodo, N `e il numero di record appartenenti al nodo padre, k `e il numero dei valori di un attributo e N (vj)
`e il numero di record associati al nodo figlio j.
Gli algoritmi di costruzione di un albero di decisione scelgono una con- dizione di test che massimizzi il guadagno; nel caso di attributi nominali
CAPITOLO 5. DATA MINING
ci`o comporta ovviamente che le soluzioni di split multiway siano preferibili, mentre nel caso di attributi continui sono necessari degli accorgimenti per evitare problemi dal punto di vista del costo computazionale1.
5.3
Regole Associative
L’apprendimento di regole associative `e una metodologia utile per scoprire relazioni nascoste in grandi insiemi di dati[22]. Prendiamo per esempio un dataset come quello in tabella 5.12:
TID Items 1 Bread, Milk
2 Bread, Diapers, Beer, Eggs 3 Milk, Diapers, Beer, Cola 4 Bread, Milk, Diapers, Beer 5 Bread, Milk, Diapers, Cola
Tabella 5.1: Esempio di transazioni ‘basket market’
Le relazioni trovate possono essere rappresentate con regole associative come ad esempio:
Diapers =⇒ Beer
La regola suggerisce l’esistenza di una forte relazione tra la vendita di pan- nolini e birra dato che i clienti che comprano i primi solitamente comprano anche la seconda. Vediamo alcune definizioni utili:
Itemset
Un itemset `e una collezione di uno o pi`u articoli (ad esempio Milk, Bread, Diapers); un k-itemset `e un itemset composto da k articoli.
1Approfondimenti sul tema sono disponibili in [22, cap.4, par 3.4] 2La tabella `e presa da [22, table 6.1]
CAPITOLO 5. DATA MINING
Support Count
Il support count (ρ) indica la frequenza di un itemset; ad esempio ρ(M ilk, Bread, Diapers) = 1.
Support
Il supporto rappresenta la frazione di transazioni che contengono l’i- temset; ad esempio s(M ilk, Bread, Diapers) = 25.
Frequent Itemset
Si dice che un itemset `e frequente se il suo supporto `e maggiore o uguale ad una soglia predefinita, chiamata minsup.
A questo punto possiamo definire una regola associativa come una implica- zione, nella forma {X =⇒ Y }, dove X e Y sono itemset disgiunti. La forza di una regola associativa pu`o essere misurata in funzione del suo sup- porto e della sua confidenza; abbiamo gi`a visto che il supporto rappresenta la frazione di transazioni che contengono sia X che Y. La confidenza invece rappresenta quanto spesso gli articoli in Y siano presenti in una transazione contenente X:
c = ρ(M ilk, Diapers, Beer) ρ(M ilk, Beer) =
2
3 = 0.67
Il suppporto `e una misura inmportante per svariati motivi; una regola con un supporto molto basso pu`o essere frutto del caso; da un punto di vista eco- nomico una regola con supporto basso pu`o essere poco interessante ed inoltre dal punto di vista computazionale ha una propriet`a utile che verr`a mostrata in seguito. La confidenza `e altres`ı fondamentale, dato che rappresenta la sua affidabilit`a.
Il problema di scoprire regole associative, dato un insieme di transazioni, consiste nel trovare tutte le regole che hanno supporto maggiore o uguale alla soglia minsup, e confidenza maggiore o uguale della soglia minconf. Un approccio brute-force prevede il calcolo del supporto e della confidenza di ogni possibile regola, eliminando quelle che non superano le soglie; questo approccio `e ovviamente proibitivo computazionalmente, pertanto sono stati
CAPITOLO 5. DATA MINING
sviluppati algoritmi alternativi. Un primo miglioramento si ha seguendo un approccio articolato su due fasi; la prima fase, detta frequent itemset generation, ha il compito di generare gli itemset che hanno supporto maggiore alla soglia minsup, mentre la seconda, detta rule generation, ha il compito di generare regole con confidenza maggiore a minconf da ogni itemset frequente, dove ogni regola `e una partizione binaria dell’itemset frequente.
Generare gli itemset frequenti `e una procedura computazionalmente pe- sante; seguendo un approccio brute force potremmo pensare di calcolare il supporto per ogni itemset possibile, e ci`o comporta una complessit`a nell’ordi- ne di O(N M w) dove N `e il numero delle transazioni, M = 2K− 1 `e il numero
di itemset candidati (con K numero di articoli nel dataset) e w il numero massimo di articoli che compongono una transazione. Come si evince dalla formula precedente, la complessit`a computazionale pu`o essere ridotta in pi`u modi:
Ridurre il numero di candidati (M)
Dato che la ricerca completa `e computazionalmente improponibile, un approccio pu`o essere quello di ridurre M tramite tecniche di pruning. L’algoritmo A Priori segue questo principio.
Ridurre il numero di transazioni (N)
Una alternativa pu`o essere quella di ridurre il numero di transazioni prese in esame al crescere di M.
Ridurre il numero di confronti (NM)
Invece di ridurre il numero di candidati o le transazioni, `e possibile utilizzare strutture dati avanzate per la memorizzazione dei candidati e la compressione del dataset in modo da non aver bisogno di confrontare tutti i candidati con tutte le transazioni.
CAPITOLO 5. DATA MINING
5.3.1
Generazione degli itemset frequenti ed algoritmo
Apriori
Il numero di itemset candidati pu`o essere ridotto rispettando il seguente principio:
‘Apriori Principle: If an itemset is frequent, then all of its subsets must also be frequent.’ [22, cap. 6.2.1]
L’idea che sta dietro al principio `e illustrata nella figura 5.23. Supponiamo
che l’itemset {c, d, e} sia frequente; ovviamente ogni transazione che contiene il dato itemset contiene anche i suoi sottoinsiemi. Da ci`o consegue che tutti i suoi sottoinsiemi devono essere frequenti. Viceversa, se un itemset tipo {a, b} non `e frequente, allora anche tutti i suoi sovrainsiemi non possono essere frequenti. Il principio discende dal fatto che la funzione supporto applicata agli itemset `e anti-monotona[22, cap. 6.2.1]:
∀X, Y : (X ⊆ Y ) =⇒ s(X) ≥ s(Y )
Ci`o significa il supporto di un itemset non supera mai il supporto di un suo sottoinsieme; questa propriet`a pu`o essere sfruttata per effettuare un pruning degli itemset (support based pruning, rappresentato in figura 5.4).
L’algoritmo Apriori `e storicamente il primo algoritmo a sfruttare il sup- port based pruning per la generazione degli itemset candidati; nella figura 5.4 possiamo vedere come l’algoritmo genera gli itemset candidati basandosi sulla tabella 5.1. Inizialmente ogni articolo viene considerato un 1-itemset candi- dato, e per ognuno si calcola il supporto; nel nostro caso gli articoli Cola e Eggs vengono scartati perch`e non frequenti. Nell’iterazione successiva ge- neriamo gli 2-itemset candidati basandoci sugli articoli frequenti, dato che il principio Apriori ci garantisce che tutti i sovrainsiemi di un itemset non frequente devono essere non frequenti; lo stesso facciamo con i 3-itemset.
CAPITOLO 5. DATA MINING
Figura 5.2: Principio Apriori
E’ evidente il risparmio in termini di numero di itemset generati; con un approccio brute-force gli itemset candidati sarebbero stati
6 1 +6 2 +6 3 = 6 + 15 + 20 = 41
mentre rispettando il principio Apriori gli itemset candidati sono 6 1 +4 2 + 1 = 6 + 6 + 1 = 13
con un risparmio percentuale sul numero di itemset candidati generati del 68%. Nella tabella 5.2 `e riportato lo pseudocodice dell’algoritmo[22, pag. 337].
CAPITOLO 5. DATA MINING
Figura 5.3: Support Based Pruning
La funzione apriori-gen ha il compito di generare gli itemset candidati effettuando le due seguenti operazioni:
• Generazione dei candidati; • Pruning dei candidati.
Ci sono molti modi per generare gli itemset candidati; una buona procedura deve rispettare i seguenti requisiti:
• deve evitare di generare troppi itemset candidati non necessari, cio`e itemset con almeno un sottoinsieme di articoli non frequente;
• deve garantire di generare tutti gli itemset candidati frequenti; • non deve generare lo stesso itemset candidato pi`u di una volta.
CAPITOLO 5. DATA MINING
Figura 5.4: Generazione degli itemset frequenti tramite l’algoritmo Apriori
I principali metodi di generazione dei candidati sono il metodo brute-force[22, pag. 339], che considera tutti i i k-itemset come candidati ed applica il pruning per eliminare i candidati non necessari, il metodo Fk−1× F1[22, pag.
339], che estende i (k-1)-itemset frequenti con altri articoli frequenti, ed il metodo Fk−1 × Fk−1[22, pag. 341], che `e quello realmente implementato
nell’algoritmo Apriori, dove vengono uniti due (k-1)-itemset frequenti solo se hanno i primi k-2 articoli identici.
Per quanto riguarda il calcolo del supporto per gli itemset candidati che hanno superato la fase di pruning un approccio possibile pu`o essere quello di confrontare ogni transazione con ogni itemset candidato; `e evidente per`o che in questo modo abbiamo un costo computazionale notevole. Un approccio alternativo `e quello di enumerare gli itemset candidati contenuti in ogni tran- sazione in modo da utilizzarli per aggiornare il support count dei rispettivi itemset candidati[22, pag. 343]. L’algoritmo Apriori utilizza un approccio differente, dove gli itemset candidati vengono partizionati in differenti bucket e memorizzati in un albero hash, come rappresentato in figura 5.5; durante
CAPITOLO 5. DATA MINING
1: k = 1.
2: Fk= {i|i ∈ I ∧ ρ(i) ≥ N × minsup}. {Find all frequent 1-itemset}
3: repeat 4: k = k + 1.
5: Ck = apriori-gen(Fk−1). {Generate candidate itemset}
6: for each transaction t ∈ T do
7: Ct= subset(Ck, t). {Identify all candidates that belong to t }
8: for each candidate itemset c ∈ Ctdo
9: ρ(c) = ρ(c) + 1. {Increment support count} 10: end for
11: end for
12: Fk = {c|c ∈ Ck∧ ρ(c) ≥ N × minsup}. {Extract the frequent k-itemset}
13: until Fk= ∅
14: Result =S Fk.
Tabella 5.2: Pseudocodice dell’algoritmo Apriori
il calcolo del supporto anche gli itemset contenuti nelle transazioni vengono partizionati nei rispettivi bucket tramite la stessa funzione hash, in modo da confrontare ogni itemset della transazione non con tutti gli itemset candidati ma solo con quelli che appartengono allo stesso bucket.
CAPITOLO 5. DATA MINING
Come possiamo inferire dalla precedente trattazione, dal punto di vista computazionale l’algoritmo Apriori `e affetto dai seguenti fattori:
Soglia minsup
Abbassando la soglia minsup ovviamente risulteranno frequenti molti pi`u itemset, pertanto verranno generati pi`u itemset candidati con una lunghezza massima probabilmente superiore, rendendo pi`u pesanti le fasi di calcolo del supporto e incrementando il numero di iterazioni dell’algoritmo.
Numero di articoli
Aumentando il numero di articoli aumenta di conseguenza il costo in termini di spazio per memorizzarne il support count, e, se il numero di articoli frequenti aumenta proporzionalmente aumentano di conseguen- za anche gli itemset candidati con conseguente costo computazionale aggiuntivo.
Numero di transazioni
Dato che l’algoritmo Apriori effettua numerose iterazioni scandendo l’intero dataset, pi`u transazioni sono presenti pi`u la scansione `e com- putazionalmente onerosa.
Lunghezza media delle transazioni
Se abbiamo transazioni molto lunghe in media, anche la lunghezza mas- sima degli itemset frequenti tender`a a crescere con conseguente mag- gior numero di iterazioni dell’algoritmo e maggior costo in spazio per memorizzare il support count degli itemset; inoltre aumenta anche il numero di itemset in una transazione, aumentando il costo del calcolo del supporto.
Esistono metodi alternativi per generare gli itemset frequenti in modo da superare i limiti dell’algoritmo Apriori ; la trattazione di questi algoritmi `e presente in [22, cap. 6.5] e [22, cap. 6.6].
CAPITOLO 5. DATA MINING
5.3.2
Generazione delle regole
Una volta ottenuti gli itemset frequenti l’obiettivo si sposta sulla genera- zione di regole; ogni k-itemset frequente Y pu`o generare fino a 2k− 2 regole
associative, ignorando le regole che hanno l’insieme vuoto come antecedente o conseguente. Una regola associativa pu`o essere estratta partizionando Y in due sottoinsiemi non vuoti, {X} e {Y − X}, in modo che X =⇒ Y − X abbia una confidenza superiore alla soglia minconf. Calcolare la confidenza delle regole non comporta ulteriori scansioni del dataset dato che il calco- lo del supporto degli itemset frequenti `e gi`a stato effettuato nella fase di generazione dei candidati.
A differenza del supporto, la confidenza non gode di nessuna propriet`a di monotonia; se per`o restringiamo il campo alle regole generate da uno stesso itemset frequente possiamo enunciare il seguente teorema, sul quale si basa la tecnica di pruning detta confidence-based pruning:
‘If a rule X =⇒ Y −X does not satisfy the confidence threshold, then any rule X0 =⇒ Y − X0, where X’ is a subset of X, must not satisfy the confidence threshold as well.’[22, pag. 350]
L’algoritmo Apriori usa un approccio a livelli per generare le regole asso- ciative; inizialmente vengono generate tutte le regole ad alta confidenza, cio`e che hanno confidenza maggiore di minconf, che hanno un solo articolo come conseguente. Esse vengono utilizzate per generare nuove regole candidate; ad esempio, se {acd} =⇒ {b} e {abd} =⇒ {c} sono regole associative ad alta confidenza allora la regola candidata {ad} =⇒ {bc} verr`a generata unendo i termini conseguenti delle regole precedenti. Nella figura 5.6 `e rap- presentato il reticolo delle regole associative generate dall’itemset frequente {abcd}; come si pu`o vedere in figura, se troviamo un nodo nel reticolo che ha bassa confidenza tutto il sottografo da lui generato pu`o essere eliminato direttamente, secondo il teorema precedentemente introdotto.
CAPITOLO 5. DATA MINING
Figura 5.6: Pruning delle regole associative tramite il calcolo della confidenza
Nelle tabelle 5.3 e 5.4 `e descritto in pseudocodice l’algoritmo di generazio- ne delle regole associative per l’algoritmo Apriori. Da notare la somiglianza della procedura ap-genrules con la procedura di generazione degli itemset frequenti descritta nella tabella 5.2; l’unica differenza sta nel non dover ef- fettuare una nuova scansione del dataset per calcolare il support count, come detto precedentemente.
1: for each frequent k-itemset fk, k ≥ 2 do
2: H1 = {i|i ∈ fk}. {1-item consequents of the rule}
3: callap − genrules(fk, H1)
4: end for
Tabella 5.3: Pseudocodice della fase di generazione di regole associative per l’algoritmo Apriori
CAPITOLO 5. DATA MINING
1: k = |fk|. {size of frequent itemset}
2: m = |Hm|. {size of rule consequent}
3: if k > m + 1 then
4: Hm+1 = apriori-gen(Hm).
5: for each hm+1 ∈ Hm+1do
6: conf = ρ(fk)/ρ(fk− hm+1).
7: if conf ≥ minconf then
8: output the rule (fk− hm+1) =⇒ hm+1.
9: else 10: delete hm+1 from Hm+1. 11: end if 12: end for 13: call ap-genrules(Fk, Hm+1). 14: end if
Tabella 5.4: Pseudocodice della procedura ap-genrules
Rappresentazione compatta degli itemset frequenti
Nella pratica il numero di itemset frequenti prodotti da una transazione pu`o essere molto grande, pertanto `e utile identificare un piccolo insieme di itemset dal quale tutti gli altri possono essere derivati. Un possibile approccio si basa sul concetto di itemset frequente massimale:
‘A maximal frequent itemset is defined as a frequent itemset for which none of its immediate supersets are frequent’[22, pag. 354]
Il concetto `e illustrato in figura 5.7; gli itemset nel reticolo sono divisi in due gruppi, frequenti e non frequenti, e gli itemset {a, d}, {a, c, e} e {b, c, d, e} sono massimali perch`e nessuno dei suoi immediati sovrainsiemi `e frequente.