Alberi di Decisione

Figura 4.4: Esempio di Decision Stump. $v$ è una caratteristica (feature) estratta dall'immagine e $\theta$ una soglia.

Un Albero di Decisione (Decision Tree) è un metodo molto semplice ed efficace per realizzare un classificatore e l'addestramento degli alberi di decisione è una delle tecniche attuali di maggior successo. Un albero di decisione è un albero di classificatori (Decision Stump) dove ogni nodo interno è associato ad una particolare “domanda” su una caratteristica (feature). Da questo nodo dipartono tanti archi quanti sono i possibili valori che la caratteristica può assumere, fino a raggiungere le foglie che indicano la categoria associata alla decisione. Particolare attenzione normalmente è posta per i nodi di decisione binaria.

Una buona “domanda” divide i campioni di classi eterogenee in dei sottoinsiemi con etichette abbastanza omogenee, stratificando i dati in modo da mettere poca varianza in ogni strato.

Figura 4.5: Esempio di Decision Tree.

Per permettere questo è necessario definire una metrica che misuri questa impurità. Definiamo $X$ come un sottoinsieme di campioni di un particolare insieme di addestramento formato da $m$ possibili classi. $X$ è di fatto una variabile aleatoria, che assume solo valori discreti (il caso continuo è comunque uguale). È possibile associare ad ogni valore discreto $x_i$, che può assumere $X$, la distribuzione di probabilità $p(x_i) = p_i$. $X$ è un data set formato da $m$ classi e $p_i$ è la frequenza relativa della classe $i$ all'interno dell'insieme $X$.

Figura 4.6: Confronto tra metriche di misura dell'impurità nel caso di problema di classificazione binario.

Data la definizione di $X$, negli alberi di decisione sono largamente usate le seguenti metriche:

Entropia

Dalla teoria dell'informazione, l'entropia $I_H$ di $X$ vale:

$$I_H(X)=-\sum_{i=1}^{m} p_i \log_2 p_i$$ (4.46)

Indice di Gini

L'indice di impurità di Gini è definito come

$$I_G(X) = 1 - \sum_{i=1}^m{p^2_i}$$ (4.47)

Errore di Classificazione

Dalla teoria bayesiana:

$$I_E(X) = 1 - \max_i{p_i}$$ (4.48)

Intuitivamente un nodo con distribuzione delle classi $(0,1)$ ha impurità minima, mentre un nodo con distribuzione uniforme $(0.5,0.5)$ ha impurità massima.

Una “domanda” $h_j(x)$, che ha $k$ possibili risposte, divide l'insieme $\mathcal{E}$ nei sottoinsiemi $\mathcal{E}_1, \ldots, \mathcal{E}_k$.

Per testare quanto bene la condizione viene eseguita, bisogna confrontare il grado di impurità dei nodi figli con l'impurità del nodo padre: maggiore è la loro differenza, migliore è la condizione scelta.

Data una metrica $I(\cdot)$ che misuri l'impurità, il guadagno $\Delta$ è un criterio che può essere usato per determinare la bontà della divisione:

$$\Delta = I(\mathcal{E}) - \sum_{i=1}^{k} \frac{ N(\mathcal{E}_i) } { N(\mathcal{E}) } I( \mathcal{E}_i)$$ (4.49)

dove $N(\mathcal{E})$ è il numero di campioni nel nodo padre e $N(\mathcal{E}_i)$ è il numero di campioni nel nodo figlio i-esimo.

Se viene usata come metrica l'entropia, il guadagno $\Delta$ è conosciuto come Information Gain (TSK06).

Gli alberi di decisione inducono algoritmi che scelgono una condizione di test che massimizza il guadagno $\Delta$. Siccome $I(\mathcal{E})$ è uguale per tutti i possibili classificatori e $N(\mathcal{E})$ è costante, massimizzare il guadagno è equivalente a minimizzare la somma pesata delle impurità dei nodi figli:

$$\hat{h} = \argmin_{h_j} \sum_{i=1}^{k} N(\mathcal{E}_i) I( \mathcal{E}_i)$$ (4.50)

La miglior domanda $h_j(x)$ è quella che minimizza tale quantità.

Nel caso di classificatori binari, la metrica di Gini è ampiamente utilizzata, in quando il guadagno da minimizzare si riduce a

$$\frac{p_1 n_1}{p_1 + n_1} + \frac{p_2 n_2}{p_2 + n_2}$$ (4.51)

con $p_1,n_1$ numero di campioni positivi e negativi che il classificatore sposta nel ramo sinistro e $p_2,n_2$ numero di campioni nel ramo destro.

Gli alberi di decisione si adattano sia molto bene che velocemente ai dati di addestramento e conseguentemente, se non limitati, soffrono in maniera sistematica del problema di overfitting. Normalmente agli alberi viene applicato un algoritmo di raffinamento (pruning) per ridurre, ove possibile, il problema di overfitting. Gli approcci di pruning sono solitamente due: pre-pruning o post-pruning. Il pre-pruning si limita a fermare la creazione dell'albero sotto determinate condizioni per evitare una eccessiva specializzazione (esempio massima dimensione dell'albero). Il post-pruning invece raffina un albero già creato, eliminando quei rami che non soddisfano alcune condizioni su un validation set precedentemente selezionato.

Questa tecnica di creazione di un albero di decisione viene solitamente indicata come Classification and regression trees (CART) (B$^+$84). Infatti, nel caso reale in cui le caratteristiche analizzate sono grandezze statistiche, non si parla di creare un albero di classificazione, ma più propriamente di costruire un albero di regressione. Trovare la partizione ottima dei dati è un problema NP-completo, perciò normalmente si fa uso di algoritmi ingordi greedy come quello mostrato in sezione.