Quando si parla di albero decisionale si fa riferimento a una tecnica predittiva di machine learning potente e diffusa che viene utilizzata per prevedere delle variabili che possono essere discrete (e allora si parla di classificazione) o continue (in questo caso di regressione).
Un algoritmo popolare che ci permette di raggiungere questo scopo è sicuramente il CART (Classification and Regression Trees).
Prima di vedere tale metodo, dovremmo prima familiarizzare con gli alberi decisionali, in particolare con gli alberi binari, proprio perché il CART permette di rappresentare un albero di questo tipo.
Albero decisionale: alcune definizioni
Un albero è una raccolta di entità chiamate nodi collegati tra loro tramite frecce o linee. Ogni nodo contiene un valore e può avere o meno nodi figli, mentre le frecce indicano le decisioni/regole che un albero può prendere o meno.
Nell’immagine seguente vediamo subito un esempio di albero.
I nodi sono A, B, C, D, E e F e sono collegati da delle linee che indicano delle relazioni di parentela tra i vari nodi.
Il nodo A viene detto nodo radice ed è il punto di partenza dell’albero. Esso si compone di tre figli: il nodo B, il nodo C e il nodo D. L’unico nodo senza genitore è il nodo radice.
Il nodo B ha a sua volta due figli: il nodo E ed F. Questi ultimi due insieme ai nodi C e D sono chiamati nodi foglia perché si trovano nella parte inferiore dell’albero e non hanno figli. I nodi foglia rappresentano i risultati che vogliamo ottenere dal problema e che ci servono per fare previsioni su nuovi dataset.
La profondità di un albero è definita come il numero di livelli, escluso il nodo radice. L’albero sopra ha una profondità di 2 poiché il nodo B, il nodo C e il nodo D sono tutti su un livello e il nodo E e il nodo F sono su un secondo livello.
In altre parole, il numero di livelli è il numero di figli che dobbiamo attraversare dalla radice al nodo foglia più lontano. Sebbene il nodo radice A, sia al suo livello, di solito non lo includiamo quando contiamo la profondità di un albero (se dovessimo considerarlo, lo chiameremo livello 0).
L’albero sopra è un albero generale, ma non è un albero binario. Gli alberi decisionali sono alberi binari, pertanto da qua in avanti faremo riferimento solo a questa tipologia di albero. Un esempio di albero binario viene mostrato nella seguente immagine.
La condizione affinché un albero sia considerato binario è che ciascun nodo genitore deve avere al massimo 2 nodi figlio.
Se volessimo per caso rappresentare su un albero binario una variabile continua, che possiede più di due valori, come potremmo fare?
L’albero viene suddiviso in più livelli, in modo che ogni nodo padre abbia solamente due nodi figli, come mostrato nell’esempio seguente.
Supponiamo di avere diversi casi per un nodo, come nell’immagine sotto a sinistra in cui abbiamo tre regioni: (-∞, -3], (-3, 3) e [3, + ∞).
Possiamo ancora dividerlo in due decisioni binarie, come a destra. Innanzitutto, dividere in (-∞, -3] e (-3, + ∞). Successivamente possiamo dividere (-3, +∞) in due regioni: (-3, 3) e [3, +∞). Possiamo farlo per qualsiasi decisione con un numero qualsiasi di casi: dividerlo in una sequenza di decisioni binarie.
Cos’è l’algoritmo CART?
CART sta per Classification and Regression Trees ed è un algoritmo introdotto da Leo Breiman per determinare un modello predittivo di classificazione e regressione. Tale modello viene rappresentato attraverso alberi binari.
È facile da usare e può fornire rapidamente informazioni preziose su enormi quantità di dati. Inizialmente, quando si crea un albero si parte da dati che vengono detti di apprendimento. Per questo motivo si può considerare il CART come un albero decisionale di apprendimento dai dati.
La creazione di un algoritmo CART implica:
- Decidere quali caratteristiche scegliere, ossia le variabili di input;
- Quali condizioni utilizzare per la divisione;
- Definire quando fermarsi.
Una volta impostato e creato l’albero decisionale è possibile testare un nuovo set di dati, partendo dal nodo radice, per effettuare previsioni.
Decidere quali caratteristiche scegliere
Per scegliere le caratteristiche si utilizza generalmente una tecnica di Recursive Binary Splitting.
In questa procedura vengono considerate tutte le caratteristiche e diversi punti di divisione vengono provati e testati utilizzando una funzione di costo. La divisione con costo più basso è selezionata.
Nella prima divisione, o nella definizione del nodo radice, vengono considerate tutte le caratteristiche e i dati di allenamento sono divisi in gruppi o regioni in base a questa suddivisione.
Se ad esempio si hanno 3 caratteristiche, si hanno 3 divisioni candidate. Si calcola per ognuna di essa quanta accuratezza ogni divisione costerà (usando una funzione) e si sceglie quella con costo migliore.
Questo algoritmo è un algoritmo greedy ed è di natura ricorsiva poiché i gruppi formati possono essere suddivisi utilizzando la stessa strategia anche per i nodi successivi al primo.
Quali condizioni utilizzare per la divisione
La funzione di costo utilizzata per valutare le diverse divisioni è differente a seconda del tipo di problema da risolvere.
Per i problemi di modellazione predittiva di regressione, la funzione di costo è l’errore di somma al quadrato (errore quadratico o Residual squared sum, RSS) tra tutti i dati di addestramento che rientrano nella regione:
Dove y è il valore reale osservato mentre la previsione è il valore previsto (per maggiori informazioni vedi l’articolo sulla regressione lineare multipla).
Per i problemi di classificazione viene utilizzata la funzione del coefficiente di Gini che fornisce un’indicazione di quanto “puri” siano i nodi foglia.
G rappresenta il coefficiente di Gini su tutte le classi, mentre pi è la proporzione delle istanze di formazione con la classe i nella regione di interesse. Per un problema di classificazione binaria, questo può essere riscritto come:
G = 2 x p1 x p2
Che equivale a dire:
Definire quando fermarsi
Alberi decisionali con molti nodi e numero di divisioni possono portare a un sovradattamento dei dati (definito più propriamente dal termine overfitting). Ciò significa che il modello risulta di difficile interpretazione in quanto diventa inaccurato per previsioni successive.
Un modo per evitare questo problema è impostare un numero minimo di dati di allenamento da utilizzare su ciascun nodo foglia. Ad esempio, possiamo utilizzare un livello minimo di 4 per prendere una decisione e ignorare qualsiasi nodo foglia che richieda meno di 4 livelli.
Un altro modo è impostare la profondità massima del modello, che come abbiamo visto si riferisce alla lunghezza del percorso più lungo dal nodo radice al nodo foglia.
Per migliorare ulteriormente le prestazioni dell’albero è possibile utilizzare anche la tecnica Pruning.
Semplicemente, si tratta di rimuovere i rami che fanno uso di caratteristiche che hanno poca importanza. In questo modo, riduciamo la complessità dell’albero e quindi aumentiamo il suo potere predittivo (fatto che riduce a sua volta il sovradattamento).
Il metodo di Pruning più semplice inizia dalle foglie e rimuove ogni nodo con la classe più popolare in quella foglia, fermandosi prima di ridurre la precisione.
Esempio di applicazione CART
Vediamo ora un esempio di applicazione dell’algoritmo CART applicato ad un problema di classificazione.
Prendiamo semplicemente un famoso set di dati nel mondo del machine learning che è un dataset meteorologico. Per semplicità scriverò i dati in italiano (anche se il vero dataset è in inglese):
- La frequenza dei Si nella caratteristica e regola analizzate;
- La frequenza dei No nella caratteristica e regola analizzate;
- Il numero di istanze di cui è composta la caratteristica e relativa regola. Esso è la somma dei valori trovati nelle due precedenti colonne (si noti che la somma delle righe della colonna numero di istanze è pari esattamente al numero di dati di allenamento, ossia 14).
Meteo
Gini (Meteo = Soleggiato) = 1 – (2/5)2 – (3/5)2 = 1 – 0,16 – 0,36 = 0,48
Gini (Meteo = Nuvoloso) = 1 – (4/4)2 – (0/4)2 = 0
Gini (Meteo = Piovoso) = 1 – (3/5)2 – (2/5)2 = 1 – 0,36 – 0,16 = 0,48
Il coefficiente di Gini pesato per la caratteristica Meteo è dato dalla seguente espressione:
Gini (Meteo) = (5/14) x 0,48 + (4/14) x 0 + (5/14) x 0,48 = 0,171 + 0 + 0,171 = 0,342
Temperatura
Similmente, la caratteristica temperatura può assumere 3 diverse decisioni: caldo, freddo e mite. Riassumiamo le decisioni per questa caratteristica:
Gini (Temperatura = Caldo) = 1 – (2/4)2 – (2/4)2 = 1 – 0,25 – 0,25 = 0,5
Gini (Temperatura = Freddo) = 1 – (3/4)2 – (1/4)2 = 1 – 0,5625 – 0,0625 = 0,375
Gini (Temperatura = Mite) = 1 – (4/6)2 – (2/6)2 = 1 – 0,444 – 0,111 = 0,445
Il coefficiente di Gini pesato per la caratteristica Temperatura è dato dalla seguente espressione:
Gini (Temperatura) = (4/14) x 0,5 + (4/14) x 0,375 + (6/14) x 0,445 = 0,142 + 0,107 + 0,190 = 0,439
Umidità
L’umidità è una caratteristica di classe binaria. Può avere decisione Elevata o Normale.
Gini (Umidità = Elevata) = 1 – (3/7)2 – (4/7)2 = 1 – 0.183 – 0.326 = 0.489
Gini (Umidità = Normale) = 1 – (6/7)2 – (1/7)2 = 1 – 0.734 – 0.02 = 0.244
Il coefficiente Gini pesato per la caratteristica Umidità è dato dalla seguente espressione:
Gini (Umidità) = (7/14) x 0.489 + (7/14) x 0.244 = 0.367
Vento
Il Vento è una classe binaria simile all’umidità. Può assumere decisioni Debole e Forte.
Gini (Vento = Debole) = 1 – (6/8)2 – (2/8)2 = 1 – 0.5625 – 0.062 = 0.375
Gini (Vento = Forte) = 1 – (3/6)2 – (3/6)2 = 1 – 0.25 – 0.25 = 0.5
Gini (Vento) = (8/14) x 0.375 + (6/14) x 0.5 = 0.428
Scelta del nodo radice
Arrivati a questo punto non ci resta che scegliere il nodo radice dell’albero. Esso sarà dato dalla caratteristica con coefficiente di Gini pesato più basso, ossia dalla caratteristica Meteo, come possiamo vedere dalla seguente tabella:
Volendo rappresentare quanto enunciato, mostriamo una prima rappresentazione di albero, in cui i nodi rappresentano le caratteristiche, mentre le frecce le decisioni/regole che può assumere la caratteristica.
Guardando attentamente la figura precedente potrai notare che la decisione Non Soleggiato per la caratteristica Meteo non esiste. L’ho inserita poiché altrimenti avrei creato tre nodi figli per la caratteristica Meteo e non rappresentando più realmente un albero binario.
Dall’immagine precedente possiamo notare che il set di dati secondario nella decisione Nuvoloso ha solo risultati Sì (vedi colonna risultato). Ciò significa che è un nodo foglia, e possiamo rappresentarlo come un rettangolo per distinguerlo dai nodi padri.
Ora, per determinare i nodi figli, valuteremo quanto appena visto ripartendo sia per la decisione Soleggiato sia per la decisione Piovoso (quindi non si utilizzerà più la tabella iniziale per il calcolo del coefficiente di Gini, ma le tabelle appena mostrate).
Partiamo dalla tabella Soleggiato, correlandola con le altre caratteristiche Temperatura, Umidità e Vento. Successivamente tale procedura verrà eseguita anche per la tabella Piovoso.
Ovviamente il numero massimo di istanze in questo caso è pari a 5, come i record della tabella.
Meteo soleggiato e Temperatura
Gini (Meteo = Soleggiato e Temperatura = Caldo) = 1 – (0/2)2 – (2/2)2 = 0
Gini (Meteo = Soleggiato e Temperatura = Freddo) = 1 – (1/1)2 – (0/1)2 = 0
Gini (Meteo = Soleggiato e Temperatura = Mite) = 1 – (1/2)2 – (1/2)2 = 1 – 0.25 – 0.25 = 0.5
Gini (Meteo = Soleggiato e Temperatura) = (2/5) x 0 + (1/5) x 0 + (2/5) x 0.5 = 0.2
Meteo Soleggiato e Umidità
Gini (Meteo = Soleggiato e Umidità = Elevata) = 1 – (0/3)2 – (3/3)2 = 0
Gini (Meteo = Soleggiato e Umidità = Normale) = 1 – (2/2)2 – (0/2)2 = 0
Gini (Meteo = Soleggiato e Umidità) = (3/5) x 0 + (2/5) x 0 = 0
Meteo Soleggiato e Vento
Gini (Meteo = Soleggiato e Vento = Debole) = 1 – (1/3)2 – (2/3)2 = 0.266
Gini (Meteo = Soleggiato e Vento = Forte) = 1 – (1/2)2 – (1/2)2 = 0.2
Gini (Meteo = Soleggiato e Vento) = (3/5) x 0.266 + (2/5) x 0.2 = 0.466
Scelta del nodo per la variabile Soleggiato
Come per decidere il nodo radice, la scelta del primo nodo figlio è data dalla caratteristica con coefficiente di Gini Meteo Soleggiato più basso. In questo caso Umidità, vince.
L’albero prenderà seguente forma (per semplicità ora non considero le decisioni Piovoso e Nuvoloso).
Come visto, il risultato è sempre No per Elevata Umidità e Meteo Soleggiato. D’altra parte, il risultato sarà sempre Sì per Umidità Normale e Meteo Soleggiato. Siamo fortunati perché abbiamo trovato altri due nodi foglia: questo ramo è finito.
Arrivati a questo punto, dobbiamo concentrarci sulla decisione Piovoso procedendo esattamente allo stesso modo per come abbiamo fatto per il ramo Soleggiato.
Meteo Piovoso e Temperatura
Gini (Meteo = Piovoso e Temperatura = Freddo) = 1 – (1/2)2 – (1/2)2 = 0.5
Gini (Meteo = Piovoso e Temperatura = Mite) = 1 – (2/3)2 – (1/3)2 = 0.444
Gini (Meteo = Piovoso e Temperatura) = (2/5) x 0.5 + (3/5) x 0.444 = 0.466
Meteo Piovoso e Umidità
Gini (Meteo = Piovoso e Umidità = Elevata) = 1 – (1/2)2 – (1/2)2 = 0.5
Gini (Meteo = Piovoso e Umidità = Normale) = 1 – (2/3)2 – (1/3)2 = 0.444
Gini (Meteo = Piovoso e Umidità) = (2/5) x 0.5 + (3/5) x 0.444 = 0.466
Meteo Piovoso e Vento
Gini(Meteo = Piovoso e Vento = Debole) = 1 – (3/3)2 – (0/3)2 = 0
Gini(Meteo = Piovoso e Vento = Forte) = 1 – (0/2)2 – (2/2)2 = 0
Gini(Meteo = Piovoso e Vento) = (3/5) x 0 + (2/5) x 0 = 0
Decisione per il Meteo Piovoso
La caratteristica con Meteo Piovoso che presenta coefficiente di Gini pesato più basso in questo caso è il Vento.
Anche qua possiamo notare che Meteo Piovoso e Vento Debole generano il nodo foglia Si. Idem per Meteo Piovoso e Vento Forte otteniamo il nodo foglia No. Ci possiamo fermare qua, in quanto l’albero risulta completo.
Per maggiori approfondimenti sull’algoritmo CART, consiglio la lettura/visione dei seguenti link:
