Lezione 16Alberi di decisione e random forest

Settimana: 6 · Fonte: slide del corso Machine Learning, Ingegneria dell'Automazione UniPD (lezione 16)

Argomenti trattati

1. Albero di decisione: regole su una variabile alla volta, nodi e foglie.
2. Entropia e guadagno d'informazione (ID3), indice di Gini e soglie sulle variabili numeriche (CART), alberi di regressione.
3. Overfitting e potatura (cost-complexity), vantaggi e svantaggi.
4. Dal singolo albero alla foresta: varianza alta di un albero e idea del bagging.
5. Approfondimento: non nel programma di Telecomunicazioni.

Teoria

• 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 →

Esercizi

• Esercizio - Albero di decisione ID3 sul dataset del tennis
• Esercizio - Albero di decisione con criteri di impurità e potatura sul dataset iris

Lezione precedente: Lezione 15 · Laboratorio kNN e regressione logistica Lezione successiva: Lezione 17 · Metodi ensemble basati su alberi