Alberi di decisione

Gli alberi sono tra i metodi più efficaci per l'apprendimento supervisionato su dati tabellari di dimensione medio-piccola (meno di circa 10 000 campioni), e le idee alla base sono semplici (Lezione 16 · Alberi di decisione e random forest). Qui si costruisce l'albero singolo; la combinazione di molti alberi (foreste, boosting) è in Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →. Gli esercizi sono Esercizio - Albero di decisione ID3 sul dataset del tennis, Esercizio - Albero di decisione con criteri di impurità e potatura sul dataset iris e Esercizio - ID3 con potatura e foresta casuale sul dataset Titanic (Lezione 18 · Laboratorio sui metodi ad albero).

L'idea: decisioni a una variabile alla volta

Un esempio di decisione medica: «età > 50? peso > 90 kg? fumatore?» da cui si stima il rischio di infarto. Il diagramma è probabilmente stato costruito da dati storici: è un problema supervisionato multivariato di classificazione, ma ogni decisione guarda una sola variabile per volta.

Definizione (albero di decisione). Struttura ad albero in cui

• ogni nodo interno rappresenta una regola basata su una feature (per esempio «umidità = alta» oppure «$x_3\le1{,}9$»);
• ogni ramo è l'esito della regola;
• ogni foglia è una predizione: tipicamente la classe più frequente tra i campioni che arrivano in quella foglia (in regressione, la media dei loro valori).

Per classificare un nuovo punto si parte dalla radice e si segue il ramo indicato dal valore delle sue feature, fino a una foglia.

L'obiettivo dell'addestramento è trovare le decisioni (coppie variabile-valore, o variabile-soglia) che dividono i dati in scenari in cui una classe diventa dominante o più facile da prevedere. Si procede in modo ricorsivo:

1. si parte dalla radice con tutti i dati;
2. si sceglie la variabile (e il valore) che «semplifica» di più il problema, cioè che rende più omogenee le classi nei figli;
3. si divide e si ripete su ciascun figlio, finché le classi sono separate o si raggiunge una profondità massima.

Serve una misura quantitativa di quanto sia «semplice» un nodo: le misure di impurità.

Entropia e guadagno d'informazione

Definizione (entropia). (Logaritmo in base 2: 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 un insieme $S$ di campioni con $c$ classi, di proporzioni $p_1,\dots,p_c$, $$H(S)=-\sum_{i=1}^cp_i\log_2p_i\qquad(\text{con }0\log_20=0).$$ $H=0$: l'insieme è puro (una sola classe); $H$ più alta: classi più mescolate, maggiore incertezza. Con due classi il massimo è $1$ per $p=\tfrac12$.

Definizione (guadagno d'informazione). Dividere $S$ secondo i valori $v$ dell'attributo $A$ in sottoinsiemi $S_v$ riduce l'entropia di $$IG(S,A)=H(S)-\sum_{v\in\text{Valori}(A)}\frac{|S_v|}{|S|}\,H(S_v).$$ $IG$ alto: la divisione riduce molto l'incertezza (buona scelta); $IG$ basso: l'attributo non aiuta a separare le classi.

Il secondo termine è la media delle entropie dei figli pesata dalla frazione di campioni di ciascun figlio.

Esempio (dataset del tennis, Mitchell 1997). Dati di 14 giorni per prevedere se l'amico gioca a tennis:

(Le slide indicano $n=15$ ma le righe sono 14.) Ci sono $9$ «Yes» e $5$ «No»: $H(S)=-\tfrac9{14}\log_2\tfrac9{14}-\tfrac5{14}\log_2\tfrac5{14}=0{,}643\cdot0{,}637+0{,}357\cdot1{,}485=0{,}410+0{,}530=0{,}940$.

Passo 1: scelta della radice. Per ogni attributo si calcola l'entropia di ciascun sottoinsieme.

• Outlook: Sunny (5: 2 Yes, 3 No) $H=0{,}971$; Overcast (4: 4 Yes) $H=0$; Rain (5: 3 Yes, 2 No) $H=0{,}971$. $IG=0{,}940-\big(\tfrac5{14}0{,}971+\tfrac4{14}0+\tfrac5{14}0{,}971\big)=0{,}940-0{,}693=\mathbf{0{,}247}$.
• Temperature: Hot (4: 2/2) $H=1$; Mild (6: 4/2) $H=0{,}918$; Cool (4: 3/1) $H=0{,}811$. $IG=0{,}940-(\tfrac4{14}1+\tfrac6{14}0{,}918+\tfrac4{14}0{,}811)=0{,}940-0{,}911=0{,}029$.
• Humidity: High (7: 3 Yes, 4 No) $H=0{,}985$; Normal (7: 6/1) $H=0{,}592$. $IG=0{,}940-(0{,}5\cdot0{,}985+0{,}5\cdot0{,}592)=0{,}940-0{,}788=0{,}152$.
• Wind: Weak (8: 6/2) $H=0{,}811$; Strong (6: 3/3) $H=1$. $IG=0{,}940-(\tfrac8{14}0{,}811+\tfrac6{14}1)=0{,}940-0{,}892=0{,}048$.

Il guadagno massimo è quello di Outlook ($0{,}247$): è la radice. Il ramo Overcast è già puro (sempre Yes): foglia «Yes».

Passo 2: rami Sunny e Rain.

• Sunny (5 campioni: 2 Yes, 3 No, $H=0{,}971$): lo split su Humidity dà High $\to$ 3 No ($H=0$) e Normal $\to$ 2 Yes ($H=0$): $IG=0{,}971$, il massimo possibile (Temperature darebbe $0{,}571$, Wind $0{,}020$).
• Rain (5 campioni: 3 Yes, 2 No): lo split su Wind dà Weak $\to$ 3 Yes e Strong $\to$ 2 No: $IG=0{,}971$.

Outlook?
├── Sunny    -> Humidity?
│               ├── High   -> No
│               └── Normal -> Yes
├── Overcast -> Yes
└── Rain     -> Wind?
                ├── Weak   -> Yes
                └── Strong -> No

L'albero classifica correttamente tutti i 14 campioni di training. Le regole sono immediatamente leggibili («se è soleggiato e l'umidità è normale, gioca»).

L'indice di Gini e l'algoritmo CART

Definizione (indice di Gini o impurità di Gini). $\displaystyle\operatorname{Gini}(S)=1-\sum_{i=1}^cp_i^2.$ Vale $0$ per un insieme puro, e il massimo $1-\tfrac1c$ per classi equiprobabili. Per una divisione in sinistra/destra: $$\operatorname{Gini}_{\text{split}}=\frac{n_{\text{sx}}}{n}\operatorname{Gini}(\text{sx})+\frac{n_{\text{dx}}}{n}\operatorname{Gini}(\text{dx}).$$ Si sceglie la divisione con $\operatorname{Gini}_{\text{split}}$ minimo (cioè con la massima riduzione di impurità).

Esempio. Sul tennis, $\operatorname{Gini}(S)=1-(\tfrac9{14})^2-(\tfrac5{14})^2=1-0{,}413-0{,}128=0{,}459$. Split su Outlook: Sunny $1-(0{,}4)^2-(0{,}6)^2=0{,}48$, Overcast $0$, Rain $0{,}48$, quindi $\operatorname{Gini}_{\text{split}}=\tfrac5{14}0{,}48+0+\tfrac5{14}0{,}48=0{,}343$ (riduzione $0{,}116$); Humidity: $0{,}367$; Wind: $0{,}429$; Temperature: $0{,}440$. Anche con Gini la scelta migliore è Outlook.

Le due curve sono molto simili, come quella dell'errore di classificazione $1-\max_ip_i$ (per due classi, in funzione di $p$):

(Il Gini ha massimo $0{,}5$ per due classi.)

CART (Classification And Regression Trees) costruisce alberi binari con un algoritmo ricorsivo:

CART(dati):
    se tutti gli esempi hanno la stessa classe  ->  foglia con quella classe
    miglior_divisione = attributo e valore con il Gini_split minimo
    se nessuna divisione migliora il Gini        ->  foglia con la classe maggioritaria
    sx, dx = dividi i dati con la miglior_divisione
    nodo con: la condizione, CART(sx), CART(dx)

Variabili numeriche

Per una feature numerica (per esempio la lunghezza del petalo) CART considera divisioni binarie $x\le t$ e prova molte soglie $t$ (di solito i punti medi tra valori consecutivi dei dati ordinati), scegliendo quella che minimizza l'impurità. Per le variabili categoriche si divide in «uguale a un valore» / «diverso».

Esempio. $x=[1,2,3,4,5,6]$ con etichette $[A,A,B,A,B,B]$. Per le soglie $t=1{,}5;\ 2{,}5;\ 3{,}5;\ 4{,}5;\ 5{,}5$ il Gini ponderato vale $0{,}400;\ 0{,}250;\ 0{,}444;\ 0{,}250;\ 0{,}400$. Per $t=2{,}5$: sinistra $\{A,A\}$ (Gini $0$), destra $\{B,A,B,B\}$ (Gini $1-(0{,}25)^2-(0{,}75)^2=0{,}375$): $\tfrac26\cdot0+\tfrac46\cdot0{,}375=0{,}25$. Le soglie $2{,}5$ e $4{,}5$ sono alla pari (ex aequo): si sceglie la prima trovata.

Esempio (dataset iris con CART, profondità 3). Radice: petalo $\le0{,}8$ cm (o, equivalentemente, lunghezza del petalo $\le1{,}9$) isola le 50 setosa. Poi larghezza $\le1{,}75$ e lunghezza $\le4{,}95$ o $\le4{,}85$. Accuracy sul training $0{,}973$ con profondità 3 ($0{,}667$ con profondità 1, $0{,}960$ con 2, $0{,}993$ con 4, $1{,}0$ con 5).

Alberi di regressione

Con un target continuo cambiano il criterio di divisione e l'uscita delle foglie.

Formula (criteri per la regressione). Per una divisione in sinistra/destra con $n_L,n_R$ campioni ($n=n_L+n_R$): $$\mathrm{MSE}_{\text{split}}=\frac{n_L}{n}\mathrm{MSE}_L+\frac{n_R}{n}\mathrm{MSE}_R,\qquad\text{riduzione di varianza}=\operatorname{Var}(\text{genitore})-\Big(\frac{n_L}{n}\operatorname{Var}_L+\frac{n_R}{n}\operatorname{Var}_R\Big),$$ con $\operatorname{Var}(y)=\frac1n\sum(y_i-\bar y)^2$ (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →). Poiché in ogni nodo la previsione è la media (e quindi l'MSE del nodo è la sua varianza), massimizzare la riduzione di varianza equivale a minimizzare l'MSE. Ogni foglia restituisce la media del target dei suoi campioni.

Esempio. $x=[1,2,3,4,5,6]$, $y=[1,2,3,10,11,12]$: varianza del genitore $20{,}92$. Per $t=2{,}5$: sinistra $[1,2]$ (varianza $0{,}25$), destra $[3,10,11,12]$ (media $9$, varianza $\tfrac{36+1+4+9}4=12{,}5$): MSE ponderato $\tfrac26\cdot0{,}25+\tfrac46\cdot12{,}5=0{,}083+8{,}333=8{,}42$. Ripetendo per tutte le soglie si ottiene $14{,}87;\ 8{,}42;\ \mathbf{0{,}67};\ 8{,}42;\ 14{,}87$ per $t=1{,}5;\ 2{,}5;\ 3{,}5;\ 4{,}5;\ 5{,}5$: la migliore è $t=3{,}5$ (sinistra $[1,2,3]$ con media $2$ e varianza $\tfrac23$; destra $[10,11,12]$ con media $11$ e varianza $\tfrac23$), con riduzione di varianza $20{,}92-0{,}67=20{,}25$. Le predizioni sono $2$ per $x\le3{,}5$ e $11$ per $x>3{,}5$: una funzione costante a tratti.

ID3 e altre varianti

ID3 (Iterative Dichotomiser 3) è l'algoritmo originale per feature categoriche, alternativo a CART:

• a ogni nodo si calcola l'entropia di split (o il guadagno) per ogni feature non ancora usata nel ramo e si sceglie la migliore;
• si divide in tutti i valori della feature, creando tanti figli quanti sono i valori (anche più di due, o uno solo);
• una feature usata non è riutilizzata nei discendenti;
• si fermano la crescita (foglia): nessun campione nel nodo $\to$ si predice la classe maggioritaria del genitore; tutti i campioni della stessa classe $\to$ quella classe; nessuna feature rimasta con classi miste $\to$ classe maggioritaria (e, opzionale, profondità massima).

Per le feature continue si può: usare la soglia binaria come in CART (scegliere la miglior $x\le t$), oppure quantizzare le variabili in intervalli e trattarle come categoriche (pre-elaborazione), oppure fare uno split multiplo con i punti medi tra valori consecutivi. Nelle prove di laboratorio sul Titanic la soglia ($0{,}825$ di accuracy su test) e la quantizzazione ($0{,}790$) sono confrontabili.

Overfitting e potatura

Un albero lasciato crescere fino a foglie pure separa perfettamente il training ma si adatta al rumore: varianza alta (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →), scarsa generalizzazione (lo stesso fenomeno di 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 →). Al crescere della profondità l'accuracy sul training sale sempre (nell'iris da $0{,}667$ a $1{,}0$); su dati nuovi sale e poi scende. Due rimedi:

Pre-potatura (profondità massima). Si ferma la crescita a una profondità $d_{\max}$ anche se altre divisioni migliorerebbero l'adattamento (early stopping). Pro: veloce e facile da controllare; evita l'overfitting con pochi dati. Contro: può perdere divisioni utili subito oltre il limite e non guarda quanto siano significative. Nel laboratorio sul dataset wine l'accuracy su test passa da $0{,}730$ (profondità 1) a $0{,}946$ (2) e $0{,}973$ (3).

Post-potatura a costo-complessità (minimal cost-complexity pruning, di CART). Si lascia crescere l'albero completo e poi si tolgono i rami che non migliorano la generalizzazione. Si cercano i sottoalberi che bilanciano l'errore e la semplicità: $$R_\alpha(T)=R(T)+\alpha\,|T|,$$ con $R(T)$ l'errore (impurità di Gini o tasso di errata classificazione) dell'albero $T$, $|T|$ il numero di foglie e $\alpha\ge0$ il parametro di potatura (più alto = più potatura). Per ogni nodo interno $t$ si calcola il $\alpha$ al quale conviene sostituire il suo sottoalbero $T_t$ con una foglia: $$\alpha_{\text{eff}}(t)=\frac{R(t)-R(T_t)}{|T_t|-1},\qquad R(t)=\frac{n_t}{N}\,\operatorname{Gini}(t),\quad R(T_t)=\sum_{\text{foglie di }T_t}R(\ell).$$ Il numeratore è la riduzione di errore che quel sottoalbero apporta, il denominatore il numero di foglie «aggiunte». Si pota per primo il nodo con $\alpha_{\text{eff}}$ minimo (il «filo più debole»: aggiunge poco per foglia), si ricalcolano gli $\alpha_{\text{eff}}$ e si ripete; ciò dà una successione di alberi sempre più piccoli, tra cui si sceglie con una validazione. Pro: flessibile, di solito generalizza meglio del limite rigido; contro: più lenta (valuta sottoalberi) e richiede un'accurata scelta di $\alpha$.

Esempio (iris, albero di profondità 3, 150 campioni). I quattro nodi interni sono: (a) il nodo «larghezza $>1{,}75$» (46 campioni: 1 versicolor e 45 virginica) con due foglie $[0,1,2]$ e $[0,0,43]$: $R(t)=\tfrac{46}{150}\,\operatorname{Gini}=0{,}0130$, $R(T_t)=0{,}0089$, 2 foglie $\Rightarrow\alpha_{\text{eff}}=(0{,}0130-0{,}0089)/(2-1)=0{,}0042$; (b) il nodo «larghezza $\le1{,}75$» (54 campioni) con le foglie $[0,47,1]$ e $[0,2,4]$: $0{,}0297$; (c) il nodo «larghezza $>0{,}8$» (100 campioni, 4 foglie): $0{,}0979$; (d) la radice (5 foglie): $0{,}1567$. Si pota per primo il nodo (a), con $\alpha_{\text{eff}}$ minimo ($0{,}0042$), poi si ricalcolano gli altri. (Nel notebook di laboratorio i valori $0{,}0042$, $0{,}0297$, $0{,}0979$ sono gli stessi; per la radice compare $0{,}1045$ perché il loro albero divide anche il nodo puro delle setosa e ha 7 foglie: $(0{,}6667-0{,}0397)/(7-1)=0{,}1045$.)

Vantaggi e svantaggi

• Pro: facilmente interpretabili (regole leggibili); non richiedono normalizzazione dei dati (le soglie su una variabile non dipendono dalla scala); classificazione quasi immediata; la parte costosa (l'addestramento) si fa una volta, offline; trattano classi multiple e variabili miste.
• Contro: sono classificatori ad alta varianza: piccole modifiche nei dati cambiano molto l'albero, quindi sono soggetti a overfitting e spesso generalizzano male.

La soluzione è considerare molti alberi diversi e combinarli: una foresta (Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →). L'importanza delle feature, calcolata dalla riduzione di impurità, è trattata anch'essa lì.

Codice

from sklearn.tree import DecisionTreeClassifier, export_text
tree = DecisionTreeClassifier(criterion="gini", max_depth=3, ccp_alpha=0.0, random_state=0)
tree.fit(X_train, y_train)
print(export_text(tree, feature_names=names))      # regole dell'albero
alphas = tree.cost_complexity_pruning_path(X_train, y_train).ccp_alphas   # alpha di potatura

L'implementazione da zero nei laboratori usa classi con impurity() e split_impurity() e un nodo con (feature, soglia, predizione); nodi indicizzati come $2i+1$ e $2i+2$. Nota: nel codice del laboratorio il criterio «minimizza» (Gini, entropia) o «massimizza» (guadagno d'informazione).

Errori tipici

• Dimenticare che il guadagno d'informazione si massimizza mentre Gini e entropia dei figli si minimizzano.
• Calcolare la media delle entropie dei figli senza pesare per la dimensione dei sottoinsiemi.
• Scegliere la profondità guardando l'accuracy sul training (sale sempre).
• Pensare che serva standardizzare le feature: per gli alberi non serve.
• Usare un albero molto profondo sperando in una buona generalizzazione: varianza alta.