L'algoritmo CART (Classification And Regression Trees) è una variante degli algoritmi per l'apprendimento automatico di alberi di decisione. Esso è in grado di costruire alberi sia per la classificazione che per la regressione. È un algoritmo di apprendimento supervisionato che apprende da istanze etichettate (del training set) un albero di decisione da usare in seguito per predire le etichette della variabile target per nuove istanze.

CART presenta le seguenti caratteristiche costruisce un albero composto da nodi e rami. I nodi interni rappresentano diversi punti di decisione, mentre i rami rappresentano i possibili esiti di tali decisioni. I nodi-foglia dell'albero contengono l'output da predire per la variabile target, ossia un'etichetta di classe o un valore reale. CART utilizza un approccio greedy per partizionare i dati in ciascun nodo. Valuta tutte le possibili suddivisioni e seleziona quella che riduce maggiormente la misura di impurità dei sottoinsiemi risultanti. Per alberi per la classificazione, CART utilizza l'impurità di Gini come criterio di divisione. Più bassa è l'impurità, più puro è il sottoinsieme. Nei problemi di regressione, CART utilizza la riduzione residua come criterio di divisione. Più bassa è la riduzione residua, migliore è l'adattamento del modello ai dati. per evitare il sovradattamento dei dati, la potatura (pruning) serve a rimuovere i sottoalberi che contribuiscono in misura minima all'accuratezza del modello. Fra le tecniche più diffuse rientrano la potatura in base al costo computazionale e la potatura in base al guadagno informativo (information gain).

Costruzione del modello L'idea di base della costruzione dell'albero di decisione è quella di scegliere per in ciascun nodo (interno) un partizionamento delle istanze tra tutti i possibili in modo che i nodi figli risultanti siano i più “puri”. Nell'algoritmo vengono prese in considerazione solo suddivisioni univariate. Ciò significa che ogni partizionamento dipende dal valore di una sola variabile predittiva. Si considerano, quindi, tutte le suddivisioni possibili per ciascun predittore. Se è una variabile categorica nominale di categorie, ci saranno possibili divisioni per questo predittore. Se è una variabile categorica ordinale o continua con K valori diversi, ci saranno divisioni diverse su .

L'albero viene costruito a partire dal nodo radice utilizzando ripetutamente i seguenti passaggi su ciascun nodo:

Trovare la suddivisione migliore per ciascun predittore. Per ciascun predittore continuo e ordinale, ordinare i valori dal più piccolo al più grande. Si esaminano i valori ordinati per valutare ciascun punto di partizionamento candidato per determinare la migliore condizione di split: dato un valore , se , l'istanza va al nodo figlio sinistro, altrimenti va a quello destro. Il punto di split migliore è quello che massimizza il criterio adottato. Per ogni predittore nominale, esaminare ogni possibile sottoinsieme di valori per trovare il miglior partizionamento: dato il sottoinsieme , se , l'istanza va al figlio sinistro, altrimenti va a quello destro. Trovare la migliore divisione del nodo: Tra le migliori suddivisioni trovate al passo 1, scegliere quella che massimizza il criterio di split. Se le condizioni di fine-crescita non sono soddisfatte, partizionare le istanze del nodo utilizzando la migliore condizione di split trovata al passo 2 altrimenti il nodo sarà una foglia contenente la moda dei valori delle etichette delle sue istanze (classe di maggioranza) ovvero la media dei valori delle etichette (regressione)

Pseudocodice Input: dataset D con feature X e variabile target y (categorica) Output: albero di classificazione

Funzione CART_classificazione(D) Se tutte le istanze in D appartengono alla stessa classe o criteri di stop raggiunti: Creare un nodo-foglia con la classe dominante in D Ritornare nodo foglia Altrimenti: Per ogni variabile e per ogni suo possibile valore di split: Dividere D in due sottoinsiemi D1, D0 in base allo split Calcolare l'impurità (es. Gini) per il partizionamento Seleziona variabile e split che minimizzano l'impurità Creare nodo interno con test sulla variabile e split scelti con albero_0 = CART_classificazione(D0) con albero_1 = CART_classificazione(D1) Restituire nodo internoInput: Dataset D con feature X e variabile target continua Y Output: Albero di regressione

Funzione CART_regressione(D): Se la varianza di Y in D è inferiore rispetto a una soglia o D è troppo piccolo: Restituire un nodo foglia con il valore medio di Y in D Altrimenti: Per ogni feature x_i in X: Per ogni possibile punto di split s di x_i: Dividere D in D_1 e D_0 secondo x_i <= s Calcolare la varianza pesata sommata di Y in D_1 e D_0 Selezionare x* e s* che minimizzano la varianza pesata Creare un nodo decisionale che partiziona su x* al valore s* albero_1 = CART_regressione(D_1) albero_0 = CART_regressione(D_0) Restiture il nodo con albero_1 e albero_0

Criteri di partizionamento Sia il training set di istanze etichettate.

Al nodo , la condizione migliore per il partizionamento si sceglie massimizzando un criterio di partizionamento . Potendo definire una funzione di impurità per il nodo, il criterio equivale al decremento di impurità dovuto alla partizionamento.

Classificazione Se la variabile target è categorica, si può usare lindice di Gini o l'entropia (o il Twoing, anche nella sua variante ordinata).

Per il nodo e la classe , le probabilità , , possono essere stimate come segue:

probabilità di avere un'istanza di classe nel nodo ; , con peso dell'istanza e peso della frequenza di rispetto a tutto ; , conteggio analogo ma limitato a , istanze del nodo ; , probabilità a priori; , probabilità condizionata.

La misura di impurità di Gini si può scrivere, dato il costo dell'errore di misclassificazione :

e il criterio basato su tale indice è il decremento di impurità:

dove e sono le probabilità di istradare le istanze verso il sottoalbero per cui la condizione è vera () o falsa (), rispettivamente. Esse sono facilmente stimabili con .

Regressione Quando la variabile target è continua, il criterio di partizionamento usato è

dove, dato l'insieme degli esempi al nodo t:

con le misure di impurità LSD (Least Squares Deviation)

dove: .

Condizioni di fine-crescita Controllano se il processo di sviluppo dell'albero debba terminare o meno. Fra le condizioni più usate:

Se il nodo è puro, ossia quando tutti le istanze hanno lo stesso valore per la variabile target , il nodo non sarà partizionato. Se tutte le istanze nel nodo hanno valori identici per ogni variabile predittiva , il nodo non sarà partizionato. Se la profondità corrente dell'albero ha raggiunto una soglia massima fissata dall'utente il processo può essere terminato. Se il numero di esempi presso un nodo è inferiore rispetto a una soglia fissata dall'utente, il nodo non sarà partizionato. Se il partizionamento di un nodo porta a un nodo-figlio inferiore a una soglia fissata dall'utente, il nodo non sarà partizionato.

Note

Voci correlate Indice di eterogeneità di Gini Twoing

Categoria:Apprendimento automatico