Esercizio - Balanced random forest (laboratorio di ripasso)

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (laboratorio di ripasso, dataset Wine sbilanciato). Un random forest costruisce molti alberi su campioni bootstrap del training. Con classi sbilanciate l'errore sulla classe rara pesa poco nella loss e il modello tende a ignorarla. Nel balanced random forest per ogni albero si sottocampiona la classe maggioritaria: si conta il numero di campioni della classe minoritaria e, per ogni classe, si estraggono con reinserimento altrettanti campioni.

1. Si implementino balanced_bootstrap_sample, fit_balanced_random_forest e predict_balanced_random_forest (voto di maggioranza con confidenza).
2. Con classi di $100$, $30$ e $10$ campioni, quanti campioni ha ogni campione bootstrap bilanciato? Con quale probabilità un campione specifico di ciascuna classe finisce nel campione bootstrap di un albero?
3. Tre alberi predicono per tre campioni le classi $(0,1,2)$, $(0,1,1)$, $(1,1,2)$ (una riga per albero). Quali sono la predizione finale e la confidenza?
4. Perché l'accuratezza non è la metrica giusta e cosa usare?

Teoria usata: 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 →, 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 →, Metriche di classificazioneIn classificazione binaria ogni previsione è vero positivo (TP), vero negativo (TN), falso positivo (FP, errore di tipo I) o falso negativo (FN, errore di tipo II). Da queste quattro quantità: accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità $=\frac{TN}{TN+FP}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, e la loro media armonica $F_1=\frac{2PR}{P+R}$. Con dati sbilanciati l'accuracy inganna (un modello che predice sempre la classe maggioritaria ha 99%): si usano precision, recall, F1, ROC-AUC, la cross-validation stratificata e il riequilibrio con undersampling o oversampling (non SMOTE). Cambiando la soglia sulla probabilità si ottiene la curva ROC (TPR contro FPR) e l'area AUC. Approfondimento: non nel programma di Telecomunicazioni.Metriche di classificazione →, Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →.

1. Implementazione

import numpy as np
from collections import Counter

def balanced_bootstrap_sample(X, y):
    classi, conteggi = np.unique(y, return_counts=True)
    m = conteggi.min()                                   # numero di campioni della classe rara
    idx = np.concatenate([
        np.random.choice(np.where(y == c)[0], size=m, replace=True)   # con reinserimento
        for c in classi])
    return X[idx], y[idx]

def fit_balanced_random_forest(X, y, T, max_depth):
    trees = []
    for _ in range(T):
        Xb, yb = balanced_bootstrap_sample(X, y)         # un campione bilanciato per albero
        tree = DecisionTree(max_depth=max_depth, min_impurity_improvement=0.0)
        tree.fit(Xb, yb)
        trees.append(tree)
    return trees

def predict_balanced_random_forest(X, trees):
    tree_predictions = np.array([t.predict(X) for t in trees])      # forma (T, n_campioni)
    y_pred, confidences = [], []
    for i in range(tree_predictions.shape[1]):
        votes = Counter(tree_predictions[:, i])           # voti dei T alberi per il campione i
        classe, n = votes.most_common(1)[0]
        y_pred.append(classe)
        confidences.append(n / len(trees))                # frazione di alberi d'accordo
    return np.array(y_pred), np.array(confidences)

Il training e il test si dividono prima in modo stratificato (stessa proporzione di classi in entrambi) e solo il training viene ribilanciato per albero: il test deve restare con la distribuzione reale, altrimenti la valutazione non è onesta.

2. Dimensione del campione e probabilità

La classe minoritaria ha $m=10$ campioni, quindi ogni campione bootstrap bilanciato ha $3\cdot10=30$ campioni (10 per classe).

Un campione specifico di una classe con $N_c$ elementi, in $10$ estrazioni con reinserimento, non viene mai scelto con probabilità $(1-1/N_c)^{10}$ (ogni estrazione lo manca con probabilità $1-1/N_c$ e le estrazioni sono indipendenti), quindi viene incluso con probabilità $1-(1-1/N_c)^{10}$:

• classe da $100$: $1-0{,}99^{10}=0{,}0956$ (il numero atteso di campioni distinti scelti è $100\cdot0{,}0956=9{,}56$, quindi quasi nessun duplicato);
• classe da $30$: $1-(29/30)^{10}=0{,}287$;
• classe da $10$: $1-0{,}9^{10}=0{,}651$ (in media $6{,}5$ campioni distinti su $10$, con duplicati).

La classe rara è quindi usata quasi per intero in ogni albero, mentre ogni albero vede solo circa il $10\%$ della classe maggioritaria: gli alberi sono diversi tra loro (diversità tra i membri dell'ensemble) ed ognuno è addestrato su dati bilanciati.

3. Voto

Alberi in riga, campioni in colonna: $\begin{bmatrix}0&1&2\\0&1&1\\1&1&2\end{bmatrix}$.

• campione $1$: voti $(0,0,1)$: classe $0$ con $2$ voti su $3$, confidenza $2/3=0{,}667$;
• campione $2$: voti $(1,1,1)$: classe $1$, confidenza $1$;
• campione $3$: voti $(2,1,2)$: classe $2$, confidenza $0{,}667$.

Predizioni $(0,1,2)$ con confidenze $(0{,}667;\ 1;\ 0{,}667)$ (verificato con il codice sopra). La confidenza è la frazione di alberi concordi, non una probabilità calibrata; è usata per costruire curve come la ROC variando la soglia sul voto.

4. Metrica

Con classi sbilanciate l'accuratezza è ingannevole: un classificatore che predice sempre la classe maggioritaria (nell'esempio $100/140=71\%$) ha accuratezza alta e recall nullo sulla classe rara. Si usano la matrice di confusione, precision, recall e F1 per classe, o l'AUC (Metriche di classificazioneIn classificazione binaria ogni previsione è vero positivo (TP), vero negativo (TN), falso positivo (FP, errore di tipo I) o falso negativo (FN, errore di tipo II). Da queste quattro quantità: accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità $=\frac{TN}{TN+FP}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, e la loro media armonica $F_1=\frac{2PR}{P+R}$. Con dati sbilanciati l'accuracy inganna (un modello che predice sempre la classe maggioritaria ha 99%): si usano precision, recall, F1, ROC-AUC, la cross-validation stratificata e il riequilibrio con undersampling o oversampling (non SMOTE). Cambiando la soglia sulla probabilità si ottiene la curva ROC (TPR contro FPR) e l'area AUC. Approfondimento: non nel programma di Telecomunicazioni.Metriche di classificazione →). Il bilanciamento per albero tende ad aumentare il recall della classe rara a scapito della precision.