Proseguiamo la carrellata di classificatori e dopo aver analizzato le SVM, oggi ci concentriamo sui Decision Tree. Come sempre spenderemo prima alcune parole per capire quali sono i concetti chiave dietro questo modello, successivamente vedremo degli esempi basati sulla libreria scikit-learn.

I classificatori Decision tree possono essere visti come un modello che separa i dati prendendo delle decisioni basate su una serie di domande che vengono poste durante il processo decisionale.

Un esempio di ruotine quotidiana usata per decidere cosa fare può essere il seguente:

Basandosi sulle caratteristiche del nostro training set, il modello impara una serie di domande da porre per capire la classe del campione in oggetto. Sebbene l’esempio mostri un albero decisionale basato su variabili di categoria, la stessa tecnica può essere utilizzata anche con numeri reali.

Il metro di giudizio utilizzato per decidere quando dividere i dati è il valore del così detto Information Gain (IG).

Massimizzare l’Information Gain

Affinché si possa dividere il dataset in corrispondenza delle caratteristiche più informative, è necessario definire una funzione obiettivo da massimizzare con il nostro modello. In questo caso la nostra funzione è l’IG (Information Gain).

Matematicamente parlando, possiamo definire l’IG nel seguente modo:

IG(D_p,f) = I(D_p) - \sum_{j=1}^{m}\frac{N_j}{N_p}I(D_j)

Nella formula sopra riportata, f è la caratteristica su cui effettuare lo split, D_p e D_j sono rispettivamente il dataset del genitore e del j-esimo nodo figlio, I è la nostra misura dell’impurità, N_p è il numero totale di campioni al nodo genitore mentre N_j nel nodo j-esimo.

In pratica l’IG non è altro che la differenza tra l’impurità del nodo genitore e quella del nodo figlio: più è bassa l’impurità del nodo figlio, più è alta la IG.

Per ridurre la complessità, molte librerie, tra cui scikit, implementano degli alberi binari in cui ciascun nodo genitore è splittato al massimo in 2 nodi figli (left e right):

IG(D_p,f) = I(D_p) - \frac{N_{left}}{N_p}I(D_{left}) - \frac{N_{right}}{N_p}I(D_{right})

Criteri di Misura dell’Impurità

Per quanto riguarda la funzione I, i criteri maggiormente utilizzati sono:

• Entropy (I_H).
• Gini impurity (I_G).
• Classification error (I_E).

partiamo dall’entropy:

I_H(t) = -\sum_{i=1}^{c}p(i|t)log_2(p(i|t))

In questa equazione p(i|t) rappresenta la proporzione dei campioni che appartengono alla classe c per un particolare nodo t.

Ad esempio, in uno scenario di classe binaria, l’entropia è 0 se p(i=1|t) = 1 o p(i=0|t) = 0. Viceversa se le classi sono distribuite uniformemente, ovvero i 2 valori appena visti valgono 0.5, l’entropia è 1.

Similmente, la Gini impurity è così definita:

I_G(t) = 1 -\sum_{i=1}^{c}p(i|t)^2

Anche in questo caso si raggiunge il massimo valore quando le classi sono perfettamente mischiate tra loro.

Entrambi i criteri portano a risultati molto simili tra loro.

L’ultimo criterio che andiamo giusto a definire, il classification error, è così fatto:

I_E = 1 - max(p(i|t))

In linea generale possiamo dire che sia l’entropy che la Gini impurity tendono a comportarsi in maniera simile. Nel caso invece del classification error abbiamo un metro di misura che risulta essere poco sensibile ai cambiamenti nelle classi di probabilità dei nodi e quindi non è raccomandabile utilizzarlo per addestrare un albero.

Come Funziona l’Impurità

Per capire meglio il funzionamento di un Decision Tree Classifier, vale la pena soffermarsi su un esempio di calcolo dell’impurità; utilizzeremo la Gini Impurity.

Immaginiamo un dataset D_p composto al nodo genitore D_p da 80 campioni, 40 appartenenti alla classe 1 e 40 alla classe 2. Immaginiamo di avere davanti 2 possibilità di split rappresentati in figura:

Possiamo affermare che in questo scenario p(i | t) = 0.5 in quanto il nodo t = D_p ha una distribuzione uniforme di entrambe le classi i = 1, 2.

Detto ciò possiamo calcolare l’impurità del nodo genitore:

I_G(D_p) = 1 - p(1 | D_p)^2 - p(2 | D_p)^2 = 1 - \frac{40}{80}^2 - \frac{40}{80}^2 = 0.5

Proseguiamo quindi con il calcolare l’impurità dei 2 scenari, partiamo dal caso A:

I_G(D_{right}) = I_G(D_{left}) = 1 - p(1 | D_p)^2 - p(2 | D_p)^2 = 1 - \frac{30}{40}^2 - \frac{10}{40}^2 = 0.375

Passiamo ora al caso B:

I_G(D_{right}) =  1 - p(1 | D_p)^2 - p(2 | D_p)^2 = 1 - \frac{20}{20}^2 - 0^2 = 0

I_G(D_{left}) =  1 - p(1 | D_p)^2 - p(2 | D_p)^2 = 1 - \frac{20}{60}^2 - \frac{40}{60}^2 = 0.4

Adesso abbiamo tutti gli ingredienti per poterci calcolare l’IG dei vari scenari.

IG_A =  0.5 - \frac{40}{80} * 0.375 - \frac{40}{80} * 0.375 = 0.125

IG_B =  0.5 - \frac{60}{80} * 0.4 - 0 = 0.16

Appare chiaro come lo split B, essendo più puro dell’A, sia preferibile in quanto abbiamo un Information Gain superiore che ci garantisce una capacità discriminativa migliore.

Costruire un Decision Tree Classifier con SciKit

Un Decision Tree può creare alberi molto profondi e complessi con conseguente pericolo di overfitting.

Nel nostro esempio andiamo ad utilizzare scikit-learn per costruire un albero decisionale con una profondità massima di 4 elementi, useremo la Gini Impurity  come criterio di impurità.

Come siamo ormai abituati a fare, useremo il nostro classico dataset costruito nel primo articolo per classificare i nomi maschili e femminili italiani.

Per cominciare, creiamo il nostro script Python, scarichiamo il dataset da questo link, scompattiamolo e salviamo il file denominato dataset_names.txt nella stessa cartella dello script.

A questo punto, il codice da tenere di conto è il seguente:

Come puoi vedere lo script è molto semplice.

Dopo aver caricato il dataset e averlo diviso in un training e test set (riga 65) costruiamo l’istanza del Decision Tree Classifier impostando i parametri discussi sopra (riga 67) e procediamo subito all’addestramento.

Se esegui lo script utilizzando il dataset vedrai che lo score, stampato nella riga 70 e raggiunto utilizzando questa tecnica, è del 96.86%.

Le righe 72-74 infine permettono di testare il classificatore su nomi a scelta dell’utente.

Visualizzare il Decision Tree con GraphViz

Bene, abbiamo visto com’è facile con scikit-learn addestrare il nostro Decision Tree Classifier. Adesso possiamo spingerci ulteriormente avanti e visualizzare l’albero in forma grafica.

Scikit-learn permette di esportare i Decision Tree, una volta addestrati, in formato .dot visualizzabile poi con GraphViz un software crossplatform compatibile con Linux, Windows e macOS liberamente scaricabile da questo link.

Andiamo a modificare il codice Python del metodo main sopra riportato:

Nel codice, una volta fatto l’addestramento del nostro albero decisionale, generiamo il grafo con l’istruzione della riga 9. Tra i parametri passati alla funzione, abbiamo anche specificato il nome del file che dovrà essere generato: graph.dot.

Ottimo, se non hai ancora installato GraphViz è il momento farlo. Vai alla pagina di download e scarica la versione compatibile con il tuo OS.

A questo punto, vogliamo convertire il file appena generato in formato PNG.

Seguendo la documentazione ufficiale, apri una console nella cartella dove lo script Python ha generato il file graph.dot e lancia il seguente comando:

Il risultato sarà un’immagine come questa:

Come possiamo vedere, il Decision Tree Classifier ha compreso che l’informazione principale per classificare il campione in ingresso è controllare che il nome termini per a. In tal caso si effettuano una serie di controlli sul numero di consonanti, vocali e sulla lunghezza del nome. Viceversa, se il nome non termina per a, si controlla subito che il nome termini per o e poi si passa a fare una seconda serie di controlli.

Dai vari nodi visualizzati, è possibile anche vedere il valore dell’impurità, la classe di appartenenza del nodo e il numero di campioni contenuti.

In questo articolo abbiamo approfondito il funzionamento del Decision Tree Classifier, un modello che permette di definire un albero decisionale che divide il dataset in sottogruppi utilizzando le feature per discriminarli.

Una volta concluso il processo di addestramento, le soglie trovate vengono utilizzate per classificare qualsiasi campione in ingresso al modello. Tra le varie cose, abbiamo inoltre visto come è possibile creare delle immagini che mostrino gli alberi generati insieme ai parametri trovati dal classificatore.