Caratteristiche degli alberi di decisione (decision tree) in informatica
Il decision tree è un classificatore con struttura ad albero (alberi di decisione), in cui ogni nodo può essere o foglia o nodo interno: se foglia, indica il valore della classe assegnata all’istanza; se nodo interno, specifica il test effettuato su un attributo. Per ciascun valore assunto da un attributo in un test, l’algoritmo crea un ramo e il relativo sottoalbero.
Il focus principale dell’algoritmo di crescita del decision tree è come scegliere gli attributi da testare in ciascun nodo interno dell’albero.
L’obiettivo è selezionare gli attributi più utili per classificare le istanze di training attraverso una strategia top down, che consiste in una ricerca greedy degli attributi senza tornare a riconsiderare le precedenti scelte.
Il criterio di split (suddivisione) con cui crea un nuovo nodo si basa sul massimo guadagno di informazione (info gain). In pratica sceglie l’attributo che riesce a dividere “meglio” le istanze appartenenti a classi diverse (detto anche criterio di massima riduzione di incertezza). Quando tutti gli elementi in un nodo hanno la medesima classe, l’algoritmo non procede con ulteriore split (criterio di stopping). Per evitare overfitting, l’algoritmo inizia una eventuale fase di pruning (potatura): individua gli attributi che non hanno contribuito ad una consistente suddivisione delle istanze ed elimina i rispettivi nodi riunendo le istanze al livello superiore. Quando l’algortimo termina, è possibile percorrere l’albero dalla radice e, seguendo il persorso risultante dai singoli test presenti su ogni nodo interno, si ottiene la classificazione dell’istanza (nodo foglia).
Il decision tree non funziona bene quando la classificazione prevede numerose classi e un numero relativamente piccolo di esempi. Inoltre la fase di training può essere computazionalmente costosa perchè deve confrontare tutti i possibili split ed eventualmente effettuare il pruning, anch’esso molto costoso.
