35 - Alberi decisionali: come si sceglie una domanda con Gini ed entropia

Conosci il gioco delle venti domande: devi indovinare un oggetto facendo domande a cui si risponde sì o no. Chi gioca bene non chiede a caso: la prima domanda è quella che divide le possibilità più o meno a metà («è un essere vivente?»), la successiva dipende dalla risposta. Un albero decisionale è esattamente un gioco delle venti domande appreso dai dati: una sequenza di test sulle feature («lunghezza del petalo ≤ 2,45?») che porta a una foglia con la previsione.

Il punto interessante è come si sceglie la domanda giusta. Serve un modo di misurare quanto un gruppo di esempi è «mescolato», e quanto una domanda riduce il disordine. Quel modo si chiama impurità, e ne vedremo due: l'indice di Gini e l'entropia.

Anatomia di un albero

• Nodo: un punto dell'albero dove si pone una domanda sulla feature (per esempio «larghezza petalo ≤ 0,8?»). La domanda è un confronto con una soglia.
• Radice: il primo nodo, in cima, dove arrivano tutti gli esempi.
• Ramo: l'esito di una domanda (sì/no). Gli esempi seguono il ramo giusto.
• Foglia: un nodo finale, senza domande, che contiene la previsione (la classe più frequente tra gli esempi che ci arrivano).
• Profondità: il numero massimo di domande che separa la radice da una foglia.
• Ricorsione: costruire un albero significa costruire alberi più piccoli sui due sottoinsiemi, e così via, finché un criterio di arresto dice basta.

Le sei voci sono un vocabolario ma anche una sequenza: la radice riceve tutti gli esempi, ogni nodo li divide con una soglia, i rami portano alle foglie, e la profondità misura quante domande servono al massimo. La parola che spiega tutto il resto è «ricorsione»: un albero è un nodo con due alberi più piccoli sotto, ed è per questo che il codice più sotto è una funzione che richiama sé stessa.

Misurare il disordine: Gini ed entropia

Considera un nodo che contiene esempi di K classi, con p_k la frazione di esempi della classe k. Un nodo è puro se contiene una sola classe. Le due misure più usate:

Gini(nodo)     = 1 − Σ_k p_k²

Entropia(nodo) = − Σ_k p_k · log₂(p_k)        (con 0·log 0 = 0)

L'intuizione di Gini: se estrai due esempi a caso (con reinserimento) dal nodo, Σ p_k² è la probabilità che abbiano la stessa classe; 1 meno quella è la probabilità che siano diversi. Un nodo puro dà 0; due classi al 50% danno 0,5, il massimo per due classi. L'entropia, già incontrata nella teoria dell'informazione, misura la sorpresa media: 0 per un nodo puro, 1 bit per due classi equiprobabili.

import numpy as np

def gini(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    return 1.0 - (p ** 2).sum()

def entropia(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    p = p[p > 0]
    return float(-(p * np.log2(p)).sum()) + 0.0

for nome, y in [("puro 10/0", np.array([0] * 10)),
                ("90/10", np.array([0] * 9 + [1])),
                ("70/30", np.array([0] * 7 + [1] * 3)),
                ("50/50", np.array([0] * 5 + [1] * 5))]:
    print("%-10s Gini %.3f   Entropia %.3f" % (nome, gini(y), entropia(y)))

puro 10/0  Gini 0.000   Entropia 0.000
90/10      Gini 0.180   Entropia 0.469
70/30      Gini 0.420   Entropia 0.881
50/50      Gini 0.500   Entropia 1.000

Cosa fa il codice. np.bincount(y) conta quante volte compare ciascuna classe (interi non negativi), e dividendo per len(y) si ottengono le frequenze p_k. gini applica 1 − Σp²; entropia scarta le probabilità nulle (p[p > 0], perché 0·log 0 non è definito numericamente e per convenzione vale 0) e applica −Σp·log₂p. I quattro nodi di prova vanno dal puro al perfettamente misto: per il nodo 70/30 si legge Gini 0,420 (= 1 − 0,49 − 0,09) ed entropia 0,881.

Le due misure hanno andamento molto simile: zero sul nodo puro, massimo sul 50/50. Nella pratica i due criteri producono spesso alberi simili, ma non sempre: l'esercizio più sotto mostra un caso in cui scelgono radici diverse. Gini non richiede il logaritmo, quindi costa un po' meno da calcolare; scikit-learn usa gini come criterio predefinito.

Quanto vale una domanda: la riduzione di impurità

Una domanda divide un nodo padre di n esempi in due figli, sinistro (n_L esempi) e destro (n_R). L'impurità dei figli va pesata per la loro dimensione, altrimenti un figlio minuscolo ma puro ingannerebbe la misura. Il guadagno è:

Δ = I(padre) − ( n_L/n · I(sinistro) + n_R/n · I(destro) )

Con l'entropia come I questo Δ si chiama guadagno di informazione. Un esempio svolto a mano: un nodo con 10 esempi, 6 della classe A e 4 della classe B. Una domanda manda a sinistra 5 esempi tutti di A, a destra gli altri 5 (1 di A e 4 di B).

Gini(padre)    = 1 − (0,6² + 0,4²)  = 1 − 0,52  = 0,48
Gini(sinistro) = 1 − (1² + 0²)      = 0
Gini(destro)   = 1 − (0,2² + 0,8²)  = 1 − 0,68  = 0,32
Impurità pesata = 5/10 · 0 + 5/10 · 0,32 = 0,16
Δ = 0,48 − 0,16 = 0,32

Il codice che segue calcola la stessa cosa per Gini ed entropia con una piccola funzione peso che applica la media pesata. Si vede che con l'entropia il guadagno vale 0,610 e con Gini 0,320: i numeri assoluti non sono confrontabili tra criteri, ma l'ordine delle domande (quale è migliore) di solito coincide.

Tra tutte le domande possibili si sceglie quella con Δ massimo. Verifichiamo il conto con il codice:

padre = np.array([0] * 6 + [1] * 4)
sx = np.array([0] * 5)
dx = np.array([0] * 1 + [1] * 4)
peso = lambda f, a, b: len(a) / len(padre) * f(a) + len(b) / len(padre) * f(b)
print("Gini:     padre %.3f  pesata figli %.3f  guadagno %.3f" % (gini(padre), peso(gini, sx, dx), gini(padre) - peso(gini, sx, dx)))
print("Entropia: padre %.3f  pesata figli %.3f  guadagno %.3f" % (entropia(padre), peso(entropia, sx, dx), entropia(padre) - peso(entropia, sx, dx)))

Gini:     padre 0.480  pesata figli 0.160  guadagno 0.320
Entropia: padre 0.971  pesata figli 0.361  guadagno 0.610

L'uscita conferma il conto a mano: con Gini il padre vale 0,480 e i figli pesati 0,160, quindi il guadagno è 0,320. Con l'entropia i valori sono 0,971, 0,361 e 0,610. In entrambi i casi la domanda toglie circa due terzi dell'impurità del padre, ma i numeri sono su scale diverse e non si confrontano tra misure. Nell'esercizio che segue vedrai che anche l'ordine delle domande può cambiare.

DOMANDA A - "arriva dalla chat del prodotto?"
   si' (60):  60 informazioni ,  0 bug
   no  (40):  20 informazioni , 20 bug

DOMANDA B - "contiene un allegato?"
   no  (90):  80 informazioni , 10 bug
   si' (10):   0 informazioni , 10 bug

L'algoritmo: ricerca golosa e ricorsiva

Il metodo standard (CART, Classification And Regression Trees) è goloso (greedy): a ogni nodo prova tutte le feature e, per ogni feature numerica, tutte le soglie candidate (i punti medi tra valori consecutivi ordinati), sceglie la coppia (feature, soglia) con Δ massimo, divide, e ripete su ciascun figlio. Si ferma quando il nodo è puro, o raggiunge una profondità massima, o ha troppo pochi esempi. La foglia predice la classe maggioritaria dei suoi esempi.

«Goloso» significa che la scelta migliore adesso non garantisce l'albero migliore in assoluto: trovare l'albero ottimo è un problema computazionalmente intrattabile, e si ripiega su questa euristica che nella pratica funziona bene.

Implementazione a mano

Costruiamo l'albero su Iris (150 fiori, 4 misure, 3 specie) con soli due pezzi: migliore_divisione, che prova ogni coppia (feature, soglia) e tiene quella con il guadagno più alto, e costruisci, che la applica ricorsivamente fino a una profondità massima. Il risultato viene confrontato con DecisionTreeClassifier, a parità di criterio e di profondità.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

def migliore_divisione(X, y, impurita):
    n, d = X.shape
    migliore = (None, None, 0.0)                     # (feature, soglia, guadagno)
    base = impurita(y)
    for j in range(d):
        valori = np.unique(X[:, j])
        for s in (valori[:-1] + valori[1:]) / 2:     # punti medi tra valori consecutivi
            sx = X[:, j] <= s
            nl = sx.sum()
            guadagno = base - (nl / n * impurita(y[sx]) + (n - nl) / n * impurita(y[~sx]))
            if guadagno > migliore[2] + 1e-12:
                migliore = (j, s, guadagno)
    return migliore

def costruisci(X, y, impurita, profondita=0, max_prof=3, min_campioni=2):
    if profondita >= max_prof or len(y) < min_campioni or impurita(y) == 0:
        return {"foglia": int(np.bincount(y).argmax())}
    j, s, g = migliore_divisione(X, y, impurita)
    if j is None:
        return {"foglia": int(np.bincount(y).argmax())}
    sx = X[:, j] <= s
    return {"feature": j, "soglia": s,
            "sx": costruisci(X[sx], y[sx], impurita, profondita + 1, max_prof, min_campioni),
            "dx": costruisci(X[~sx], y[~sx], impurita, profondita + 1, max_prof, min_campioni)}

def prevedi_uno(nodo, x):
    while "foglia" not in nodo:
        nodo = nodo["sx"] if x[nodo["feature"]] <= nodo["soglia"] else nodo["dx"]
    return nodo["foglia"]

Xi, yi = load_iris(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xi, yi, test_size=0.3, stratify=yi, random_state=0)

albero = costruisci(Xtr, ytr, gini, max_prof=3)
pred = np.array([prevedi_uno(albero, x) for x in Xte])
sk = DecisionTreeClassifier(criterion="gini", max_depth=3, random_state=0).fit(Xtr, ytr)

print("radice a mano:  feature %d, soglia %.3f" % (albero["feature"], albero["soglia"]))
print("radice sklearn: feature %d, soglia %.3f" % (sk.tree_.feature[0], sk.tree_.threshold[0]))
print("accuratezza a mano %.3f   sklearn %.3f" % ((pred == yte).mean(), sk.score(Xte, yte)))
print()
print(export_text(sk, feature_names=["lung_sepalo", "larg_sepalo", "lung_petalo", "larg_petalo"]))

radice a mano:  feature 2, soglia 2.350
radice sklearn: feature 3, soglia 0.800
accuratezza a mano 0.956   sklearn 0.956

|--- larg_petalo <= 0.80
|   |--- class: 0
|--- larg_petalo >  0.80
|   |--- larg_petalo <= 1.75
|   |   |--- lung_petalo <= 4.95
|   |   |   |--- class: 1
|   |   |--- lung_petalo >  4.95
|   |   |   |--- class: 1
|   |--- larg_petalo >  1.75
|   |   |--- lung_petalo <= 4.85
|   |   |   |--- class: 2
|   |   |--- lung_petalo >  4.85
|   |   |   |--- class: 2

Cosa fa il codice. migliore_divisione scorre tutte le feature j; per ognuna prende i valori distinti ordinati (np.unique) e propone come soglie i punti medi tra valori consecutivi: una soglia in mezzo a due valori vicini separa gli esempi in modo diverso da ogni altra. Per ogni soglia calcola la maschera booleana sx degli esempi a sinistra e il guadagno pesato. Tiene il migliore. costruisci è ricorsiva: se ha raggiunto la profondità massima, ha pochi esempi o il nodo è già puro (impurità zero) restituisce una foglia con la classe più frequente (np.bincount(y).argmax()); altrimenti trova la miglior divisione e richiama sé stessa sui due sottoinsiemi. prevedi_uno scende l'albero dalla radice seguendo le soglie fino a una foglia. L'albero è un dizionario annidato: nessuna classe, nessuna dipendenza.

Un dettaglio istruttivo: la radice a mano usa la feature 2 (lunghezza petalo, soglia 2.35), quella di scikit-learn la feature 3 (larghezza petalo, soglia 0.80). Non è un errore: entrambe isolano perfettamente la classe 0, quindi hanno lo stesso guadagno, e vince la prima trovata. In scikit-learn le feature vengono esaminate in ordine casuale a ogni divisione, e la documentazione di DecisionTreeClassifier avverte che con guadagni identici la divisione scelta può variare; fissare random_state rende il comportamento deterministico. L'accuratezza sul test è identica (0.956).

Guarda anche le due foglie in fondo a ciascun ramo dell'albero stampato: sotto «larg_petalo ≤ 1.75» la divisione su «lung_petalo ≤ 4.95» produce due foglie della stessa classe 1, e sotto l'altro ramo due foglie della classe 2. Quella domanda non cambia nessuna previsione, ma riduce l'impurità (separa pochi esempi di un'altra classe), ed è per questo che l'algoritmo goloso la sceglie comunque. Un albero può quindi contenere divisioni che non servono alla previsione: la potatura, più sotto, ne elimina molte.

L'albero è leggibile come un insieme di regole «se... allora...»: è il suo punto di forza rispetto a quasi tutti gli altri modelli, e conta molto quando devi spiegare una decisione a una persona o a un auditor.

La trappola principale: l'albero profondo memorizza

Se non lo fermi, un albero continua a dividere finché ogni foglia è pura, cioè finché ha memorizzato il training set. Lo vediamo sul dataset Breast Cancer (569 casi, 30 feature) facendo crescere la profondità:

from sklearn.datasets import load_breast_cancer

Xb, yb = load_breast_cancer(return_X_y=True)
Xbt, Xbe, ybt, ybe = train_test_split(Xb, yb, test_size=0.3, stratify=yb, random_state=0)

for prof in (1, 2, 3, 5, 8, None):
    t = DecisionTreeClassifier(max_depth=prof, random_state=0).fit(Xbt, ybt)
    print("max_depth=%-4s foglie %3d   train %.3f   test %.3f" % (
        prof, t.get_n_leaves(), t.score(Xbt, ybt), t.score(Xbe, ybe)))

max_depth=1    foglie   2   train 0.932   test 0.889
max_depth=2    foglie   4   train 0.942   test 0.906
max_depth=3    foglie   8   train 0.980   test 0.901
max_depth=5    foglie  15   train 0.997   test 0.912
max_depth=8    foglie  16   train 1.000   test 0.906
max_depth=None foglie  16   train 1.000   test 0.906

Cosa fa il codice: carica Breast Cancer (569 pazienti, 30 misure da immagini di cellule, etichetta benigno/maligno), divide in modo stratificato e addestra alberi con profondità massima crescente; max_depth=None significa nessun limite. get_n_leaves() conta le foglie, una misura diretta della complessità.

Senza limite di profondità l'accuratezza sul training è 1.000 e l'albero arriva a 16 foglie: ha una regola per quasi ogni caso. Il test però non migliora: con soli 4 foglie (profondità 2) fa 0.906, come l'albero completo. Su questo dataset la complessità in più non compra nulla. Gli iperparametri che controllano la complessità sono max_depth, min_samples_leaf (minimo di esempi per foglia), min_samples_split e ccp_alpha (potatura a posteriori che elimina rami il cui guadagno non giustifica la complessità). Si scelgono con la validazione incrociata.

Trappola: le colonne di rumore e le etichette sporche

Quando i dati hanno etichette rumorose (errori di annotazione, casi ambigui), un albero senza limiti non si accontenta di ciò che è spiegabile: continua a dividere finché non isola anche gli errori, e per farlo ha bisogno di qualsiasi colonna con soglie da provare, anche se non contiene informazione. Costruiamo un caso controllato: tre feature informative, il 15% delle etichette sbagliate, e confrontiamo l'albero con e senza dieci colonne di rumore puro.

from sklearn.datasets import make_classification

Xi3, yi3 = make_classification(n_samples=1000, n_features=3, n_informative=3, n_redundant=0,
                               n_clusters_per_class=1, flip_y=0.15, shuffle=False, random_state=0)
rng = np.random.default_rng(0)
Xn = np.hstack([Xi3, rng.normal(size=(1000, 10))])           # 3 colonne vere + 10 di rumore
Xt, Xe, yt, ye = train_test_split(Xn, yi3, test_size=0.3, stratify=yi3, random_state=0)

for nome, cols in (("3 informative", slice(0, 3)), ("3 informative + 10 rumore", slice(0, 13))):
    t = DecisionTreeClassifier(random_state=0).fit(Xt[:, cols], yt)
    imp = t.feature_importances_
    print("%-26s foglie %3d  train %.3f  test %.3f  importanza assegnata al rumore: %.3f" % (
        nome, t.get_n_leaves(), t.score(Xt[:, cols], yt), t.score(Xe[:, cols], ye),
        imp[3:].sum() if imp.size > 3 else 0.0))

3 informative              foglie  96  train 1.000  test 0.830  importanza assegnata al rumore: 0.000
3 informative + 10 rumore  foglie  72  train 1.000  test 0.797  importanza assegnata al rumore: 0.212

Cosa fa il codice: make_classification con shuffle=False mantiene le 3 colonne informative in prima posizione, così possiamo sapere quali sono. flip_y=0.15 inverte il 15% delle etichette. Si aggiungono con np.hstack dieci colonne di rumore gaussiano. Per ciascuna configurazione si addestra un albero senza limiti e si somma l'importanza delle colonne di rumore (imp[3:].sum()): feature_importances_ è la riduzione di impurità totale attribuita a ciascuna feature, normalizzata a somma 1.

Nei due casi l'albero raggiunge 1.000 sul training con decine di foglie: sta memorizzando le etichette sbagliate. Con le colonne di rumore a disposizione l'albero attribuisce loro il 21,2% dell'importanza totale e il test scende da 0.830 a 0.797 (una sola divisione 70/30 e un solo seme, quindi la differenza è un'indicazione, non una misura). Nota che nel dataset Breast Cancer di prima, dove le feature vere separano bene le classi, il rumore non sarebbe stato usato: il problema si manifesta quando i dati sono sporchi. Per questo l'importanza delle feature calcolata sul training (impurità media) va letta con cautela; l'alternativa più robusta è la permutation importance calcolata su dati di validazione.

Instabilità: piccoli cambi nei dati, alberi diversi

Gli alberi sono modelli ad alta varianza. Se addestri lo stesso algoritmo su campioni leggermente diversi della stessa popolazione, ottieni alberi anche molto diversi. Prova con cinque ricampionamenti del training set (estraendo con reinserimento):

nomi = load_breast_cancer().feature_names
for seed in range(5):
    r = np.random.default_rng(seed)
    idx = r.integers(0, len(Xbt), size=len(Xbt))
    t = DecisionTreeClassifier(max_depth=3, random_state=0).fit(Xbt[idx], ybt[idx])
    print("campione %d: radice = %-22s soglia %.3f   test %.3f" % (
        seed, nomi[t.tree_.feature[0]], t.tree_.threshold[0], t.score(Xbe, ybe)))

campione 0: radice = worst perimeter        soglia 110.050   test 0.906
campione 1: radice = worst perimeter        soglia 106.100   test 0.912
campione 2: radice = worst concave points   soglia 0.115   test 0.906
campione 3: radice = worst radius           soglia 16.815   test 0.947
campione 4: radice = worst radius           soglia 17.005   test 0.936

La radice cambia da campione a campione: «worst perimeter» in due casi, «worst concave points» in uno, «worst radius» in due, con soglie diverse, e l'accuratezza sul test oscilla tra 0.906 e 0.947. Nessuna di queste feature è «sbagliata» (sono tutte molto correlate tra loro), ma la struttura che leggi dall'albero dipende dal campione che hai in mano. Questa instabilità è il difetto che in Random Forest trasformiamo in vantaggio: se un solo albero è instabile, la media di molti alberi diversi no.

Trade-off

• Pro: interpretabili, non richiedono scaling né normalizzazione, gestiscono feature numeriche e categoriche (con codifica), catturano interazioni e non linearità senza che tu le specifichi, veloci da usare in previsione.
• Contro: overfitting facile, alta varianza, confini a «scalini» ortogonali agli assi (una diagonale richiede molti scalini), nella regressione non estrapolano oltre l'intervallo visto in training (predicono costanti a tratti).
• Gini o entropia? Nella pratica la differenza è piccola. Parti dal default (Gini) e cambia solo se la validazione lo giustifica.

I vantaggi e gli svantaggi vengono dalla stessa scelta: un albero è un insieme di regole esplicite, quindi leggibile e senza bisogno di preparare i dati, ma ogni regola è una soglia rigida su una sola feature, e questo lo rende instabile e incline a memorizzare. La documentazione di scikit-learn dice che il costo di una previsione è logaritmico nel numero di esempi di training e che gli alberi non sono adatti a estrapolare, perché le loro previsioni sono costanti a tratti.

Trappole reali

• Accuratezza di training a 1.0 è un sintomo di overfitting, non un successo.
• Classi sbilanciate: le foglie pure della classe maggioritaria dominano. Usa class_weight="balanced" e valuta con recall e precision.
• Colonne identificative lasciate nel dataset (id, indirizzo email, timestamp unico): l'albero le sfrutta per memorizzare. Toglile.
• Soglie su dati in produzione che hanno un'altra distribuzione del training: l'albero non ha alcuna «morbidezza», un valore appena oltre la soglia cambia ramo.
• Leggere troppo un singolo albero: la sua struttura è instabile, non è una «legge» sul fenomeno.

Le cinque trappole condividono una causa: l'albero fa esattamente ciò che gli chiedi, cioè ridurre l'impurità sul training, e lo fa anche quando l'unico modo è usare un identificatore, un'etichetta sbagliata o una soglia fortuita. Quindi nessuna di queste trappole produce un errore o un avviso: le trovi solo guardando il test, l'importanza per permutazione e la stabilità fra campioni.

Alberi per la regressione: la riduzione della varianza

Finora l'albero prevedeva una classe. Per prevedere un numero la struttura è identica: cambiano il criterio con cui si sceglie la divisione e il valore nelle foglie. Invece di Gini o entropia si usa la riduzione della somma dei quadrati degli scarti (SSE, equivalente a ridurre la varianza): una divisione è buona se i valori in ciascun figlio sono più vicini alla propria media che i valori del padre alla media del padre. La foglia prevede la media dei valori che ci arrivano, che è il valore che minimizza l'errore quadratico in quella foglia (la media è il valore che minimizza la somma dei quadrati degli scarti, lo stesso argomento del centroide in K-Means).

from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(0)
x_r = np.sort(rng.uniform(0, 6, 120))
y_r = np.sin(x_r) + rng.normal(0, 0.3, 120)                           # sinusoide con rumore

def best_regression_split(x, y):
    best_threshold, best_sse = None, np.inf
    for threshold in (x[:-1] + x[1:]) / 2:                             # punti medi tra valori consecutivi
        left, right = y[x <= threshold], y[x > threshold]
        sse = ((left - left.mean()) ** 2).sum() + ((right - right.mean()) ** 2).sum()
        if sse < best_sse:
            best_threshold, best_sse = threshold, sse
    return best_threshold, ((y - y.mean()) ** 2).sum() - best_sse     # soglia e riduzione di SSE

threshold, gain = best_regression_split(x_r, y_r)
sk = DecisionTreeRegressor(max_depth=1).fit(x_r[:, None], y_r)
print("a mano:      soglia %.4f   riduzione di SSE %.2f   medie nelle foglie %.4f e %.4f" % (
    threshold, gain, y_r[x_r <= threshold].mean(), y_r[x_r > threshold].mean()))
print("scikit-learn: soglia %.4f                                medie nelle foglie %.4f e %.4f" % (
    sk.tree_.threshold[0], sk.tree_.value[1, 0, 0], sk.tree_.value[2, 0, 0]))

x_grid = np.linspace(0, 6, 300)
print("\nprofondità   foglie   errore sulla funzione vera   errore sul training")
for depth in (1, 2, 3, 5, 8, None):
    m = DecisionTreeRegressor(max_depth=depth, random_state=0).fit(x_r[:, None], y_r)
    print("%-9s   %5d   %26.4f   %17.4f" % (depth, m.get_n_leaves(), ((m.predict(x_grid[:, None]) - np.sin(x_grid)) ** 2).mean(), ((m.predict(x_r[:, None]) - y_r) ** 2).mean()))

a mano:      soglia 3.2412   riduzione di SSE 50.17   medie nelle foglie 0.5460 e -0.7487
scikit-learn: soglia 3.2412                                medie nelle foglie 0.5460 e -0.7487

profondità   foglie   errore sulla funzione vera   errore sul training
1               2                       0.0907              0.1459
2               4                       0.0625              0.1160
3               8                       0.0333              0.0778
5              29                       0.0564              0.0509
8              87                       0.0971              0.0079
None          120                       0.1035              0.0000

Cosa fa il codice. best_regression_split scorre le soglie candidate (come per la classificazione) e per ciascuna calcola la somma dei quadrati degli scarti nei due figli rispetto alle rispettive medie; tiene la soglia che minimizza la somma, e restituisce anche la riduzione rispetto al padre (50,17). La divisione trovata a mano, 3,2412, coincide con quella di scikit-learn, e le medie nelle foglie (0,546 e −0,749) sono i valori che l'albero prevede: una costante per x ≤ 3,24 e un'altra per x > 3,24.

Poi si fa crescere la profondità e si misura l'errore rispetto al seno vero sulla griglia (possibile perché i dati sono sintetici) e quello sul training. Il profilo è quello di sempre: l'errore sul training cala monotonicamente fino a zero (con 120 foglie l'albero memorizza ogni punto, rumore compreso), mentre l'errore rispetto alla funzione vera ha un minimo a profondità 3 (0,033, con 8 foglie) e poi risale: 0,056 a profondità 5, 0,097 a 8 e 0,104 senza limite, quasi il valore del caso peggiore, cioè la varianza del rumore (0,09) più un po'. L'albero di regressione disegna una funzione a gradini, e con pochi gradini approssima bene la curva liscia; con troppi, insegue il rumore. È lo stesso compromesso, con gli stessi rimedi (profondità massima, foglie minime, potatura) e la stessa conseguenza: fuori dall'intervallo dei dati predice una costante.

La potatura per complessità di costo: scegliere la dimensione dell'albero

Limitare la profondità a priori è una scelta grossolana. Un approccio più fine è far crescere l'albero completo e poi potarlo. La potatura per complessità di costo (CCP, Breiman e coll. 1984) penalizza il numero di foglie: per un parametro α ≥ 0 minimizza SSE_albero + α·(numero di foglie), o l'analoga con l'impurità. Con α = 0 si tiene l'albero completo; aumentando α si tagliano via via i rami il cui contributo non giustifica la complessità, e si ottiene una sequenza annidata di alberi sempre più piccoli. Scikit-learn ne calcola la sequenza esatta: i valori critici di α in cui l'albero cambia. Poi si sceglie α con la validazione incrociata.

from sklearn.model_selection import cross_val_score

path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(Xbt, ybt)         # sul training di Breast Cancer
alphas = path.ccp_alphas
print("valori critici di alfa: %d, dal più piccolo %.5f al più grande %.4f" % (len(alphas), alphas[0], alphas[-1]))

print("alfa        foglie   acc. training   acc. CV (5 gruppi)   acc. test")
for alpha in sorted(set(np.round(np.quantile(alphas, [0, 0.5, 0.8, 0.9, 0.95, 0.98]), 5))):
    tree = DecisionTreeClassifier(random_state=0, ccp_alpha=alpha).fit(Xbt, ybt)
    cv = cross_val_score(DecisionTreeClassifier(random_state=0, ccp_alpha=alpha), Xbt, ybt, cv=5).mean()
    print("%-10g  %5d   %12.3f           %14.3f           %9.3f" % (alpha, tree.get_n_leaves(), tree.score(Xbt, ybt), cv, tree.score(Xbe, ybe)))

valori critici di alfa: 12, dal più piccolo 0.00000 al più grande 0.3435
alfa        foglie   acc. training   acc. CV (5 gruppi)   acc. test
0              16          1.000                    0.925               0.906
0.00686         7          0.982                    0.937               0.918
0.02461         4          0.962                    0.930               0.901
0.02648         3          0.932                    0.930               0.889
0.1692          2          0.932                    0.905               0.889
0.2738          2          0.932                    0.905               0.889

Cosa fa il codice. cost_complexity_pruning_path restituisce i 12 valori critici di α per l'albero completo del training di Breast Cancer; per sei di essi si addestra l'albero potato e si riporta il numero di foglie, l'accuratezza su training, la media della validazione incrociata a 5 gruppi (calcolata sul solo training) e l'accuratezza sul test. Con α = 0 l'albero ha 16 foglie, accuratezza di training 1,000 (memorizza), validazione 0,925 e test 0,906. Con α = 0,00686 le foglie scendono a 7, il training a 0,982 e la validazione sale al massimo, 0,937: il test arriva a 0,918. Potando ancora, a 4 e 3 foglie la validazione cala a 0,930 e a 2 foglie, il «ceppo», a 0,905.

Si legge la lezione classica: la complessità giusta sta nel mezzo (qui 7 foglie), la scelta si fa sulla validazione incrociata e non sul training (che cresce sempre con la complessità) e il test conferma la direzione (0,906 → 0,918; con 171 esempi di test una differenza di 0,012 sono due esempi, quindi è un'indicazione e non una prova). La potatura è un modo principiato di trovare la profondità giusta: un solo parametro continuo α invece di combinare profondità massima, foglie minime e campioni minimi per divisione.

Importanza delle feature: due misure a confronto

Un albero fornisce feature_importances_: la riduzione totale di impurità portata da ciascuna feature, normalizzata. È veloce ma è calcolata sul training, ed è influenzata dalla struttura dell'albero. L'alternativa è la permutation importance (che ritrovi in Random Forest): si mescola una colonna del test e si misura il calo di accuratezza. Le due misure rispondono a domande diverse: la prima «quanto ha usato l'albero questa feature per costruirsi?», la seconda «quanto serve questa feature per prevedere bene dati nuovi?».

from sklearn.inspection import permutation_importance

shallow = DecisionTreeClassifier(random_state=0, max_depth=4).fit(Xbt, ybt)
impurity = shallow.feature_importances_
permutation = permutation_importance(shallow, Xbe, ybe, n_repeats=20, random_state=0).importances_mean
names = load_breast_cancer().feature_names

print("feature                     importanza da impurità   importanza per permutazione (test)")
for j in np.argsort(-impurity)[:4]:
    print("%-26s   %14.3f           %20.3f" % (names[j], impurity[j], permutation[j]))
print("\nle quattro feature con la maggiore importanza per permutazione:")
for j in np.argsort(-permutation)[:4]:
    print("%-26s   %14.3f           %20.3f" % (names[j], impurity[j], permutation[j]))

feature                     importanza da impurità   importanza per permutazione (test)
worst perimeter                       0.816                          0.173
mean texture                          0.057                         -0.003
worst concave points                  0.043                          0.118
mean concave points                   0.020                         -0.006

le quattro feature con la maggiore importanza per permutazione:
worst perimeter                       0.816                          0.173
worst concave points                  0.043                          0.118
area error                            0.011                          0.110
worst compactness                     0.011                          0.041

Cosa fa il codice. Addestra un albero di profondità 4 e confronta le due importanze. Per l'impurità, worst perimeter domina con 0,816: l'albero ha costruito gran parte della sua riduzione di impurità sulla radice. Per permutazione la stessa feature pesa 0,173, cioè mescolarla fa perdere 17 punti di accuratezza sul test: è la feature più importante anche con questa misura, ma il valore assoluto è molto diverso (0,816 e 0,173 sono su scale diverse e non vanno confrontati direttamente).

Il confronto istruttivo è sulle altre: mean texture ha importanza da impurità 0,057 (seconda in graduatoria) ma importanza per permutazione −0,003, ossia mescolarla non cambia l'accuratezza di test: l'albero l'ha usata per adattarsi al training ma non serve per generalizzare. Viceversa area error compare tra le prime quattro per permutazione (0,110) senza essere nelle prime per impurità. È lo stesso avvertimento visto con le colonne di rumore: l'importanza da impurità misura l'uso che l'albero ha fatto della feature, non la sua utilità. Per dire quali feature contano davvero per la previsione serve la permutazione, calcolata su dati non usati per l'addestramento, e con feature correlate va letta con cautela (l'importanza si spartisce tra le feature «gemelle»).

Le variabili categoriche: codifica ordinale o one-hot?

Un albero lavora con soglie numeriche, quindi una variabile categorica va tradotta in numeri. Due scelte. La codifica ordinale assegna un intero a ciascuna categoria (rosso = 0, verde = 1...): una sola colonna, ma impone un ordine che non esiste. La codifica one-hot crea una colonna 0/1 per ciascuna categoria: più colonne, nessun ordine inventato. Per un albero la differenza si vede nel numero di domande necessarie. Costruiamo un caso in cui 12 categorie sono associate a una classe in modo arbitrario (5 categorie «positive», sparse a caso tra i codici) e misuriamo l'accuratezza con la validazione incrociata, al variare della profondità.

r = np.random.default_rng(1)
n = 2000
category = r.integers(0, 12, n)
positive = np.array([0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0])             # quali codici appartengono alla classe positiva (arbitrario)
y_cat = (positive[category] ^ (r.random(n) < 0.05)).astype(int)       # 5% di etichette scambiate

encodings = {"ordinale (1 colonna)": category[:, None].astype(float), "one-hot (12 colonne)": np.eye(12)[category]}
print("codifica                  profondità   foglie   accuratezza CV (5 gruppi)")
for name, features in encodings.items():
    for depth in (2, 4, None):
        tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
        accuracy = cross_val_score(tree, features, y_cat, cv=5).mean()
        print("%-25s  %-10s  %6d   %.3f" % (name, depth, tree.fit(features, y_cat).get_n_leaves(), accuracy))

codifica                  profondità   foglie   accuratezza CV (5 gruppi)
ordinale (1 colonna)       2                4   0.719
ordinale (1 colonna)       4                6   0.791
ordinale (1 colonna)       None            12   0.944
one-hot (12 colonne)       2                3   0.799
one-hot (12 colonne)       4                5   0.944
one-hot (12 colonne)       None            12   0.944

Cosa fa il codice. Genera 2 000 esempi con una variabile categorica a 12 valori e un'etichetta che dipende dalla categoria in modo irregolare (con il 5% di rumore), e addestra alberi con le due codifiche. Con la codifica ordinale e profondità 2 l'accuratezza è 0,719, con profondità 4 sale a 0,791 e solo senza limite (12 foglie, una per ciascun codice) raggiunge 0,944. Con one-hot bastano profondità 4 e 5 foglie per arrivare allo stesso 0,944, e già a profondità 2 si ottiene 0,799, più che l'ordinale a profondità 4.

Perché? L'albero con la codifica ordinale può solo dividere in «codici minori di s» e «maggiori di s»: per isolare un insieme sparso di codici (0, 2, 3, 5, 6, 8, 10, 11 contro 1, 4, 7, 9) servono molte soglie consecutive, quindi molti livelli, e in dati reali questo si traduce in molti più esempi necessari e in rischio di overfitting. Con one-hot ogni domanda è «è proprio questa categoria?», e cinque domande isolano le cinque categorie positive. La regola pratica: per categorie senza ordine naturale usa one-hot (o un algoritmo che gestisce le categorie nativamente, come LightGBM o HistGradientBoosting); l'ordinale ha senso solo quando l'ordine c'è davvero (taglie, livelli). Con molte categorie (centinaia), l'one-hot esplode il numero di colonne e si ricorre a raggruppamenti, codifica del target (con grande attenzione al leakage) o a modelli con supporto nativo.

Tre prove da fare

Esercizio 1. Per l'albero di regressione, aggiungi min_samples_leaf=10 e confronta l'errore rispetto alla funzione vera con quello dell'albero senza limiti: quanto vale, come regolarizzatore, un vincolo sulle foglie? Esercizio 2. Nella potatura, prova a scegliere α con GridSearchCV sui 12 valori critici: l'α scelto coincide con quello che hai individuato a mano? Esercizio 3. Ripeti l'esperimento delle categorie con 60 categorie e un training di 300 esempi: la differenza tra codifica ordinale e one-hot cresce o cala?

Per allenarti sul triage dei ticket di assistenza c'è uno scheletro di esercizi in Python con tre parti da completare: Gini ed entropia con il caso 0·log 0, il guadagno pesato sul caso in cui i due criteri scelgono radici diverse, e il rapporto di guadagno che smonta la colonna identificatore. Finché i punti da completare sono vuoti, stampa quali esercizi mancano.

Che cosa sai fare adesso

Sai calcolare a mano Gini, entropia e guadagno di una divisione, sai scrivere la ricerca golosa che costruisce un albero e sai riconoscere quando due criteri legittimi scelgono radici diverse. Sai scegliere la complessità con la potatura e la validazione incrociata, sai leggere un'importanza per impurità con sospetto e sai perché un singolo albero cambia con i dati. In Random Forest combiniamo molti alberi instabili per ottenere un modello stabile.

Fonti

Lezione precedente del percorso: KNN: classificare guardando i vicini (e la maledizione della dimensionalità). Nella stessa serie rimandano a questa lezione anche: Entropia, entropia incrociata e divergenza KL: perché le funzioni di costo sono tutte la stessa cosa, Il processo di un progetto di ML: split, data leakage e metriche che mentono, Boosting: AdaBoost, Gradient Boosting e cenni su XGBoost.