Alberi di regressione e classificazione

Un albero di classificazione è un algoritmo di scelta di un valore discreto, basato su un grafo ad albero; nei prossimi paragrafi si analizzerà la loro costruzione. Il grafo di un albero di classificazione è costruito mediante ripetute suddivisioni di sottoinsiemi dell’insieme χ, detto nodo principale t1, che contiene tutti i dati del campione per l’apprendimento, in due sottoinsiemi discendenti, detti nodi non terminali, a partire da χ stesso.

Quindi ciascun nodo discendente viene ulteriormente diviso in altri due nodi non terminali discendenti. Ovviamente questo processo di scissione non è infinito, per cui si giungerà a nodi che non possono essere ulteriormente divisi, detti nodi terminali o foglie. Gli insiemi dei casi attribuiti ai nodi terminali formano una partizione dell’insieme χ e ciascuno è attribuito ad una classe (possono esistere pi`u nodi terminali attribuiti alla stessa classe).

Nella figura sopra riportata (presa dal sito www.gisdevelopment.net), osserviamo che i nodi non terminali sono rappresentati da cerchi, i nodi terminali da punti neri, o spesso anche da quadrati; la distinzione grafica rappresenta quindi la diversa funzione dei due tipi di nodi: infatti i nodi non terminali sono associati a domande riferite su una delle variabili precedenti sulla quale si basa una suddivisione del nodo (è come se si effettuasse un test ai dati in input), i nodi terminali sono associati ai risultati della classificazione,per questo, come visto sopra, ciascuno di essi è attribuito a una classe, perché è in questi nodi che i dati vengono classificati.

Le suddivisioni, che in questo caso sono “binarie”, perché ogni volta dividono un nodo in altri due, si eseguono mediante condizioni sulle coordinate del vettore di misure x = (x1, . . . , xN) e in genere si basano su domande la cui risposta pu`o essere positiva o negativa. L’obiettivo di un albero di classificazione è prevedere una classe per il vettore x ponendo le varie condizioni sulle coordinate: dalla prima suddivisione si determina se x va nel nodo di destra, indicato con tR, o nel nodo di sinistra, indicato con tL, quindi attraversa tutti i rami discendenti, fino a raggiungere un nodo terminale, dove la classe è data dal numero posto, in generale, al di sotto del simbolo scelto per rappresentare una foglia (come visto sopra un quadrato o un punto nero).

L’intera costruzione di un albero ruota, quindi, attorno a tre elementi fondamentali:
1. la selezione delle suddivisioni,
2. la decisione di dichiare un nodo terminale o continuare a suddividerlo,
3. l’assegnazione di una classe ad ogni nodo terminale.