Nell'albero decisionale i nodi interni corrispondono a test su un attributo, mentre le foglie sono le categorie di oggetti classificati.
Un albero decisionale si costruisce partendo da un training set nel seguente modo: quando tutti i dati su un attributo assumono lo stesso valore crea una foglia, altrimenti genera un nodo interno su un attributo partizionando l'insieme nel modo migliore. Alla fine avremo tante foglie quante sono le classi in cui abbiamo diviso il training set.
Quindi si potrà usare un test sample per verificare la correttezza del nostro albero, nel quale ogni cammino dalla radice a una foglia rappresenta un insieme di condizioni da verificare.
Un problema che sorge nel costruire gli alberi decisionali è che il loro numero è circa esponenziale, e si deve scegliere il migliore. Anche questo passo, come la scelta dell'attributo su cui fare la partizione, si risolve con una funzione di bontà.
Due possibilità per le scelte della goodness function sono l'information gain(information ratio) e il gini index.
L'information gain è una misura usata da ID3/C4.5, algoritmi che servono a costruire l'albero decisionale con un metodo top-down, che cioè partendo dalla radice dividono ricorsivamente il training set su un attributo. Questi metodi hanno una fase di pruning per togliere tutti i cammini che portano a errore.
ID3, invece di usare tutto il training set, prende una window e costruisce da questa l'albero. Testa la correttezza dell'albero usando gli altri elementi dell'insieme. Per ogni oggetto non classificato correttamente, lo aggiunge alla window e ripete il procedimento.
L'information gain ha come idea chiave che ogni attributo definisce una categoria di informazione, e si basa sul concetto di entropia. Sia X una variabile aleatoria che può assumere k valori xi con probabilità pi. Allora H(p1,p2, ..., pn) è l'incertezza media che viene rimossa all'accadere di un xi, cioè H è il disordine di una variabile random:
Nel caso di ID3, assumiamo che ci siano due classi P e N, e che S contenga p elementi della classe di P e n elementi della classe di N. Ogni oggetto sta in P con probabilità p/(p+n) e in N con probabilità n/(p+n). La quantità d'informazione necessaria per classificare un oggetto, cioè per decidere se un elemento appartiene a P o ad N è definita come:
Supponiamo che usando l'attributo A come radice, l'insieme S sarà partizionato in
insiemi. Se Si contiene pi elementi di P, ed
ni elementi di N, le informazioni necessarie per classificare gli
oggetti in Si sono I(pi, ni). Quindi l'informazione richiesta per
l'albero con radice A è ottenuta da una media pesata degli
I:
Nel caso generale, sia S avente k classi differenti C1, C2, ..., Ck. L'informazione per classificare un dato campione è:
che è l'entropia dell'insieme S, e misura la quantità di informazione necessaria per identificare la classe di un record di S.
Sia T un insieme di record, sia X un attributo avente valori {a1, a2, ..., an}. Facendo un test su X partizioneremo T in tanti sottoinsiemi Ti, l'entropia di T sarà la media ponderata delle entropie dei singoli sottoinsiemi, cioè:
La quantità d'informazione guadagnata dal partizionamento di T secondo l'attributo X sarà:
L'attributo X è selezionato se l'information gain è massimo, cioè se infoX(T) è minimo perchè info(T) è lo stesso per tutti gli attributi di quel nodo. L'information gain seleziona sempre il test che massimizza questa quantità.
Il problema di questo approccio è che è fortemente sbilanciato verso quei test con molti esiti. Può accadere però che la divisione dovrebbe essere fatta su un attributo con pochi valori possibili, ma per quanto detto questo non verrà scelto.
Un modo per ovviare a questo problema è normalizzare l'information gain. Consideriamo l'informazione contenuta da un messaggio sulla probabile divisione dell'insieme T negli insiemi Ti. Tale informazione sarà data da:
e per analogia con la definizione di info(S) si ha:
che rappresenta la potenziale informazione generata dalla divisione di T. Quindi l'information ratio è pari a:
Un'altra misura di goodness è il gini index che si applica per attributi con valori continui. Se un insieme S contiene n classi, l'indice Gini è definito come
dove pi è la frequenza relativa della classe i in S. Se S è diviso in due sottoinsiemi S1 e S2 di dimensione N1 e N2, il gini index dello split è definito come:
L'attributo con minor valore è scelto come attributo di splitting.
Nel caso di test su attributi di tipo continuo, l’esito è quello di una comparazione con un valore soglia Z, per cui i risultati saranno due: o il valore A dell’attributo è maggiore di Z o non lo è (A > Z o A <= Z). Il criterio introduce anche un’altra restrizione, ovvero che per ogni divisione i due più piccoli insiemi risultanti devono avere un numero minimo stabilito di elementi.
Nel caso di test su attributi di tipo continuo abbiamo parlato di Z come valore soglia. La ricerca di questa soglia per effettuare il test viene fatta valutando tutti i valori assunti dall’attributo in questione in tutti i casi presenti nel training set. Questi valori vengono raggruppati in un insieme ordinato {v1, v2, . . . , vm}. Di conseguenza, scelto vi come valore soglia, l’insieme verrebbe partizionato in {v1, v2, . . . , vi} e {vi+1, vi+2, . . . , vm} .
Parlando di information gain abbiamo dato per scontato l'esistenza di informazione su un particolare valore, ma non sempre questo accade e in questo caso la differenza di entropia tra prima e dopo il test è nulla. Possiamo riscrivere il gain(X) nel seguente modo:
dove X è un test su alcuni attributi A, T è il training set ed F è la percentuale di casi di T per cui A è noto. Va ricalcolata split info(T) e di conseguenza anche il gain ratio. Questo avrà effetto sul partizionamento. Se il record ha un valore sconosciuto, il peso è proprio la probabilità che il valore sia vi.
Ogni sottoinsieme Ti è ora una collezione di casi con pesi possibilmente frazionali, così che |Ti| potrebbe essere reinterpretata come la somma di pesi frazionali dei casi nel sottoinsieme. In generale, un caso di T con peso w il cui esito non è conosciuto è assegnato a ogni sottoinsieme Ti con peso w * probabilità che l'esito sia vi.
L’elevato numero di attributi in un training set o la particolare distribuzione dei valori degli attributi, può fare crescere notevolmente la dimensione dell’albero. Questo fenomeno è chiamato overfitting. Rende più difficile la classificazione (dovuto ad outliers) ed è associato ad un aumento non giustificato di errori. Il pruning rimuove una parte di albero, uno o più rami, che non contribuisce ad una corretta classificazione, producendo qualcosa di meno complesso e così più comprensibile. Le strategie possibili per effettuare il pruning di un albero sono due: