DECISION TREE Flashcards
Cos’è un decision tree?
Sono dei modelli di ML per task di classificazione, regressione. Ha la struttura di un albero, dove i nodi hanno diversi attributi:
- Samples: numero di istanze che appartengono a quel nodo
- Value: i valori delle istanze
- Gini: misura di impurità, quanto è buono lo split, se 0 vuol dire che le istanze appartengono ad una sola classe, obiettivo è minimizzare questo valore
Per predire un risultato, si parte dalla radice e ci si muove in basso fino ad arrivare ad un nodo foglia in base ai predicati dei nodi. Nel caso in cui nel nodo foglia ci sono più classi, la classificazione fa fede alla classe con la probabilità più alta.
L’obiettivo è di suddividere iterativamente il dataset in subset omogenei, in base alle caratteristiche dei dati.
L’idea per la costruzione di un albero di decisione è quella di scegliere ricorsivamente l’attributo più significativo come radice del sottoalbero al passo k. (split)
Uno split è ottimale quando si isolano al meglio tutti i casi positivi oppure tutti i casi negativi rispetto al predicato.
Un’altra misura di impurità è l’entropia, l’obiettivo è di minimizzare questo valore.
Algoritmo CART
Per la creazione di un albero di decisione, inizialmente splitta il training set in due subset usando una feature k e una soglia t(k). Seleziona questa coppia tra tutte le possibili coppie cercando di minimizzare la funzione di costo che misura l’impurità del sottoalbero sinistro e destro. L’algoritmo si ferma quando raggiunge il valore del parametro max_depth oppure quando non riesce a ridurre l’impurità.
Il problema di trovare un albero ottimale è NP-COMPLETO perché l’algoritmo deve cercare una partizione ottimale tra tutte le possibili partizioni, il numero di possibili alberi cresce esponenzialmente con la dimensione del dataset e il numero di variabili. O(e^m)
Complessità decision tree
Generalmente un albero di decisione è bilanciato, quindi attraversarlo costa O(log m).
Però l’algortimo di training compara tutte le features su tutti gli esempi per ogni nodo, quindi costa O(n * log m).
IPERPARAMETRI
L’albero può incorrere nell’overfitting, per evitare questo si regolarizza il parametro max_depth(profondità dell’albero). Più un albero è profondo più è complesso.
Decision tree regression
Il valore che predice un albero di decisione quando fa regressione è la media degli elementi presenti nella foglia. In questo caso l’algoritmo CART minimizza MSE. Anche in questo caso si regolarizza il parametro min_samples_leaf per evitare l’overfitting.
Problemi nei decision tree
Hanno delle limitazioni:
sono sensibili alle variazioni del dataset, questo problema viene limitato con le RANDOM FOREST che effettuano una media sui risultati si singoli alberi di decisione.
