Alberi di decisione Flashcards
Cos’è un Decision Tree?
Un decision tree, o albero decisionale, è un modello di apprendimento automatico supervisionato utilizzato per la classificazione e la regressione. È una rappresentazione strutturata a forma di albero di decisioni logiche che vengono prese in base alle caratteristiche o attributi dei dati di input.
Ogni nodo è caratterizzato da diversi attributi:
* Samples: il numero di istanze che appartengono a quel nodo;
* Value: i valori delle istanze presenti nel nodo;
* Gini: una misura di impurità, se 0 indica che tutte le istanze appartengono alla stessa classe
FORMULA GINI
L’obiettivo principale di un decision tree è quello di creare una serie di regole decisionali che possano classificare o predire correttamente le istanze di input. Durante la fase di addestramento, il decision tree viene costruito in modo ricorsivo suddividendo il set di addestramento in base alle caratteristiche migliori per discriminare tra le classi o per ridurre l’errore nella regressione. Questo processo di suddivisione continua fino a quando una condizione di arresto viene soddisfatta, ad esempio quando tutte le istanze appartengono alla stessa classe o quando viene raggiunta una profondità massima predefinita dell’albero
Cos’è l’indice di Gini?
L’indice di Gini è una misura utilizzata nell’ambito dei decision tree e di altri modelli di classificazione per valutare l’impurità dei dati e la qualità delle divisioni degli attributi. Viene comunemente utilizzato come criterio di suddivisione per determinare quali attributi siano i migliori per separare le classi nel processo di costruzione del decision tree.
L’indice di Gini misura la probabilità che due istanze casualmente selezionate da un set di dati siano etichettate in modo diverso. Un indice di Gini pari a 0 indica che tutte le istanze nel nodo appartengono alla stessa classe, mentre un indice di Gini pari a 1 indica che le istanze sono uniformemente distribuite tra le diverse classi.
L’indice di Gini per un nodo di un decision tree può essere calcolato utilizzando la seguente formula:
Gini = 1 - (sum(pi^2))
Dove:
𝑝𝑖, 𝑘 è il rapporto delle istanze della classe K tra le istanze di addestramento nel nodo di indice i.
Un altro modo di misurare tramite indice Gini uno split è dato dalla seguente formula:
gini split(T)=(n1/n)gini(T1)+(n2/n)gini(T2)
Cos’è l’entropia?
L’entropia è una misura utilizzata nell’ambito dei decision tree e di altri modelli di classificazione per valutare l’impurità dei dati e la qualità delle divisioni degli attributi. Viene comunemente utilizzata come criterio di suddivisione per determinare quali attributi siano i migliori per separare le classi nel processo di costruzione del decision tree.
L’entropia misura l’incertezza o l’impurità di un set di dati rispetto alla distribuzione delle classi. Più l’entropia è alta, maggiore è l’incertezza e l’eterogeneità delle classi presenti nel set di dati.
L’entropia per un nodo di un decision tree può essere calcolata utilizzando la seguente formula:
Entropy = - (sum(pi * log2(pi)))
Dove:
pi rappresenta la proporzione delle istanze del nodo che appartengono alla classe i. La somma viene effettuata su tutte le classi presenti nel nodo.
Come possono essere gli split? (DECISION TREE)
no split può essere:
* Binario;
* Multiplo
Per gli attributi numerici:
* Binary split: A <= v, A > v
* Multiple split: A <= v1, v1 < A <= v2, …, vn 1 < A <= vn
Per gli attributi categorici:
* Binary split: A ∈ S’, A ∈ S - S’
* Multiple split: A ∈ S1, …, A ∈ Sn
Limiti degli alberi di decisione
Gli alberi di decisione hanno delle limitazioni:
* Amano i confini decisionali ortogonali e sono sensibili alle rotazioni nel training set;
* Il problema principale è che sono molto sensibili a piccole variazione nel training set
Questi problema vengono limitati con le Random Forest che effettuano una media sui risultati di singoli alberi di decisione.
Complessità albero decisionale
Fare previsioni con un albero decisionale richiede di attraversare l’albero partendo dalla radice fino a raggiungere una foglia. Gli alberi decisionali sono generalmente approssimativamente bilanciati, quindi attraversare l’albero decisionale richiede di passare attraverso circa 𝑂(log2(𝑚)) nodi, dove 𝑚 è il numero totale di nodi dell’albero.
Poiché ogni nodo richiede solo di verificare il valore di una caratteristica, la complessità complessiva delle previsioni è semplicemente 𝑂(log2(𝑚)), indipendentemente dal numero di caratteristiche presenti.
Tuttavia, l’algoritmo di addestramento confronta tutte le caratteristiche (o meno se è impostato un limite tramite max_features) su tutti i campioni in ogni nodo. Ciò porta a una complessità di addestramento di 𝑂(𝑛 × 𝑚 log(𝑚)), dove 𝑛 è il numero totale di campioni nel set di addestramento e 𝑚 è il numero di nodi dell’albero
CART
CART, che sta per “Classification and Regression Trees”, è un algoritmo di apprendimento automatico utilizzato per costruire alberi decisionali che possono essere impiegati sia per la classificazione che per la regressione. L’algoritmo CART è stato sviluppato da Leo Breiman e il suo gruppo alla University of California, Berkeley.
Ecco una panoramica di come funziona l’algoritmo CART:
Selezione della divisione migliore: L'algoritmo inizia dividendo il set di dati iniziale in base a una caratteristica (variabile) che massimizza la riduzione dell'indice di Gini (nel caso della classificazione) o la riduzione della somma dei quadrati degli errori (nel caso della regressione). Questo passaggio cerca di creare divisioni che massimizzino la purezza all'interno dei nodi. Creazione dei nodi figli: Una volta selezionata la caratteristica di divisione ottimale, il set di dati viene suddiviso in due sottoinsiemi in base ai valori della caratteristica scelta. Questo processo viene quindi ripetuto per ciascun sottoinsieme, creando ulteriori suddivisioni dell'albero. Ricorsione: Il processo di suddivisione e creazione dei nodi figli viene ripetuto in modo ricorsivo per ciascun nuovo nodo creato, finché non si raggiunge una condizione di terminazione. Questa condizione potrebbe essere una profondità massima dell'albero, un numero minimo di osservazioni in un nodo o altri criteri definiti. Pruning (potatura): Una volta che l'albero è stato costruito, è possibile eseguire un processo di potatura per semplificarlo e prevenire l'overfitting. La potatura coinvolge la rimozione di rami dell'albero che non contribuiscono in modo significativo alle prestazioni generali su dati non visti. Classificazione o regressione: Dopo la costruzione dell'albero, può essere utilizzato per la classificazione (assegnando classi alle istanze) o per la regressione (stimando valori continui) a seconda dell'obiettivo dell'analisi.
np-completo
