Esercizio - Albero di decisione con criteri di impurità e potatura sul dataset iris

Testo (laboratorio LAB5). Sul dataset iris (150 fiori, 4 feature, 3 classi):

1. con l'indice di Gini trovare la prima divisione ottimale e costruire l'albero di profondità 3; calcolare l'accuracy sul training al variare della profondità;
2. confrontare i criteri Gini, entropia e guadagno d'informazione su una divisione stratificata $80\%/20\%$;
3. eseguire la potatura a costo-complessità: calcolare i $\alpha_{\text{eff}}$ dei nodi interni e l'effetto della potatura sull'accuracy;
4. (esercizio del laboratorio) scrivere EntropyCriterion e InformationGainCriterion.

Teoria usata: Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione → (Gini, entropia, soglie, costo-complessità); Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo → per i logaritmi dell'entropia; il confronto con la validazione in Overfitting, ridge regression e cross-validationUna buona prestazione sul training non basta: serve stimare quella su dati nuovi. La cross-validation (K-fold: $k$ parti, ciascuna a turno come test, errore medio; Monte Carlo: $k$ divisioni casuali con quota di test $q$; leave-one-out se $k=n$) evita di dipendere da una sola divisione casuale. L'errore atteso si scompone in $\text{bias}^2+\text{varianza}+\sigma^2$: i modelli semplici fanno underfitting (bias alto), quelli complessi overfitting (varianza alta). La regolarizzazione aggiunge alla perdita una penalità: la ridge regression minimizza $|y-X\beta|^2+\lambda\sum_{j\ge1}\beta_j^2$ e ha soluzione $\beta=(X^TX+\lambda\tilde I)^{-1}X^Ty$ (l'intercetta non si penalizza, le feature si standardizzano): riduce i coefficienti, rende l'inversa stabile con feature collineari, e $\lambda$ è un iperparametro scelto con la validazione (cross-validation annidata per non contaminare il test).Overfitting, ridge regression e cross-validation →.

1. Prima divisione

Per ogni feature e per ogni soglia $t$ (si provano tutti i valori osservati, con partizione $x\le t$ e $x>t$) si calcola il Gini ponderato $\frac{n_L}{n}\operatorname{Gini}_L+\frac{n_R}{n}\operatorname{Gini}_R$. Alla radice $\operatorname{Gini}=1-3\cdot(\frac13)^2=0{,}667$.

La migliore divisione è sulla lunghezza del petalo con soglia $1{,}9$ cm: a sinistra le $50$ setosa (Gini $0$), a destra $100$ campioni (50 versicolor, 50 virginica) con Gini $=1-0{,}5^2-0{,}5^2=0{,}5$. Gini ponderato $=\frac{50}{150}\cdot0+\frac{100}{150}\cdot0{,}5=0{,}333$ (riduzione $0{,}667-0{,}333=0{,}333$). La larghezza del petalo con soglia $0{,}8$ produce la stessa partizione (pareggio): la scelta dipende dall'ordine di scansione delle feature.

Albero di profondità 3 (con scikit-learn, stessa partizione): larghezza petalo $\le0{,}8$: setosa; altrimenti larghezza $\le1{,}75$ e poi lunghezza $\le4{,}95$ (foglia $[0,47,1]$ e foglia $[0,2,4]$), oppure larghezza $>1{,}75$ e lunghezza $\le4{,}85$ (foglie $[0,1,2]$ e $[0,0,43]$). Le foglie contengono (setosa, versicolor, virginica) e prevedono la classe di maggioranza: $[0,47,1]$ sbaglia $1$ campione, $[0,2,4]$ ne sbaglia $2$, $[0,1,2]$ ne sbaglia $1$, $[0,0,43]$ nessuno. Errori totali $1+2+1=4$ su 150: accuracy sul training $=\frac{146}{150}=0{,}973$.

Con profondità 1 si separa solo la setosa: a sinistra $50$ campioni tutti giusti, a destra $100$ campioni metà versicolor e metà virginica, di cui se ne indovinano $50$: $100/150=0{,}667$; con profondità 5 si arriva a $100\%$ sul training (overfitting probabile: l'accuracy sul training cresce sempre).

2. Confronto dei criteri

Con np.random.seed(0) e divisione stratificata (120 training e 30 test, 10 per classe): Gini, entropia e guadagno d'informazione danno gli stessi risultati: accuracy di training $0{,}967$ e di test $0{,}933$ per l'albero di profondità 3. Le tre misure di impurità sono quasi equivalenti e scelgono quasi sempre lo stesso attributo. Per per il guadagno d'informazione il criterio si massimizza ($IG=H(\text{nodo})-H_{\text{split}}$), per Gini ed entropia di split si minimizza: nel codice questo si gestisce con l'attributo OPTIMIZATION.

Entropia e guadagno nel codice.

class EntropyCriterion(Criterion):
    OPTIMIZATION = "minimize"
    @staticmethod
    def impurity(y):
        p = np.unique(y, return_counts=True)[1] / len(y)
        return -np.sum(p * np.log2(p + 1e-16))               # il termine 1e-16 evita log(0)
    @staticmethod
    def split_impurity(y_left, y_right):
        n = len(y_left) + len(y_right)
        return (len(y_left) * EntropyCriterion.impurity(y_left) + len(y_right) * EntropyCriterion.impurity(y_right)) / n
class InformationGainCriterion(Criterion):
    OPTIMIZATION = "maximize"
    # impurity = entropia; split_impurity = H(y_left U y_right) - entropia ponderata dei figli
    # is_tolerance_reached: improvement = split_impurity (il guadagno stesso), confrontato con min_improvement

3. Potatura a costo-complessità

Per ogni nodo interno $t$: $\alpha_{\text{eff}}(t)=\dfrac{R(t)-R(T_t)}{|T_t|-1}$, con $R(t)=\frac{n_t}{N}\operatorname{Gini}(t)$ e $R(T_t)$ la somma di $R$ sulle foglie del sottoalbero. Sull'albero di profondità 3 (5 foglie):

1. il nodo «larghezza $>1{,}75$» (46 campioni, $[0,1,45]$): $R(t)=\frac{46}{150}(1-(\frac1{46})^2-(\frac{45}{46})^2)=0{,}0130$; foglie $[0,1,2]$ e $[0,0,43]$ con $R=\frac3{150}\cdot\frac49+\frac{43}{150}\cdot0=0{,}0089$; $\alpha_{\text{eff}}=\frac{0{,}0130-0{,}0089}{2-1}=\mathbf{0{,}0042}$ (il più piccolo: si pota per primo);
2. il nodo «larghezza $\le1{,}75$» (54 campioni): $\alpha_{\text{eff}}=0{,}0297$;
3. il nodo «larghezza $>0{,}8$» (4 foglie): $0{,}0979$; la radice (5 foglie): $0{,}1567$.

Potare il nodo 1 lo trasforma in una foglia (46 campioni, classe virginica): le foglie diventano 4 e l'accuracy sul training resta $0{,}973$. Poi si ricalcolano gli $\alpha_{\text{eff}}$ sull'albero potato: ora il nodo «larghezza $\le1{,}75$» ha ancora $0{,}0297$ ed è il minimo: potandolo le foglie diventano 3 e l'accuracy scende a $0{,}960$; infine il nodo «larghezza $>0{,}8$», ormai con due foglie, ha $\alpha_{\text{eff}}=0{,}2598$ (potandolo restano $2$ foglie, accuracy $0{,}667$) e poi la radice ha $0{,}3333$ ($1$ foglia: accuracy $0{,}333$).

La potatura iniziale (fino a $\alpha\approx0{,}03$) toglie foglie quasi senza perdere accuracy: i rami eliminati distinguevano pochissimi campioni, tipicamente rumore. La scelta del livello di potatura si fa con un insieme di validazione, non sul training (dove l'accuracy non può che scendere). Nel notebook di laboratorio il nodo radice ha $\alpha_{\text{eff}}=0{,}1045$ e non $0{,}1567$ perché il loro albero divide anche il nodo puro delle setosa (7 foglie: $\frac{0{,}6667-0{,}0397}{7-1}=0{,}1045$); gli altri tre valori coincidono.

Codice

from sklearn.tree import DecisionTreeClassifier
for depth in range(1, 6):
    t = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(X, y); print(depth, t.score(X, y))
tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X, y)
print(tree.cost_complexity_pruning_path(X, y).ccp_alphas)     # [0, 0.0042, 0.0297, 0.2598, 0.3333]
pruned = DecisionTreeClassifier(max_depth=3, ccp_alpha=0.03, random_state=0).fit(X, y)   # 3 foglie