CART (algoritmo)

L'algoritmo CART (Classification And Regression Trees) è una variante degli algoritmi per l'apprendimento automatico di alberi di decisione^[1][2][3]. 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 ${\displaystyle X}$ è una variabile categorica nominale di ${\displaystyle X}$ categorie, ci saranno ${\displaystyle 2^{K-1}-1}$ possibili divisioni per questo predittore. Se ${\displaystyle X}$ è una variabile categorica ordinale o continua con K valori diversi, ci saranno ${\displaystyle K-1}$ divisioni diverse su ${\displaystyle X}$.

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

1. 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 ${\displaystyle v}$, se ${\displaystyle x\leq v}$, 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 ${\displaystyle S}$, se ${\displaystyle x\in S}$, l'istanza va al figlio sinistro, altrimenti va a quello destro.
2. Trovare la migliore divisione del nodo:
   • Tra le migliori suddivisioni trovate al passo 1, scegliere quella che massimizza il criterio di split.
3. 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
            Calcolarw 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 interno

Input: 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 ${\displaystyle {\mathcal {D}}}$ il training set di istanze etichettate.

Al nodo ${\displaystyle t}$, la condizione migliore per il partizionamento ${\displaystyle s}$ si sceglie massimizzando un criterio di partizionamento ${\displaystyle \Delta _{i}(s,t)}$. Potendo definire una funzione di impurità per il nodo, il criterio equivale al decremento di impurità dovuto alla partizionamento.^[4]

Classificazione

Se la variabile target ${\displaystyle Y}$ è categorica, si può usare l'indice di Gini o l'entropia (o il Twoing, anche nella sua variante ordinata).

Per il nodo ${\displaystyle t}$ e la classe ${\displaystyle c}$, le probabilità ${\displaystyle p(c,t)}$, ${\displaystyle p(c|t)}$, ${\displaystyle p(t)}$ possono essere stimate come segue:

• ${\displaystyle p(c,t)={\frac {\pi (t)N_{w,c}(t)}{N_{w,c}}}}$ probabilità di avere un'istanza di classe ${\displaystyle j}$ nel nodo ${\displaystyle t}$;
  • ${\displaystyle N_{w,j}=\sum _{n\in {\mathcal {D}}}w_{n}f_{n}\mathbb {I} (y_{n}=j)}$, con ${\displaystyle w_{n}}$ peso dell'istanza ${\displaystyle n}$ e ${\displaystyle f_{n}}$ peso della frequenza di ${\displaystyle n}$ rispetto a tutto ${\displaystyle {\mathcal {D}}}$;
  • ${\displaystyle N_{w,c}(t)=\sum _{n\in {\mathcal {D}}(t)}w_{n}f_{n}\mathbb {I} (y_{n}=c)}$, conteggio analogo ma limitato a ${\displaystyle {\mathcal {D}}(n)}$, istanze del nodo ${\displaystyle n}$;
• ${\displaystyle p(t)=\sum _{c}p(c,t)}$, probabilità a priori;
• ${\displaystyle p(c|t)={\frac {p(c,t)}{p(t)}}}$, probabilità condizionata.

La misura di impurità di Gini si può scrivere, dato il costo dell'errore di misclassificazione ${\displaystyle C(c'|c)}$:

${\displaystyle i(t)=\sum _{c,c'}C(c'|c)p(c'|t)p(c|t)}$

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

${\displaystyle \Delta _{i}(s,t)=i(t)-p_{1}i(s,t_{1})-p_{0}i(s,t_{0})}$

dove ${\displaystyle p_{1}}$e ${\displaystyle p_{0}}$sono le probabilità di istradare le istanze verso il sottoalbero per cui la condizione è vera (${\displaystyle t_{1}}$) o falsa (${\displaystyle t_{0}}$), rispettivamente. Esse sono facilmente stimabili con ${\displaystyle p_{b}=p(t_{b})/p(t),\ b=0,1}$.

Regressione

Quando la variabile target ${\displaystyle Y}$ è continua, il criterio di partizionamento usato è

${\displaystyle \Delta _{i}(s,t)=i(t)-p_{1}i(s,t_{1})-p_{0}i(s,t_{0})}$

dove, dato l'insieme ${\displaystyle D(t)}$ degli esempi al nodo t:

• ${\displaystyle p_{b}=N_{w}(t_{b})/N_{w}(t)\quad b=0,1}$
• ${\displaystyle N_{w}(t)=\sum _{n\in {\mathcal {D}}(t)}w_{n}f_{n}}$

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

${\displaystyle i(t)={\dfrac {\sum _{n\in {\mathcal {D}}(t)}w_{n}f_{n}(y_{n}-{\bar {y}}_{n}(t))^{2}}{\sum _{n\in D(t)}w_{n}f_{n}}}}$

dove: ${\displaystyle {\bar {y}}(t)={\frac {\sum _{n\in D(t)}w_{n}f_{n}y_{n}}{N_{w}(t)}}}$.

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 ${\displaystyle Y}$, il nodo non sarà partizionato.
• Se tutte le istanze nel nodo hanno valori identici per ogni variabile predittiva ${\displaystyle X_{i}}$, 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.

Voci correlate

• Indice di eterogeneità di Gini
• Twoing