Classificazione dell'albero decisionale

Aggiornato su September 24, 2024 4 minuti a leggere

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.