CART (algoritmo)

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 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

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)}}}$.