albero decisionale

Apprendimento ad albero decisionale

I classificatori ad albero decisionale sono modelli molto interessanti ed utili se quello che dobbiamo analizzare riguarda l’interoperabilità. Un argomento che racchiude un sacco di informazioni utili e necessarie per migliorare le nostre tecniche di addestramento e di creazione dei modelli.

Esso suddivide i dati prendendo decisioni sulla base delle risposte a una serie di domande precise:

albero decisionale

Capiamo dalla figura come il modello di addestramento impari una serie di domande per determinare, tramite inferenza, le etichette delle classi dei campioni. Ciò può essere applicato anche in caso le caratteristiche siano di tipo numerico come nel dataser Iris, dove potremmo impostare il valore di separazione per la caratteristica sepal width e porre la domanda binaria – sepal width > 2.8 cm ?

Partendo dalla radice suddividiamo i dati in base alla caratteristica che produce il massimo guadagno informativo (IG). Tutto ciò viene ripetuto per ciascun nodo figlio fino a raggiungere le foglie pure. Questo tipo di schema determina l’appartenenza alla stessa classe dei campioni presenti in ciascun nodo. Il tutto però può creare un albero di elevata grandezza generando così il fenomeno dell’overfitting che abbiamo trattato nelle lezioni precedenti.

Massimizzare il guadagno informativo in un albero decisionale

Per suddividere i nodi sulla base delle caratteristiche maggiormente informative andiamo a definire una funzione obbiettivo che vogliamo ottimizzare con l’algoritmo di apprendimento ad albero decisionale. La funzione tende a massimizzare il guadagno informativo a ogni suddivisione, definita nel suguente modo:

albero decisionale
  • f è la caratteristica su cui si basa la suddivisione
  • Dp e Dj sono dataset del genitore e del j-esimo nodo figlio
  • I misura l’impurità
  • Np numero totale campioni nel nodo genitore
  • Nj numero campioni nel nodo figlio j-esimo
Leggi articolo   Codifica one-hot e caratteristiche nominali

Il guadagno informativo è la differenza tra l’impurità del nodo genitore e la somma dell’impurità dei nodi figli, minore è l’impurità dei nodi figli e maggiore sarà il guadagno informativo. Per facilità strutturale e di implementazione scikit-learn utilizza alberi decisionali binari. Questa implica la dipendenza di due nodi figli, dx e sx, da un nodo genitore.

albero decisionale

Le tre misure di impurità o criteri di suddivisione che vengono comunemente utilizzati negli alberi decisionali binari sono:

    • impurità di Gini (Ig)
    • entropia (Ih)
    • errore di classificazione (Ie)

Entropia

Definiamo l’entropia per tutte le classi non vuote con p(i|t) diverse da 0:

albero decisionale

P(i|t) è la proporzione dei campioni che appartengono alla classe c per un determinato nodo t. Pertanto l’entropia è 0 se tutti i campioni di un nodo appartengono alla stessa classe ed è massima se abbiamo una distribuzione uniforme nelle classi. Possiamo affermare così che il criterio di entropia cerca di massimizzare l’informazione reciproca all’interno dell’albero.

L'impurità di Gini

Essa può essere considerata come un criterio per minimizzare la probabilità di un’errata classificazione.

albero decisionale

Come l’entropia, l’impurità di Gini è massima se le classi sono perfettamente mescolate, per esempio, in una classe binaria ( c = 2 )

Errore di classificazione

L’errore di classificazione è un’altra misura di impurità:

Criterio utile alla potatura ma non consigliabile per far crescere un albero decisionale in quanto è meno sensibile ai cambiamenti nelle probabilità che i nodi appartengano a determinate classi.

albero decisionale

Graficamente ...

Per un confronto più intuitivo del funzionamento dei tre diversi criteri di impurità di cui abbiamo parlato, tracciamo gli indici di impurità per la gamma di probabilità [0,1] per la classe 1. Aggiungeremo anche una versione in scala dell’entropia (entropia/2) per osservare che l’impurità di Gini è una misura intermedia tra l’entropia e l’errore di classificazione.

Leggi articolo   KNN - Algoritmo di Supervisione
				
					import matplotlib.pyplot as plt
import numpy as np


def gini(p):
    return p * (1 - p) + (1 - p) * (1 - (1 - p))


def entropy(p):
    return - p * np.log2(p) - (1 - p) * np.log2((1 - p))


def error(p):
    return 1 - np.max([p, 1 - p])

x = np.arange(0.0, 1.0, 0.01)

ent = [entropy(p) if p != 0 else None for p in x]
sc_ent = [e * 0.5 if e else None for e in ent]
err = [error(i) for i in x]

fig = plt.figure()
ax = plt.subplot(111)
for i, lab, ls, c, in zip([ent, sc_ent, gini(x), err], 
                          ['Entropia', 'Entropia in scala', 
                           'Gini Impurità', 'Errore classificazione'],
                          ['-', '-', '--', '-.'],
                          ['black', 'lightgray', 'red', 'green', 'cyan']):
    line = ax.plot(x, i, label=lab, linestyle=ls, lw=2, color=c)

ax.legend(loc='upper center', bbox_to_anchor=(0.5, 1.15),
          ncol=3, fancybox=True, shadow=False)

ax.axhline(y=0.5, linewidth=1, color='k', linestyle='--')
ax.axhline(y=1.0, linewidth=1, color='k', linestyle='--')
plt.ylim([0, 1.1])
plt.xlabel('p(i=1)')
plt.ylabel('Impurity Index')
plt.tight_layout()
plt.show()
				
			

Condividi il post

Condividi su facebook
Condividi su google
Condividi su twitter
Condividi su email
Condividi su whatsapp