Un albero decisionale è un algoritmo di apprendimento supervisionato non parametrico, utilizzato sia per attività di classificazione che di regressione. Si compone di una struttura ad albero gerarchica, che consiste di un nodo radice, di rami, nodi interni e nodi foglia.

Come è possibile riscontrare dal diagramma precedente, un albero decisionale inizia con un nodo radice, che non ha rami in entrata. I rami in uscita dal nodo radice alimentano i nodi interni, noti anche come nodi decisionali. Sulla base delle funzionalità disponibili, entrambi i tipi di nodo conducono valutazioni per formare sottoinsiemi omogenei, che sono rappresentati da nodi foglia o nodi terminali. I nodi foglia rappresentano tutti i possibili risultati all'interno del set di dati. Ad esempio, supponiamo che tu stia cercando di valutare se andare o meno a surfare, per prendere la tua decisione potrai utilizzare le seguenti regole decisionali:

Questo tipo di struttura del diagramma di flusso crea anche una rappresentazione facile da interpretare del processo decisionale, consentendo a diversi gruppi all'interno di un'organizzazione di comprendere meglio il motivo per cui è stata presa una decisione.

L'apprendimento dell'albero decisionale prevede l'utilizzo di una strategia "dividi et impera" applicata conducendo una ricerca per identificare i punti di divisione ottimali all'interno di un albero. Questo processo di suddivisione viene quindi ripetuto in modo ricorsivo dall'alto verso il basso fino a quando tutti o la maggior parte dei record sono stati classificati in etichette di classe specifiche. Il fatto che tutti i punti dati siano classificati o meno come insiemi omogenei dipende in gran parte dalla complessità dell'albero decisionale. Gli alberi più piccoli sono più facilmente in grado di raggiungere nodi foglia semplici, ad es. punti dati in una singola classe. Tuttavia, man mano che un albero cresce di dimensioni, diventa sempre più difficile mantenere questa semplicità che di solito si traduce in una quantità insufficiente dei dati all'interno di un determinato albero secondario. Questo fenomeno è noto come frammentazione dei dati e spesso può portare a un overfitting. Di conseguenza, gli alberi decisionali prediligono strutture piccole, il che è coerente con il principio di parsimonia del rasoio di Occam; ossia, "non moltiplicare gli elementi più del necessario". In altre parole, gli alberi decisionali dovrebbero aggiungere complessità solo se necessario, poiché la spiegazione più semplice è spesso la migliore. Per ridurre la complessità e prevenire l'overfitting, viene solitamente utilizzata la potatura; questo è un processo che rimuove i rami che si dividono in caratteristiche di bassa importanza. L'adattamento del modello può quindi essere valutato attraverso il processo di convalida incrociata. Un altro modo in cui gli alberi decisionali possono mantenere il proprio livello di accuratezza consiste nel formare un insieme tramite un algoritmo a forestale casuale; questa classificazione prevede risultati più precisi, in particolare quando le singole strutture non sono correlate tra loro.

Sebbene esistano diversi modi per selezionare l'attributo migliore in ciascun nodo, due metodi, guadagno di informazioni e impurità di Gini, rappresentano i criteri di divisione più popolari per i modelli di albero decisionale. Aiutano a valutare la qualità di ciascuna condizione di test e quanto questa sarà in grado di classificare i campioni in una classe.  

Entropia e Guadagno informazioni

È difficile spiegare il guadagno di informazioni senza prima trattare l'entropia. L'entropia è un concetto che deriva dalla teoria dell'informazione, che misura l'impurità dei valori di un campione. È definito con la 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 nell'insieme, S

I valori dell'entropia sono compresi tra 0 e 1. Se tutti i campioni nel set di dati, S, appartengono a una classe, l'entropia sarà uguale a zero. Se metà dei campioni è classificata in una classe e l'altra metà è in un'altra classe, l'entropia sarà al massimo a 1. Per selezionare la caratteristica migliore in base alla quale effettuare la divisione e trovare l'albero decisionale ottimale, è necessario utilizzare l'attributo con la quantità più piccola di entropia. Il guadagno di informazioni rappresenta la differenza di entropia precedente e successiva ad una divisione in base ad un determinato attributo. L'attributo con il maggior guadagno di informazioni produrrà la suddivisione migliore poiché starà ottenendo i migliori risultati di classificazione dei dati di addestramento in base alla propria classificazione di destinazione. Il guadagno di informazioni è solitamente rappresentato con la seguente formula, dove: 

• a rappresenta un attributo specifico o un'etichetta di classe
• Entropy(S) è l'entropia del set di dati, S
• |Sv|/ |S| rappresenta la proporzione dei valori in S_v per il numero di valori nel set di dati, S
• Entropy(S_v) è l'entropia del set di dati, S_v

Facciamo un esempio per consolidare questi concetti. Immagina di avere il seguente set di dati:

Per questo set di dati, l'entropia è 0,94. Questa può essere calcolata risalendo alla proporzione dei giorni in cui "Giocare a tennis" è "Sì", che è 9/14, e la proporzione dei giorni in cui "Giocare a tennis" è "No", che è 5/14. Quindi, questi valori possono essere inseriti nella formula dell'entropia di cui sopra.

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

Possiamo quindi calcolare le informazioni di guadagno per ciascuno dei singoli attributi. Ad esempio, il guadagno di informazioni per l'attributo "Umidità" sarebbe il seguente:

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

Riepilogando,

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

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

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

Quindi, ripetere il calcolo del guadagno di informazioni per ciascun attributo nella tabella precedente e selezionare l'attributo con il guadagno di informazioni più elevato come primo punto di divisione nell'albero decisionale. In questo caso, il risultato rappresenta il maggior guadagno di informazioni. Da qui, il processo viene ripetuto per ogni albero secondario. 

Impurità Gini 

L'impurità Gini rappresenta la probabilità di classificare in modo errato un punto dati casuale nel set di dati, se fosse etichettato in base alla distribuzione di classe del set di dati. Come per l'entropia, se impostata, S, è pura (cioè appartenente a una classe), quindi la sua impurità è zero. Ciò è evidenziato dalla seguente formula: 

Mentre gli alberi decisionali possono essere utilizzati in una varietà di casi d'uso, altri algoritmi in genere hanno prestazioni migliori rispetto agli algoritmi degli alberi decisionali. Ciò questo, gli alberi decisionali sono particolarmente utili per le attività di  data mining  e knowledge discovery. Di seguito esploriamo i principali vantaggi e le sfide derivanti dall'utilizzo degli alberi decisionali:

- Facile da interpretare: la logica booleana e le rappresentazioni visive degli alberi decisionali li rendono più facili da comprendere e utilizzare. La natura gerarchica di un albero decisionale rende anche facile vedere quali attributi sono più importanti, il che non è sempre chiaro con altri algoritmi quali le  reti neurali.

- Non è necessaria alcuna o solo una minima preparazione dei dati: gli alberi decisionali hanno una serie di caratteristiche che li rendono più flessibili rispetto ad altre classificazioni. Possono gestire vari tipi di dati, ad es. valori discreti o continui, e i valori continui possono essere convertiti in valori categoriali attraverso l'uso di soglie. Inoltre, possono anche gestire valori con valori mancanti, il che può essere problematico per altre classificazioni, come Naïve Bayes.  

- Più flessibili: gli alberi decisionali possono essere sfruttati sia per la classificazione che per le attività di regressione, rendendoli 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 ne sceglierà solo una in base alla quale effettuare la suddivisione. 

- Incline all'overfitting: Gli alberi decisionali complessi tendono all'overfitting e non si generalizzano bene con i nuovi dati. Questo scenario può essere evitato attraverso i processi di pre-potatura o post-potatura. La pre-potatura interrompe la crescita degli alberi quando ci sono dati insufficienti mentre la post-potatura, dopo la creazione dell'albero, rimuove gli alberi secondari contenenti dati inadeguati. 

- Stimatori di varianza elevata: piccole variazioni all'interno dei dati possono produrre un albero decisionale molto diverso. Bagging, o media delle stime, può essere un metodo per ridurre la varianza degli alberi di decisionali. Tuttavia, questo approccio è limitato in quanto può portare a predittori altamente correlati.  

- Più costoso: Dato che, durante la creazione, gli alberi decisionali adottano un approccio di ricerca avido possono essere più costosi da addestrare rispetto ad altri algoritmi. 

- Non completamente supportati in scikit-learn:  Scikit-learn è una popolare libreria di apprendimento automatico basata su Python. Sebbene questa libreria abbia un modulo di  Albero Decisionale (DecisionTreeClassifier, il collegamento risiede all'esterno di  ibm.com), l'implementazione corrente non supporta le variabili categoriali.