06 - Decision Trees e Random Forest

Un albero decisionale è una sequenza di domande sì/no sulle misure («il nodulo ha raggio maggiore di 14?») che termina in una previsione, ed è l'unico modello di questa serie che puoi stampare e far leggere a una persona che non sa di statistica. Ha però due difetti che spiegano tutto il resto: lasciato crescere impara a memoria il training, e basta cambiare qualche esempio perché l'albero cambi aspetto. Il rimedio per il secondo, mediare molti alberi diversi, è la foresta casuale (random forest). Questo articolo costruisce un albero con un calcolo a mano e lo confronta con scikit-learn, mostra con una misura dove sovradatta e come si pota, spiega perché una foresta funziona con esperimenti sul numero di alberi e sulla scelta delle feature, e avverte sui limiti dell'importanza delle feature. Servono i capitoli 04 (bias e varianza, dove il bagging è già comparso) e 05 (validazione incrociata).

Gli esempi usano scikit-learn 1.9.0 e numpy 2.4.6, con il dataset Breast Cancer (569 esempi, 30 misure) e con dati sintetici a seme fisso; le uscite sono identiche in due esecuzioni.

Come cresce un albero

L'algoritmo è greedy (avido): parte da un nodo con tutti gli esempi, cerca la domanda «misura ≤ soglia» che separa meglio le classi, divide in due figli e ripete in ciascuno. Il manuale di James, Witten, Hastie e Tibshirani (An Introduction to Statistical Learning) lo chiama recursive binary splitting (paragrafo 8.1.1) e lo applica ai problemi di classificazione nel paragrafo 8.1.2. «Meglio» si misura con l'impurità di un nodo: tanto più bassa, quanto più il nodo contiene una sola classe. Con p_k la frazione di esempi della classe k nel nodo, l'indice di Gini è 1 − Σ p_k² e l'entropia è −Σ p_k log₂ p_k (in bit). Per due classi, un nodo 50/50 ha Gini 0,5 ed entropia 1; un nodo puro ha entrambe a 0. Il manuale osserva che i due indici sono numericamente molto simili. Una divisione si valuta con la media pesata delle impurità dei figli, e si sceglie la soglia che la minimizza.

Esercizio svolto: la migliore soglia di una sola feature

Dieci esempi con una misura x da 1 a 10, etichette 0,0,0,1,0,1,1,1,1,0 (cinque per classe). Per ogni soglia a metà fra due valori consecutivi si dividono gli esempi, si calcola il Gini dei due figli e se ne fa la media pesata; poi si confronta il risultato con quello di DecisionTreeClassifier(max_depth=1). A mano: per la soglia 3,5 il figlio sinistro (x = 1, 2, 3) è puro, con Gini 0; il destro ha 7 esempi, 5 della classe 1 e 2 della classe 0, quindi Gini 1 − (5/7)² − (2/7)² = 0,4082; la media pesata è (3·0 + 7·0,4082)/10 = 0,2857.

import numpy as np
from sklearn.tree import DecisionTreeClassifier

x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], dtype=float)
y = np.array([0, 0, 0, 1, 0, 1, 1, 1, 1, 0])           # 5 e 5; una sola feature

def gini(y):
    p = np.bincount(y, minlength=2) / len(y)
    return 1 - np.sum(p ** 2)

def entropia(y):
    p = np.bincount(y, minlength=2) / len(y)
    p = p[p > 0]
    return -np.sum(p * np.log2(p))

print("impurita' della radice: Gini =", round(gini(y), 4), " entropia =", round(entropia(y), 4))
migliore = None
for t in (x[:-1] + x[1:]) / 2:                          # soglie a meta' fra valori consecutivi
    sx, dx = y[x <= t], y[x > t]
    pesata = (len(sx) * gini(sx) + len(dx) * gini(dx)) / len(y)
    if migliore is None or pesata < migliore[1]:
        migliore = (t, pesata)
    print(f"soglia {t:4.1f}: Gini pesato dei figli = {pesata:.4f}")
print("soglia migliore a mano:", migliore[0], " riduzione di impurita':", round(gini(y) - migliore[1], 4))

albero = DecisionTreeClassifier(max_depth=1, random_state=0).fit(x[:, None], y)
print("soglia scelta da sklearn:", albero.tree_.threshold[0], " impurita' radice e figli:", albero.tree_.impurity.round(4).tolist())

# Output:
# impurita' della radice: Gini = 0.5  entropia = 1.0
# soglia  1.5: Gini pesato dei figli = 0.4444
# soglia  2.5: Gini pesato dei figli = 0.3750
# soglia  3.5: Gini pesato dei figli = 0.2857
# soglia  4.5: Gini pesato dei figli = 0.4167
# soglia  5.5: Gini pesato dei figli = 0.3200
# soglia  6.5: Gini pesato dei figli = 0.4167
# soglia  7.5: Gini pesato dei figli = 0.4762
# soglia  8.5: Gini pesato dei figli = 0.5000
# soglia  9.5: Gini pesato dei figli = 0.4444
# soglia migliore a mano: 3.5  riduzione di impurita': 0.2143
# soglia scelta da sklearn: 3.5  impurita' radice e figli: [0.5, 0.0, 0.4082]

Delle nove soglie, la 3,5 dà il Gini pesato più basso (0,2857), con una riduzione di impurità di 0,2143 rispetto alla radice; scikit-learn sceglie la stessa soglia e riporta le stesse impurità, 0,5 per la radice, 0,0 e 0,4082 per i figli. La soglia 5,5 è seconda (0,3200). Il metodo non garantisce l'albero ottimo, perché ogni scelta guarda solo il passo corrente; per questo due alberi addestrati su campioni leggermente diversi possono essere molto diversi.

Per un problema di regressione le foglie contengono la media dei valori degli esempi che vi arrivano, e l'impurità diventa l'errore quadratico dentro il nodo: si sceglie la soglia che minimizza la somma degli errori quadratici dei due figli. La regola di divisione è la stessa, cambia solo la misura.

Perché un albero sovradatta, e la potatura

Un albero senza limiti continua a dividere finché ogni foglia è pura: sul training l'errore è zero, e il costo sono foglie che descrivono il rumore. Il listato mostra l'accuratezza su training e su test (30% dei dati, 171 esempi) al crescere della profondità massima, e poi la potatura per costo-complessità (cost-complexity pruning): si definisce un costo errore + α·(numero di foglie), e per ogni α esiste un sottoalbero ottimo; cost_complexity_pruning_path calcola la sequenza degli α in cui cambia, e si sceglie l'α con la validazione incrociata sul solo training.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import GridSearchCV, StratifiedKFold, train_test_split
from sklearn.tree import DecisionTreeClassifier

X, y = load_breast_cancer(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
print("profondita' | foglie | accuratezza train | accuratezza test")
for d in (1, 2, 3, 5, 8, None):
    t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(Xtr, ytr)
    print(f"{str(d):>11} | {t.get_n_leaves():6d} | {t.score(Xtr, ytr):17.3f} | {t.score(Xte, yte):.3f}")

# potatura per costo-complessita': la sequenza di alpha viene dall'albero completo
percorso = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(Xtr, ytr)
alphas = np.unique(percorso.ccp_alphas.round(6))
gs = GridSearchCV(DecisionTreeClassifier(random_state=0), {"ccp_alpha": alphas},
                  cv=StratifiedKFold(5, shuffle=True, random_state=0)).fit(Xtr, ytr)
t = gs.best_estimator_
print(f"alpha candidati: {len(alphas)}; scelto per CV: {gs.best_params_['ccp_alpha']:.5f}; foglie={t.get_n_leaves()}; "
      f"train={t.score(Xtr, ytr):.3f} test={t.score(Xte, yte):.3f}")

# Output:
# profondita' | foglie | accuratezza train | accuratezza test
#           1 |      2 |             0.932 | 0.889
#           2 |      4 |             0.942 | 0.906
#           3 |      8 |             0.980 | 0.901
#           5 |     15 |             0.997 | 0.912
#           8 |     16 |             1.000 | 0.906
#        None |     16 |             1.000 | 0.906
# alpha candidati: 12; scelto per CV: 0.01959; foglie=5; train=0.972 test=0.918

Con profondità 1 l'albero ha 2 foglie e accuratezza di test 0,889; a profondità 5 ne ha 15 con test 0,912; da profondità 8 in poi l'albero è completo con 16 foglie, training 1,000 e test 0,906. Qui l'albero completo ha soltanto 16 foglie perché le classi sono ben separate, ma il segno del sovradattamento si vede: il training sale fino a 1,000 mentre il test si ferma attorno a 0,91. La potatura con α scelto per validazione (0,01959) lascia 5 foglie, con training 0,972 e test 0,918: un albero molto più semplice che non perde in test. Non esagerare le differenze: 0,918 e 0,906 su 171 esempi distano di due esempi, ed entrambi i valori sono compatibili con la stessa qualità reale. Il vantaggio dell'albero potato è più nella leggibilità che nel punteggio.

Dalla instabilità alla foresta

Un albero singolo ha poco bias e molta varianza, esattamente il caso in cui mediare aiuta (capitolo 04). La foresta casuale combina due idee. La prima è il bagging: ogni albero è addestrato su un campione estratto con reinserimento dal training (bootstrap), che contiene in media circa il 63% degli esempi distinti, perché la probabilità che un esempio non venga mai estratto in n estrazioni è (1 − 1/n)ⁿ, che tende a 0,368. La seconda è la scelta casuale delle feature: a ogni divisione l'albero considera solo un sottoinsieme di m misure scelte a caso, tipicamente m ≈ √p per la classificazione, e il manuale (paragrafo 8.2.2) ne spiega il motivo: se una misura è molto forte, tutti gli alberi la userebbero in cima e sarebbero simili fra loro, mentre mediare alberi molto correlati riduce poco la varianza. La documentazione di scikit-learn indica max_features="sqrt" come valore empiricamente buono per la classificazione, e max_features=None, tutte le feature, equivale al bagging di alberi.

Gli esempi esclusi dal campione di un albero (circa il 37%) sono per quell'albero esempi di test gratis: la previsione out-of-bag (OOB) di ogni esempio è la media dei soli alberi che non l'hanno visto, e l'accuratezza di quelle previsioni è una stima dell'errore di test senza validazione incrociata (manuale, paragrafo 8.2.1). Il listato usa un problema sintetico con rumore sulle etichette (10%), 20 misure di cui 5 informative e 5 ridondanti.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.tree import DecisionTreeClassifier

X, y = make_classification(n_samples=1000, n_features=20, n_informative=5, n_redundant=5,
                           flip_y=0.1, class_sep=1.0, random_state=0)
cv = StratifiedKFold(5, shuffle=True, random_state=0)
def cvm(m): return cross_val_score(m, X, y, cv=cv).mean()

print("un albero senza limiti:", round(cvm(DecisionTreeClassifier(random_state=0)), 3))
for n in (1, 10, 50, 200):
    print(f"foresta, {n:3d} alberi (max_features='sqrt'):", round(cvm(RandomForestClassifier(n_estimators=n, random_state=0)), 3))
print("foresta, 200 alberi, max_features=None (= bagging puro):",
      round(cvm(RandomForestClassifier(n_estimators=200, max_features=None, random_state=0)), 3))
rf = RandomForestClassifier(n_estimators=200, oob_score=True, random_state=0).fit(X, y)
print("stima OOB della foresta da 200 alberi:", round(rf.oob_score_, 3))

# Output:
# un albero senza limiti: 0.842
# foresta,   1 alberi (max_features='sqrt'): 0.843
# foresta,  10 alberi (max_features='sqrt'): 0.911
# foresta,  50 alberi (max_features='sqrt'): 0.92
# foresta, 200 alberi (max_features='sqrt'): 0.923
# foresta, 200 alberi, max_features=None (= bagging puro): 0.906
# stima OOB della foresta da 200 alberi: 0.922

Un albero senza limiti raggiunge 0,842 in validazione incrociata a 5 blocchi; una foresta con un solo albero fa praticamente lo stesso (0,843), com'è giusto. Con 10 alberi si arriva a 0,911, con 50 a 0,920, con 200 a 0,923: il guadagno è rapido all'inizio e poi si appiattisce, e in questo esperimento aggiungere alberi non peggiora il risultato, ma costa tempo di calcolo e di previsione. Il bagging puro, con 200 alberi e tutte le feature a ogni divisione, ottiene 0,906: la scelta casuale delle feature aggiunge circa 1,7 punti sopra il bagging in questo esperimento, perché decorrela gli alberi. La stima OOB della foresta da 200 alberi è 0,922, praticamente quella della validazione incrociata (0,923), e si ottiene da un solo addestramento. Sono risultati su un solo dataset sintetico: non fissano una regola, ma mostrano il meccanismo.

L'importanza delle feature, e perché fidarsi poco

Una foresta restituisce per ogni feature un'importanza di impurità (feature_importances_): quanto, in media, le divisioni su quella feature riducono l'impurità. È gratuita ma, avverte la documentazione di scikit-learn, è calcolata sul training ed è fortemente sbilanciata a favore delle feature con molti valori distinti, tipicamente le numeriche continue. L'alternativa è l'importanza per permutazione: si mescolano i valori di una feature nell'insieme di test e si misura di quanto cala l'accuratezza. Costruiamo un caso in cui la risposta è nota: tre feature informative e una colonna di rumore puro, continua.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=1500, n_features=3, n_informative=3, n_redundant=0,
                           n_clusters_per_class=1, flip_y=0.15, random_state=0)
rumore = np.random.default_rng(0).standard_normal((len(y), 1))      # una colonna di puro rumore, continua
X = np.hstack([X, rumore])                                          # indice 3 = rumore
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)
rf = RandomForestClassifier(n_estimators=200, min_samples_leaf=1, random_state=0).fit(Xtr, ytr)
print("train:", round(rf.score(Xtr, ytr), 3), " test:", round(rf.score(Xte, yte), 3))
print("importanza di impurita' (feature 0,1,2 e rumore):", rf.feature_importances_.round(3).tolist())
pi = permutation_importance(rf, Xte, yte, n_repeats=20, random_state=0)
print("importanza per permutazione sul test:           ", pi.importances_mean.round(3).tolist())

# Output:
# train: 1.0  test: 0.891
# importanza di impurita' (feature 0,1,2 e rumore): [0.12, 0.684, 0.106, 0.089]
# importanza per permutazione sul test:            [0.011, 0.388, 0.029, 0.007]

La foresta è perfetta sul training (1,000) e arriva a 0,891 sul test. L'importanza di impurità assegna alla colonna di rumore 0,089, quasi quanto alla feature 2 (0,106) e alla feature 0 (0,120): leggendola si concluderebbe che il rumore conta. L'importanza per permutazione sul test dà al rumore 0,007, praticamente zero, e riconosce che la feature 1 pesa molto più di tutte (0,388). La differenza nasce dal fatto che le impurità si misurano sul training, dove il rumore è stato usato per dividere gli esempi, mentre le permutazioni si valutano su dati che il modello non ha visto. La documentazione avverte anche che questa importanza descrive quanto la feature serve a un modello particolare e non il suo valore intrinseco, e che ha senso solo se il modello è buono sui dati di test.

Quando non usare alberi e foreste

• Serve estrapolare oltre l'intervallo dei dati: un albero prevede costante nell'ultima foglia, quindi una tendenza crescente viene appiattita fuori dall'intervallo del training.
• Serve un modello da spiegare passo passo: una foresta di 200 alberi non si legge, e l'albero singolo potato conserva la leggibilità a costo di un po' di accuratezza.
• La relazione è davvero lineare con molte misure rumorose: un modello lineare con penalità (capitolo 02) è più semplice e stabile.

Le tre voci sono limiti diversi di uno stesso aspetto: gli alberi approssimano con tratti costanti. Lo fanno benissimo dove ci sono soglie e interazioni, e male dove c'è continuità e tendenza. Il boosting, che costruisce alberi in sequenza invece che in parallelo, è un'altra famiglia e non è trattato in questo articolo.

Che cosa sai fare adesso

Sai calcolare a mano la divisione di un nodo con Gini ed entropia e verificarla con scikit-learn, riconoscere il sovradattamento di un albero dai due errori e potarlo con α scelto per validazione, spiegare perché la foresta riduce la varianza con bagging e feature casuali, stimarne l'errore con l'OOB, e usare l'importanza per permutazione al posto di quella di impurità. Il capitolo successivo cambia idea di separazione: invece di soglie, un margine massimo fra le classi, con 07 - Support Vector Machines e kernel trick.

Nella stessa serie trovi anche: 03 - Regressione Logistica e classificazione binaria, 11 - Metriche e valutazione modelli ML e 12 - Deployment ML in produzione: serving e monitoring.