Che cos'è un albero decisionale?

Come si può vedere dal diagramma seguente, un albero decisionale inizia con un nodo radice, che non ha rami in entrata. I rami in uscita dal nodo radice alimentano quindi i nodi interni, noti anche come nodi decisionali. Sulla base delle funzionalità disponibili, entrambi i tipi di nodo conducono valutazioni per formare sottoinsiemi omogenei, indicati da nodi foglia o nodi terminali. I nodi foglia rappresentano tutti i possibili risultati all'interno del set di dati.

Ad esempio, immaginiamo che tu stia cercando di valutare se andare a fare surf o meno. Per fare questa scelta, puoi utilizzare le seguenti regole decisionali:

Questo tipo di struttura di diagramma di flusso crea anche una rappresentazione facilmente comprensibile del processo decisionale, consentendo ai diversi gruppi di un'organizzazione di capire meglio perché è stata presa una determinata decisione.

L'apprendimento basato sugli alberi decisionali utilizza una strategia "divide et impera" conducendo una ricerca approfondita per identificare i punti di divisione ottimali all'interno di un albero. Questa suddivisione viene poi ripetuta in modo ricorsivo, dall'alto verso il basso, fino a quando tutti o la maggior parte dei record vengono classificati con etichette di classe specifiche.

La classificazione di tutti i punti dati come set omogenei dipende in gran parte dalla complessità dell'albero decisionale. Gli alberi più piccoli possono raggiungere più facilmente i nodi foglia puri, vale a dire i punti dati in una singola classe. Tuttavia, man mano che un albero cresce di dimensioni, diventa sempre più difficile mantenere questa purezza, e capita spesso che quantità insufficiente di dati rientri in un determinato albero secondario. Quando ciò si verifica, si parla frammentazione dei dati, che può portare a un overfitting.

Di conseguenza, gli alberi decisionali migliori sono quelli più piccoli, il che è coerente con il principio della parsimonia o rasoio di Occam: "le entità non devono essere moltiplicate oltre più del necessario". In altre parole, gli alberi decisionali devono aggiungere complessità solo se necessario, poiché la spiegazione più semplice è spesso la migliore. Per ridurre la complessità e prevenire l'overfitting, di solito si utilizza il criterio di potatura (pruning), un processo che rimuove i rami che si dividono su caratteristiche di scarsa importanza. La stima del modello può quindi essere valutata attraverso il processo di convalida incrociata.

Un altro modo in cui gli alberi decisionali possono mantenere la loro precisione è formando un ensemble tramite un algoritmo di random forest: questo classificatore prevede risultati più accurati, in particolare quando i singoli alberi non sono correlati tra loro.

L'algoritmo di Hunt, sviluppato negli anni '60 per modellare l'apprendimento umano in psicologia, costituisce la base di molti algoritmi di albero decisionale popolari, tra i quali:

- ID3: lo sviluppo di ID3, abbreviazione di "Iterative Dichotomiser 3", viene accreditato a Ross Quinlan. Questo algoritmo sfrutta l'entropia e l'information gain come metriche per valutare le suddivisioni candidate. Alcune delle ricerche di Quinlan del 1986 su questo algoritmo sono disponibili qui.

- C4.5: questo algoritmo è considerato un'iterazione successiva di ID3, anch'esso sviluppato da Quinlan. Può utilizzare l'information gain o il gain ratio per valutare i punti di divisione all'interno degli alberi decisionali.

- CART: il termine CART è l'abbreviazione di "classification and regression trees" (alberi di classificazione e regressione) ed è stato introdotto da Leo Breiman. Questo algoritmo utilizza tipicamente l'indice di eterogeneità di Gini per identificare l'attributo ideale su cui effettuare la divisione. L'indice di Gini misura la frequenza con cui un attributo scelto a caso viene classificato in modo errato. Quando si valuta utilizzando questo indice, un valore più basso è più ideale.

Sebbene esistano diversi modi per selezionare l'attributo migliore in ogni nodo, ci sono due metodi che fungono da criterio di suddivisione popolare per i modelli di albero decisionale, ovvero l'information gain e l'indice di eterogeneità di Gini, che aiutano a valutare la qualità di ogni condizione di test e quanto sarà in grado di classificare i campioni in una classe.

Senza parlare di entropia, è difficile spiegare l'information gain. L'entropia è un concetto derivante dalla teoria dell'informazione che misura l'impurità dei valori del campione. È definita con dalla seguente formula, dove:

• S rappresenta il set di dati in cui viene calcolata l'entropia 
• c rappresenta le classi nel set S
• p(c) rappresenta la proporzione di punti dati che appartengono alla classe c rispetto al numero di punti dati totali nel set S

I valori di entropia possono essere compresi tra 0 e 1. Se tutti i campioni nel set di dati S appartengono a una classe, allora l'entropia sarà uguale a zero. Se la metà dei campioni è classificata in una classe e l'altra metà in un'altra, l'entropia sarà massima, cioè 1. Per selezionare la funzionalità migliore su cui suddividere e trovare l'albero decisionale ottimale, è necessario utilizzare l'attributo con meno entropia.

L'information gain rappresenta la differenza di entropia prima e dopo una divisione su un dato attributo. L'attributo con il maggiore information gain produrrà la migliore suddivisione in quanto sta ottenendo i migliori risultati nella classificazione dei dati di formazione in base alla classificazione target. L'acquisizione di informazioni è solitamente rappresentata con la seguente formula,

dove

• a rappresenta un attributo specifico o un'etichetta di classe
• Entropia(S) è l'entropia del dataset S
• |Sv|/|S| rappresenta la proporzione dei valori in S_v rispetto al numero di valori nel set di dati S.

Esaminiamo un esempio per consolidare questi concetti. Immaginiamo di avere il seguente set di dati arbitrario:

Per questo set di dati, l'entropia è 0,94, e può essere calcolata trovando la proporzione di giorni in cui "Gioca a tennis" è "Sì", ovvero 9/14, e la proporzione di giorni in cui "Gioca a tennis" è "No", cioè 5/14. Questi valori possono essere inseriti nella formula dell'entropia riportata in precedenza.

Entropia (Tennis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0,94

Possiamo quindi calcolare l'information gain per ciascuno degli attributi individualmente. Ad esempio, l'information gain per l'attributo "Umidità" è il seguente:

Gain (Tennis, Umidità) = (0,94)-(7/14)*(0,985) – (7/14)*(0,592) = 0,151

Riassumendo,

- 7/14 rappresenta la proporzione di valori in cui l'umidità equivale a "alta" rispetto al numero totale di valori di umidità. In questo caso, il numero di valori in cui l'umidità equivale a "alta" è uguale al numero di valori in cui l'umidità equivale a "normale".

- 0,985 è l'entropia quando Umidità = "alta"

- 0,59 è l'entropia quando Umidità = "normale"

Ripetere il calcolo per l'information gain per ogni attributo nella tabella precedente e selezionare l'attributo con l'information gain più elevato come primo punto di divisione nell'albero decisionale. In questo caso, Outlook produce il massimo information gain. Da lì, il processo viene ripetuto per ogni albero secondario.

L'indice di eterogeneità di Gini è la probabilità di classificare erroneamente un punto dati casuale nel set di dati se venisse etichettato in base alla distribuzione delle classi del set di dati. In modo simile all'entropia, se il set S è puro (cioè appartenente ad una classe) allora la sua impurità è zero. Questo è indicato dalla seguente formula:

Sebbene gli alberi decisionali possano essere utilizzati in molteplici di casi d'uso, altri algoritmi in genere li superano. Detto questo, gli alberi decisionali sono comunque utili per le attività di data mining e knowledge discovery. Di seguito approfondiremo i vantaggi e le sfide principali dell'utilizzo degli alberi decisionali:

• Facili da interpretare: la logica booleana e le rappresentazioni visive degli alberi decisionali ne semplificano la comprensione e il consumo. La natura gerarchica di un albero decisionale agevola inoltre la visualizzazione degli attributi più importanti, che non sempre sono altrettanto chiari con altri algoritmi, come le reti neurali.
  
  
• Poca o nessuna preparazione dei dati necessaria: gli alberi decisionali hanno una serie di caratteristiche che li rendono più flessibili rispetto ad altri classificatori. Possono gestire vari tipi di dati, ad esempio valori discreti o continui, e i valori continui possono essere convertiti in valori categorici mediante l'uso di soglie. Inoltre, possono gestire valori con valori mancanti, che per altri classificatori, come Naïve Bayes, risultano invece problematici.
  
  
• Più flessibili: gli alberi decisionali possono essere sfruttati sia per le attività di classificazione che di regressione, il che li rende più flessibili rispetto ad altri algoritmi. Sono anche insensibili alle relazioni sottostanti tra gli attributi. Ciò significa che, se due variabili sono altamente correlate, l'algoritmo sceglierà solo una delle caratteristiche su cui dividersi.

• Inclini all'overfitting: gli alberi decisionali complessi tendono a subire l'overfitting e non si generalizzano bene a nuovi dati. Questo scenario può essere evitato mediante processi di pre o post-pruning. Il pre-pruning interrompe la crescita degli alberi quando non ci sono dati sufficienti, mentre il post-pruning rimuove gli alberi secondari che contengono dati inadeguati dopo la costruzione.
  
  
• Stimatori ad alta varianza: anche le più piccole variazioni all'interno dei dati possono produrre un albero decisionale molto diverso. Il bagging, o media delle stime, può essere un metodo per ridurre la varianza degli alberi decisionali. Tuttavia, questo approccio presenta dei limiti perché può portare a predittori altamente correlati.
  
  
• Più costosi: dato che gli alberi decisionali adottano un approccio di ricerca approfondito durante la costruzione, possono essere più costosi da addestrare rispetto ad altri algoritmi.