Classificazione dell'albero decisionale

Introduzione

Gli alberi decisionali (DT) sono un metodo di apprendimento supervisionato non parametrico utilizzato per la classificazione e la regressione. L'obiettivo è creare un modello che preveda il valore di una variabile target apprendendo semplici regole decisionali dedotte dalle caratteristiche dei dati.

Entropia

L'obiettivo della formazione è trovare le migliori suddivisioni nei nodi per trovare l'albero più ottimale. Le suddivisioni vengono effettuate utilizzando alcuni criteri come: Entropia.

Esistono molte definizioni di entropia come:

L'entropia corrisponde alla quantità di informazioni contenute in una fonte di informazione.
L'entropia può anche essere vista come la casualità o la misurazione della sorpresa in un insieme.
L'entropia è una metrica che misura l'imprevedibilità o l'impurità nel sistema.

Negli alberi decisionali considereremo l'entropia come la misura della purezza all'interno di un nodo. L'obiettivo del modello dell'albero decisionale è ridurre l'entropia dei nodi ad ogni divisione:

Pertanto, vogliamo massimizzare la differenza tra l'entropia del nodo genitore e l'entropia dei nodi figli. Questa differenza è chiamata guadagno di informazioni.

L'Entropia $H$ di un insieme $X$ è matematicamente formulata come segue:

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Guadagno di informazioni

Il guadagno di informazioni è la differenza tra l'entropia del nodo genitore e la somma ponderata delle entropie dei nodi figli, e quindi può essere formulato come segue:

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

Dove:

$H(.)$ è l'entropia.
$Y$ è la popolazione prima della divisione, rappresenta il nodo genitore.
$X$ è la variabile che vogliamo utilizzare per la suddivisione.
$x$ è un valore univoco di X.
$Y[X==x]$ è una lista divisa con solo valori $x$ .

facciamo un esempio corretto:

Calcoleremo il guadagno di informazioni quando dividiamo il nodo genitore utilizzando i valori di X:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Innanzitutto, calcoliamo l'entropia del nodo genitore:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

Quindi, calcoleremo la probabilità interna di ciascun nodo figlio dopo la divisione utilizzando i valori univoci di X:

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Ad esempio:

$H(Y | X = Square)$ : rappresenta l'entropia del primo nodo figlio.
$H(Y | X = Circle)$ : rappresenta l'entropia del secondo nodo figlio.

Iniziamo con il primo nodo figlio:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

E poi il secondo nodo figlio:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

Infine, sostituiamo le entropie nella formula del guadagno di informazioni:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

Come affermato in precedenza, l'obiettivo della suddivisione di un nodo è massimizzare il guadagno di informazioni e quindi ridurre al minimo l'entropia nel nodo figlio risultante. Per fare ciò, dobbiamo provare a dividere il nodo con diversi set di input $X_1, X_2, \ldots, Xn$ e manteniamo solo la divisione che massimizza il guadagno di informazioni:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Quando smettere di dividere

La suddivisione dei nodi negli alberi decisionali è ricorsiva, quindi deve esserci un criterio che possiamo utilizzare per interrompere la suddivisione. Questi alcuni dei criteri più implementati:

Quando il nodo è puro: H(nodo) = 0. È inutile dividere ulteriormente il nodo.
Numero massimo di profondità: Possiamo impostare una profondità massima che il modello può raggiungere, significa che anche se il nodo non è puro la scissione viene interrotta.
Numero minimo di campioni per nodo: Possiamo anche impostare un numero minimo $N$ di campioni per nodo. Se il numero di campioni per nodo è pari a $N$ allora interrompiamo la suddivisione anche se il nodo non è puro.

Alla fine dell'addestramento (la suddivisione), ogni nodo che si basa sulla fine dell'albero decisionale viene chiamato "Foglia", perché non è la radice di nessun sottoalbero. Ogni foglia rappresenterà la classe con il maggior numero di campioni.

Conclusione

L'albero decisionale è uno degli algoritmi di machine learning più famosi grazie alla sua efficienza, al suo background intuitivo e alla sua semplice implementazione. Questo algoritmo può essere ulteriormente utilizzato con variabili numeriche indipendenti (albero decisionale gaussiano) e può essere esteso anche per risolvere compiti di regressione.