Definizione di alberi decisionali

Partendo dall’utilizzo di insiemi già classificati di dati (training set), si cerca di definire alcune regolarità che caratterizzano le varie classi.
Dopo aver testato il modello (mediante un test set), le descrizioni (delle classi) così ottenute vengono generalizzate (inferenza o induzione) e usate per classificare record di cui non si conosce la classe di appartenenza.
Gli alberi di decisione (o alberi di classificazione) costituiscono il modo più semplice di classificare degli “oggetti” in un numero finito di classi.
Essi vengono costruiti suddividendo ripetutamente i record in sottoinsiemi omogenei rispetto all’attributo target (che ricordiamo essere categorico).
Le regole di classificazione che vedremo sono di tipo univariato, nel senso che considerano un solo “predittore” (attributo target) alla volta. Tuttavia, esistono algoritmi multivariati, nei quali il predittore è rappresentato da una combinazione lineare di variabili.
La suddivisione produce una gerarchia ad albero, dove i sottoinsiemi (di record) vengono chiamati nodi e, quelli finali (o terminali), foglie.
In particolare, i nodi sono etichettati con il nome degli attributi, gli archi sono etichettati con i possibili valori dell’attributo soprastante, mentre le foglie dell’albero sono etichettate con i differenti valori dell’attributo target (valori che descrivono le classi di appartenenza).
Un oggetto è classificato seguendo un percorso lungo l’albero che porti dalla radice ad una foglia.
I percorsi rappresentano le regole di classificazione (o regole produttive).
I rami sono i valori assunti dai diversi attributi. Le foglie sono la classificazione. La regola si scrive andando a percorrere l’albero a partire dal nodo, fino alle diverse foglie. Tutti i possibili percorsi rappresentano le possibili regole.
Esistono alcuni problemi legati all’efficienza dell’algoritmo:
- da quale nodo parto per costruire l’albero: L’esito dipende dal nodo di cui parto e dai nodi che scelgo per la costruzione. Bisogna avere una regola per essere il più efficienti possibili.
- Che significato diamo alla parola efficienza:
- Come misuriamo la bontà di un albero:
- Come limitiamo la crescita di un albero:
- Come potiamo l’albero:
C4.5 è un algoritmo per creare alberi decisionali.
1. Sia T l’insieme delle osservazioni di training (training set).
2. Si seleziona l’attributo che meglio differenzia le osservazioni (record) contenute in T. Idealmente l’attributo che meglio differenzia le osservazioni è l’attributo che consente di mettere il più possibile di osservazioni all’interno di una classe di appartenenza. L’ideale è usare attributi che classificano le osservazioni in due classi dove una prevale di molto sull’altra, è meglio che non ci sia una equi distribuzione.
3. Si crea un nodo dell’albero (nodo radice) il cui valore corrisponde all’attributo selezionato. A partire da tale nodo si creano dei collegamenti (rami), ciascuno dei quali rappresenta un valore unico per la variabile scelta. Si utilizzano i valori di tali collegamenti per suddividere ulteriormente le osservazioni in sottoclassi.
A partire da ogni attributo si ottiene un sottoinsieme di osservazioni. Se tutte le osservazioni stanno in una classe di appartenenza ho ottenuto una foglia, mentre se le osservazioni si ripartiscono equamente in classi di appartenenza, non ho ottenuto un’informazione. In queste condizioni l’algoritmo si pone il problema di cambiare la scelta del nodo di partenza. Devo prendere un altro attributo, e in corrispondenza di ognuno dei rami costruiti, si deve porre un altro attributo, per vedere come sono riapartite rispetto alla classe target.
4. Per ogni sottoclasse creata nel passo 3:
a. Se le osservazioni nella sottoclasse soddisfano i criteri predefiniti (valori dell’attributo target) o se per questo percorso non ci sono scelte alternative di variabili, si specifica la classificazione di nuove osservazioni seguendo questo percorso decisionale (nodo terminale o foglia)
b. Se la sottoclasse non soddisfa i criteri predefiniti ed esiste almeno un attributo per effettuare un’ulteriore suddivisione del percorso dell’albero, T diventa l’insieme corrente di osservazioni della sottoclasse e si torna al passo 2.