Gli alberi decisionali sono una serie di algoritmi di classificazione supervisionata molto popolari. Hanno buone prestazioni, sono semplici e veloci da addestrare e inoltre sono anche utilizzabili per la regressione (oltre che per la classificazione).
Oggi sono anche conosciuti con il nome “CART”: Classification and Regression Trees. Hanno il grande vantaggio della interpretabilità delle decisioni, cosa non frequente negli algoritmi.

Un albero decisionale è una struttura simile a un diagramma di flusso composta da nodi e rami. In ogni nodo viene eseguita una suddivisione dei dati in base a una delle caratteristiche in ingresso, generando due o più rami in uscita. Nei nodi successivi vengono effettuate sempre più suddivisioni e viene generato un numero crescente di rami per suddividere i dati originali. Questo processo continua finché non viene generato un nodo in cui i dati appartengono alla stessa classe e non sono più possibili ulteriori suddivisioni.
Per capire come funziona un albero, prendiamo l’esempio della concessione di un prestito (Fig.1 sotto).

Innanzitutto, l’algoritmo verifica se il cliente ha una buona storia creditizia. In base a ciò classifica il cliente in due gruppi: clienti affidabili e clienti meno raccomandabili. Si controlla poi il reddito (Income) del cliente e lo si classifica nuovamente in due gruppi. Infine si verifica l'importo del prestito (Loan amount) richiesto. In base ai risultati della verifica di queste tre caratteristiche, l'albero decisionale decide se il prestito del cliente debba essere approvato o meno (ciò è quanto accade oggi in banca…).
Un albero decisionale prende una serie di decisioni in base a un insieme di caratteristiche e attributi presenti nei dati. 

L'obiettivo di questi algoritmi è quello di suddividere ad ogni passo ricorsivamente il training set in sottoinsiemi, fino a quando ogni partizione è il più “pura” possibile in termini di classe di uscita. Per decidere quale caratteristica porti al sottoinsieme più corretto, occorre essere in grado di misurare la “purezza” del set di dati.

Le metriche più utilizzate sono “information gain” e l’indice di Gini. In fondo all’articolo ho inserito le modalità di calcolo di questi indici.
Ci sono due modi per evitare che un albero vada in overfitting, ovvero che diventi troppo specializzato e che non riconosca bene nuovi dati mai visti precedentemente: la potatura (pruning) e l'arresto anticipato.
La potatura viene applicata a un albero decisionale dopo la fase di addestramento. In pratica si lascia che l'albero sia libero di crescere quanto consentito dalle sue impostazioni, senza applicare alcuna restrizione esplicita. Alla fine, si procede a tagliare i rami che non sono popolati in modo adeguato. La loro rimozione dovrebbe favorire la generalizzazione su nuovi dati non visti.
L’altra opzione per evitare l'overfitting è l'arresto anticipato.
Un criterio di arresto comune è il numero minimo di campioni per nodo. Il ramo interromperà la sua crescita quando verrà creato un nodo contenente un numero di campioni di dati inferiore o uguale al numero minimo impostato. Ciò si fa per mantenere la leggibilità dell’albero.

I Random Forest risolvono il problema dell'overfitting perché combinano il risultato di più alberi decisionali per elaborare una previsione finale. Quando si crea un albero decisionale, una piccola modifica nei dati porta a un'enorme differenza nella previsione del modello. Con Random Forest questo problema non si verifica poiché i dati vengono campionati molte volte prima di generare una previsione. Questo viene fatto usando una tecnica chiamata bagging.

Nel bagging vengono addestrati più modelli dello stesso tipo su dataset diversi, ciascuno ottenuto dal dataset iniziale tramite campionamento casuale con rimpiazzo (bootstrap). Il nome bagging deriva dalla combinazione delle parole inglesi bootstrap e aggregation, in riferimento all'aggregazione di più modelli. Il bootstrap è una tecnica di campionamento e i dati di training sono campionati più volte in modo da generare diversi dataset, costruendo un albero per ognuno e ottenendone le previsioni. La previsione di ciascun albero decisionale verrà combinata per ottenere un unico risultato. Per la Regressione si calcola il valore medio delle previsioni mentre per la Classificazione vince la previsione scelta a maggioranza fra tutti gli alberi.   

ll bagging è una procedura che viene applicata per ridurre la varianza dei modelli di machine learning. Nell’algoritmo Random Forest non vengono campionate casualmente solo le righe, ma anche le variabili (colonne). Si fa questo per evitare la similarità degli alberi, producendo potenzialmente lo stesso risultato.

Esiste un altro tipo di apprendimento d'insieme chiamato Gradient Boosting, che utilizza la tecnica del “boosting”. L'idea principale alla base di questo algoritmo è quella di costruire modelli in sequenza, con i modelli successivi che cercano di ridurre gli errori del modello precedente.

La differenza fra il Random Forest e gli algoritmi basati sul boosting è che il R.F. fa la media dei risultati ottenuti da ogni singolo albero, quindi in parallelo, mentre il boosting continua a creare nuovi alberi cercando di migliorare i risultati del precedente, quindi in serie.

Dalla tecnica del boosting deriva uno dei più potenti algoritmi attualmente in uso: il XGBoost, presentato nel 2014. È uno degli algoritmi più popolari al momento perché è vincente in innumerevoli competizioni e fornisce prestazioni comparabili se non migliori delle Reti Neurali per database di non enormi dimensioni.

In conclusione, le Random Forest in genere hanno prestazioni migliori rispetto agli alberi decisionali singoli, anche se sono più lente poiché è necessario più tempo per costruire più alberi. Gli alberi decisionali sono più facili da interpretare e da visualizzare ed è facile capire come l'algoritmo abbia raggiunto il suo risultato.

L’algoritmo XGBoost è estremamente potente, di uso un po’ più complesso e, purtroppo, non permette una spiegazione chiara di come giunge alle sue conclusioni.

Con l’information gain si usa un parametro basato sull’entropia, un concetto utilizzato per misurare l'informazione o il disordine, con la formula indicata sotto la Fig. 4.

L'entropia è una metrica che misura l'impurità di una divisione in un albero decisionale. Determina come l'albero decisionale sceglie di partizionare i dati.

I valori di entropia vanno da 0 a 1, come si può vedere dalla figura 4.
Supponiamo nel nostro foglio Excel di avere una colonna con solo due classi, ad esempio “funzionante” e “non funzionante”. La prima rappresenta il 70% dei dati e la seconda il 30%.
Calcoliamo l’entropia:
Entropia = -[0,7 * log2 (0,7) + 0,3 * log2 (0,3)] = -07 * -0,51+ 0,3 * -1,74 = 0,88  

Faremo questo calcolo per ogni colonna del nostro foglio Excel per decidere quale sarà il primo nodo e dovremo ripeterlo ad ogni foglia. Si usa il valore più basso, confrontando le classi. L’information gain misura la riduzione dell'entropia durante la costruzione di un albero decisionale.
L’indice di Gini calcola la quantità di probabilità di una caratteristica specifica e varia tra i valori 0 e 1, dove 0 esprime la totale purezza della classificazione, ovvero tutti gli elementi appartengono a una classe specificata, e 1 indica la distribuzione casuale degli elementi tra le varie classi. Il valore di 0,5 dell'Indice Gini mostra un'equa distribuzione degli elementi su alcune classi.
L'indice di Gini è definito come 1 meno la somma dei quadrati delle probabilità delle classi in un set di dati, come indicato nella formula sotto la Fig. 4.
La caratteristica con l'indice di Gini più basso viene utilizzata come base per la divisione successiva.
Calcoliamo l’indice di Gini con i dati precedenti: Gini Index = 1 – [(0,7)2 +(0,3 )2 ] = 0,42

Fonti e figure: www.medium.com, Wikipedia, www.kdnuggets.com

Leggi l'articolo precedente Analisi dei dati per le imprese industriali (5)