Esercizio - ID3 con potatura e foresta casuale sul dataset Titanic

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

Testo (simulazione d'esame, esercizi 1-4). Sul dataset Titanic (712 passeggeri senza valori mancanti dopo aver tolto Cabin, PassengerId, Name, Ticket; target Survived; feature Pclass, Sex, Age, SibSp, Parch, Fare, Embarked):

1. implementare un albero ID3 (divisione su tutti i valori della feature, ogni feature usata una volta per ramo) con entropia o guadagno d'informazione, e descrivere come trattare le feature continue;
2. esplorare il dataset, pre-elaborarlo e dividerlo $80\%/20\%$ in modo adeguato; valutare l'albero;
3. aggiungere la profondità massima e la potatura a costo-complessità; valutare;
4. implementare una foresta casuale con bootstrap aggregating e con feature bagging ($\sqrt{p'}$ feature tra quelle ancora disponibili) e studiare l'effetto del numero di alberi.

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 → (ID3, entropia, potatura); 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 → (bagging, feature bagging); 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 → (accuracy); la stratificazione è in Regressione logistica e softmaxLa regressione lineare non è adatta alla classificazione (valori fuori da [0,1], retta tirata dai punti lontani). La regressione logistica passa il predittore lineare dalla sigmoide $\sigma(z)=1/(1+e^{-z})$ e interpreta $\hat y=\sigma(x^T\beta)$ come $P(y=1\mid x)$: si predice la classe 1 se $\hat y\ge0{,}5$, cioè $x^T\beta\ge0$ (bordo lineare). L'errore quadratico dà una funzione non convessa; si usa la log-verosimiglianza negativa $-\sum[y\log\hat y+(1-y)\log(1-\hat y)]$, convessa, con gradiente $X^T(\hat y-y)$ e nessuna formula chiusa (discesa del gradiente). Per più classi: one-vs-one ($C(C-1)/2$ classificatori, voto), one-vs-all ($C$ classificatori, massima probabilità), o la softmax $p_c=e^{z_c}/\sum_ke^{z_k}$ con cross-entropia. Si può regolarizzare (ridge, LASSO, Elastic Net) e la cross-validation si fa stratificata. Approfondimento: non nel programma di Telecomunicazioni.Regressione logistica e softmax →.

2. Preparazione dei dati

• Feature irrilevanti: PassengerId, Name, Ticket sono identificativi (nessun potere predittivo, rischio di overfitting); Cabin ha moltissimi valori mancanti.
• Valori mancanti: Age ($177$ mancanti) ed Embarked ($2$) $\to$ si eliminano le righe: restano $712$ campioni.
• Target sbilanciato ($424$ morti, $288$ sopravvissuti, circa $40\%$ di positivi): conviene la divisione stratificata, che mantiene la proporzione in training e test; con questa divisione: training $569$, test $143$.
• Tipi di feature: Pclass, Sex, SibSp, Parch, Embarked sono categoriche (anche se SibSp e Parch sono interi con pochi valori), Age e Fare continue.

1. L'albero ID3

Algoritmo ricorsivo con foglie quando: (1) nessun campione nel nodo $\to$ si predice la classe maggioritaria del genitore; (2) tutti i campioni hanno la stessa classe; (3) nessuna feature rimasta con classi miste $\to$ maggioranza; (4, opzionale) profondità massima raggiunta. Si sceglie la feature con guadagno massimo (o entropia di split minima), e si genera un figlio per ogni suo valore; un valore mai visto in addestramento viene mandato alla predizione del nodo corrente.

Feature continue (Age, Fare). Tre strategie:

1. Soglia binaria come in CART: si sceglie la $t$ che massimizza il guadagno e si divide in $x\le t$ e $x>t$ (si implementa dentro la classe);
2. Quantizzazione: si divide l'intervallo in intervalli di uguale ampiezza (per esempio 10) e li si tratta come categorie (pre-elaborazione);
3. Split multiplo sui punti medi tra valori consecutivi (un figlio per intervallo).

La prima è la più promettente: sfrutta la soglia ottima, mantiene l'albero piccolo e non perde informazione per un'arbitraria discretizzazione.

Entropia e guadagno scelgono la stessa feature: i due criteri danno risultati identici (training $0{,}861$, test $0{,}825$, 146 nodi), perché a ogni nodo la scelta di massimo $IG=H(\text{nodo})-H_{\text{split}}$ equivale a quella di minimo $H_{\text{split}}$.

3. Profondità massima e potatura

(Il training sale sempre; il test ha un massimo a profondità 3: oltre, overfitting. Con una divisione di soli 143 campioni la curva del test è rumorosa: va letta come tendenza.) La quantizzazione di Age e Fare in 10 intervalli e il trattamento di tutte le feature come categoriche dà training $0{,}879$ e test $0{,}790$: peggio della soglia (si perde informazione e si hanno più rami).

Potatura a costo-complessità con un insieme di validazione: ripetuta 10 volte (training diviso $80\%/20\%$, albero completo, 12 potature ciascuna del nodo con $\alpha_{\text{eff}}$ minimo, calcolato sul validation set): accuracy di test media $0{,}817\to0{,}834$ (deviazione standard $0{,}02$), accuracy di training $0{,}869\to0{,}853$. La potatura riduce l'adattamento al training e migliora un po' la generalizzazione. Nell'ID3 con più figli per nodo la formula si adatta: $\alpha_{\text{eff}}(t)=\frac{R(t)-R(T_t)}{\#\text{foglie}(T_t)}$ (non $-1$ al denominatore, perché con un solo figlio il sottoalbero potrebbe avere una sola foglia e il rapporto sarebbe indefinito: in questi casi il valore è «non definito» e il nodo viene saltato).

4. Foresta casuale

Bagging. Per ogni albero un campione bootstrap ($n$ estrazioni con rimpiazzo); previsione per voto di maggioranza. Con np.random.seed(0): $1$ albero su un bootstrap: test $0{,}797$; $10$ alberi: $0{,}811$.

Feature bagging per ID3. A ogni split, tra le $p'$ feature ancora disponibili nel ramo (non usate) se ne campionano $\lfloor\sqrt{p'}\rfloor$ a caso senza rimpiazzo e si sceglie la migliore tra queste (per $p=7$: $\lfloor\sqrt7\rfloor=2$ feature al primo split, poi sempre meno).

Effetto della dimensione della foresta (una sola prova, accuracy sul test): $T=2$: $0{,}804$; $4$: $0{,}818$; $8$: $0{,}825$; $16$: $0{,}811$; $32$: $0{,}818$. L'accuracy cresce poco e si stabilizza oltre una decina di alberi: più alberi riducono la varianza (media di modelli poco correlati) ma l'accuracy non può crescere indefinitamente; la variabilità tra una prova e l'altra è di circa $\pm1$-$2$ punti (per questo il notebook ripete 5 prove e mostra media e deviazione standard). Con $T=100$ alberi: accuracy $0{,}811$ e $\text{AUC}=0{,}918$ (Esercizio - Curva ROC e AUC di una foresta casuale e di un albero).

Confronto

Qui l'albero singolo di profondità 3 ($0{,}867$) e l'albero completo ($0{,}825$) sono competitivi con la foresta ($0{,}81$-$0{,}83$): su un test di 143 campioni una differenza di 2-6 casi non è significativa, e il dataset (7 feature, 569 campioni) è piccolo. L'AUC mostra però il vantaggio della foresta ($0{,}918$ contro $0{,}865$ dell'albero completo).

Codice (struttura)

def fit_bagging(X, y, T, cat, tree_cls):
    trees = []
    for _ in range(T):
        idx = np.random.choice(len(X), len(X), replace=True)       # bootstrap
        trees.append(tree_cls(InformationGainCriterion).fit(X[idx], y[idx], cat))
    return trees
def predict_bagging(X, trees):
    P = np.array([t.predict(X) for t in trees])                    # (T, n)
    return np.array([np.bincount(P[:, j]).argmax() for j in range(P.shape[1])])   # voto di maggioranza
class FeatureBaggingID3(DecisionTreeID3):
    def _best_split(self, X, y, mask):
        avail = np.where(mask)[0]
        chosen = np.random.choice(avail, max(1, int(np.sqrt(len(avail)))), replace=False)
        # ... scegliere la miglior feature solo tra `chosen`