Please enable JavaScript.
Coggle requires JavaScript to display documents.
Decision Tree - Coggle Diagram
Decision
Tree
Induzione
Decision Tree
CART
ID3, C4.5
Hunt's Algorithm
Se Dt contiene record che appartengono alla stessa classe y_t,
t è un nodo foglia etichettato y_t
se Dt è vuoto
t nodo foglia etichettato come l'etichetta della classe maggioritaria dei record nei nodi parenti
Dt contiene record che appartengono a più di una classe
usi un attribute test per dividere i dati in subset minori
SLIQ, SPRINT
Errori di Classificazione
Training errors
errori di classificazione
sul training set
Generalization errors
errori commessi
sul test set
Stima
approccio ottimistico
gen err = train error
approccio pessimistico
gen err = train error + penalty
utilizzare validation set
Underfitting
modello troppo semplice
Overfitting
si adatta troppo bene al train,
facendo male nel test
Come affrontarlo?
Pre Pruning
stoppa lo splitting prima di raggiungere un albero di profondità massima
un nodo può non essere
ulteriormente splittato se:
tutte le istanze appartengono alla stessa classe
tutti gli attributi hanno lo stesso valore
il nodo non contiene istanze
condizioni
più restrittive sono:
stoppare split se la distribuzione di istanze tra le classi è indipendente dai valori degli attributi
stoppare split se non migliora le misure di purezza
stoppare lo split se il numero di istanze nel nodo è minore di un valore fissato
Post Pruning
eseguire tutti gli split possibili
eliminare un sottoalbero se riduce
generalization error
scegli di eliminare sottoalberi che determinano
massima riduzione errore
costo computazionale
più alto
Stopping Criteria
stoppi l'espansione di un nodo
quando tutti i record appartengono
alla stessa classe
stoppi l'espansione di un nodo
quando tutti i record hanno
attributi con valori simili
la classificazione può
essere insignificante e dipendente
in piccole fluttuazioni di valore
risoluzione anticipata:
stoppa lo split quando il numero
di record è minore di un certo limite
la classificazione può non
essere statisticamente rilevante
Metodi di stima
della performance
Holdout
Random subsampling
Holdout n volte
Cross Validation
classificazione
trovare un modello per la classe
come funzione di altri attributi
tecniche
alberi di decisione
Rule-based methods
Nearest- Neighbor
Naive Bayes
Neural Network
Support Vector Machines
Come splittare
i record
Specificare Condizioni di Test
dipende dal
tipo di attributi
Nominali
Ordinali
Continui
Discretizzazione per formare attributi ordinali categorici
Decisione Binaria
dipende dal n° di modi
per splittare
2 way
Multi way
Determinare il Best Split
nodi con distribuzione omogenea di classi sono preferite
necessità misura di impurità del nodo
Entropia
(ID3,C4.5)
Entropy(t)= - sum(p(i|t)log2p(i|t)
Errore di Misclassificazione
C_error(t)=1-max(p(i|t))
Indice di Gini
(CART, SLIQ, SPRINT)
gini(t)=1-sum(p(i|t)^2
e con attributi continui?
-ordina per valore
-scansiona linearmente i valori,
updatando la count matrix
-scegli la split position con l'indice di Gini minore
Misura impurità split
Impurity_split= sum Nt/N measure(t)
Gain_split=measure(parent) -sum Nt/N measure(t)
GainRATIO= Gain_split/SplitInfo
SplitInfo=-sum Nt/N log2 Nt/N
Metriche di
valutazione performance
Matrice di Confusione
solita con TP TF FP FN
Accuracy= (TP+TN)/(ALL)
Error Rate= (FP+FN)/(ALL)
Precision= (TP)/(TP+FP)
Recall= (TP)/(TP+FN)
Matrice di Costo
C(i|j)= costo di classificare j as i