Alberi decisionali e regole di classificazione

Massimizzare la probabilità e MDL

Massimizzare la probabilità vuol dire minimizzare i logaritmi. Il numero dei bit per codificare qualcosa è il logaritmo negativo della sua probabilità: logPr E dipende [ ] solo dal training, quindi posso agire solamente sulla probabilità del modello Pr T, [ |E minimizzando L E T L T| .

MDL si può usare anche come criterio per trovare il miglior numero di cluster che vanno a modellare i dati. Si usa la lunghezza della descrizione come modo per misurare la codifica dei cluster.

Per codificare gli errori posso usare la distanza tra i centri dei cluster e codificare quella. La soluzione che il numero minore possibile di cluster mi darà una minore codifica per i centroidi e il costo per codificare la distanza sarà anche più basso.

Capitolo alberi e regole 6

È un'evoluzione dell'algoritmo ID in quanto consente la gestione di attributi numerici, dei valori mancanti e la gestione di dati rumorosi. Per quanto riguarda i dati rumorosi vengono utilizzate due tecniche di pruning che vedremo successivamente. L'implementazione più comune di questo algoritmo è J48.

Gestione degli attributi numerici

Per gli attributi numerici non si può avere uno split ad ogni valore, ma bisogna effettuare delle manipolazioni per riuscire a gestirli. Consideriamo ad esempio:

Tra i valori consecutivi si possono trovare dei punti di split: è possibile separare degli insiemi di istanti in due sottoclassi. Ad esempio ci sono possibili posizioni 11 per i punti di split che si riducono a 8 se non vogliamo separare oggetti appartenenti alla stessa classe. Per ogni possibile split point v si calcola l'information gain che si ottiene separando i dati con un test del tipo temperature < v.

Ad esempio il test temperature < 71.5 produce 4 yes e 2 no, mentre temperature > 71.5 produce 5 yes e 3 no. L'informazione attesa dal punto di split è:

Riassunti Machine Learning 46

È comune posizionare le soglie numeriche a metà tra i valori che delimitano i confini di un concetto, anche se si potrebbe ottenere qualcosa di più sofisticato adottando una politica diversa.

Riassumendo il procedimento è:

• Per ogni attributo numerico ordiniamo i valori dell'attributo.
• Valutiamo l'information gain per ogni possibile punto di split dell'attributo.
• Viene splittato il miglior punto con information gain migliore.

Quando si creano alberi decisionali utilizzando il metodo divide et impera, una volta selezionato il primo attributo su cui eseguire la suddivisione viene creato un nodo principale dell'albero che si suddivide su quell'attributo e l'algoritmo procede ricorsivamente su ciascun nodo figlio.

Per ogni attributo numerico, sembra che il sottoinsieme di istanze di ciascun nodo figlio debba essere riordinato in base ai valori di quell'attributo e infatti i programmi per indurre alberi decisionali vengono solitamente scritti in questo modo. Tuttavia non è effettivamente necessario riordinare perché l'ordinamento di un nodo genitore può essere utilizzato per derivare l'ordinamento per ciascun figlio, portando a una implementazione più veloce.

La complessità richiesta per l'ordinamento è O(n log n), quella per la derivazione dell'ordinamento dal genitore è O(n). L'inconveniente è che ho bisogno di creare e memorizzare questo array di indici per ogni attributo numerico.

Dal momento che per gli attributi numerici usiamo uno split binario, potremmo ottenere un albero finale che risulta meno leggibile rispetto a quelli ottenuti con split a più vie utilizzati con gli attributi nominali. In questo caso infatti lo split su un attributo nominale esaurisce tutta l'informazione contenuta in quell'attributo perché ogni attributo nominale viene testato al più una sola volta su qualsiasi percorso dell'albero.

Così non è per gli attributi numerici, che possono essere testati più volte lungo un percorso dell'albero. Due possibili rimedi sono prediscretizzare gli attributi numerici, e quindi testiamo ogni attributo una sola volta, oppure potrei usare uno split multi way, uso tante ramificazioni dello split quanti sono i valori distinti, che si gestisce mediante un algoritmo di programmazione dinamica. In generale però si continua ad utilizzare quello binario.

Gestione dei valori mancanti

Esistono diverse tecniche per gestire il problema. Bisogna innanzitutto capire se ha dei significati particolari. Una soluzione è quella di ignorare completamente tutte le istanze che hanno qualche valore mancante, ma la soluzione sarebbe troppo rigorosa perché spesso istanze con valori mancanti forniscono una buona quantità di informazioni.

Riassunti Machine Learning 47

Ci chiediamo quindi come classificare un'istanza che presenta attributi con valori mancanti attraverso un albero di decisione. Una soluzione semplice potrebbe essere quella di tenere traccia del numero di elementi del training set che scendono lungo ogni ramo e usare il ramo più popolare se il valore per un'istanza di test è mancante.

Una soluzione più sofisticata è quella di dividere l'istanza in pezzi e distribuire questi pezzi lungo ogni ramo, fino ad arrivare alle foglie. Lo split viene effettuato usando un peso numerico compreso tra 0 e 1 e il peso del ramo è scelto in maniera proporzionale al numero di istanze di training che scendono lungo quel ramo. La somma di tutti i pesi deve fare 1.

Alla fine le varie parti dell'istanza raggiungeranno un nodo foglia e le decisioni in questi nodi foglia devono essere ricombinate usando i pesi che sono stati propagati fino alle foglie. I concetti di information gain o gain ratio rimangono invariati pur di considerare istanze pesate.

Un altro problema è quello legato al partizionamento del training set una volta che è stato scelto l'attributo di split per consentire l'applicazione ricorsiva sui nodi figli della procedura che permette la costruzione dell'albero di decisione. Si utilizza sempre la stessa procedura di pesatura.

Istanze che presentano attributi con valori mancanti sono divisi in pezzi, un pezzo per ogni ramo, nella stessa proporzione con cui le varie istanze scendono lungo i vari rami. I pezzi dell'istanza contribuiscono alla decisione nei nodi inferiori sempre secondo il criterio dell'information gain ricordando però che adesso ci sono dei pesi. Questi pezzi potrebbero essere divisi a loro volta se ci sono altri attributi con valori mancanti.

Pruning

RIPPER

Un albero completamente espanso spesso contiene parti non necessarie e questo crea grossi problemi di overfitting rispetto ai dati di training.

Una strategia per semplificarli è il pruning, che si divide in prepruning (forward pruning) e postpruning (backward pruning).

Il prepruning cerca di decidere dove interrompere la costruzione degli alberi prima che sia completa, quindi evitando