Evoluzione genetica applicata agli alberi di classificazione
|
Come detto in precedenza gli algoritmi per la costruzione degli alberi di decisione sono basati su partizionamenti Greedy. Il difetto maggiore di questo approccio approccio è il fatto che il dataset utile si riduce a ogni scelta, portando i nodi più profondi ad agire su pochi dati e provocando quindi overfitting.
Un approccio alternativo agli “ensemble of trees“ è l’utilizzo degli algoritmi genetici. Gli algoritmi genetici permettono di aggirare i problemi del Ottimo locale, effettuando una ricerca globale nello spazio delle soluzioni.
Per questo tendono ad avere risultati superiori agli algoritmi Greedy nell’individuare le iterazioni tra gli attributi, producendo sia un miglioramento nelle prestazioni che alberi capaci di una maggiore generalizzazione e, nel caso di implementazioni che controllino il bloat, un pruning efficace degli alberi.
Oltre agli approcci che evolvono alberi generati con algoritmi classici esistono anche implementazioni che partono da alberi generati casualmente e utilizzano quindi tecniche evolutive per l’intero processo [cit. llora2001evolution ].
Gait (Genetic Algorithm approach for generating Intelligent Trees) è un algoritmo evolutivo descritto in [cit. fu2003genetic ]. Gait utilizza la programmazione genetica per evolvere alberi binari generati con C4.5. In [cit. fu2003genetic ] sono descritte molte varianti dell’algoritmo, qui mi limiterò a descrivere la prima variante.
La selezione è strettamente elitaria: ogni cromosoma ha una probabilità di riprodursi pari al suo fitness.
Il Crossover è definito come lo scambio tra due sottoalberi, quindi a partire da due alberi A e B si genera un terzo albero C che è costituito dall’albero A in cui uno dei rami è stato sostituito con un ramo di B. Sono possibili sia scambi ramo-ramo che ramo-foglia, mentre si evitano scambi foglia-foglia. Lavorando in questo modo ogni cromosoma prodotto è sicuramente un albero completo ed è impossibile avere un albero che ha come foglia un nodo decisionale.
La mutazione è definita come il Crossover fra due alberi identici; la selezione per la mutazione avviene scegliendo alberi dall’intera popolazione con una probabilità fissata a 0.01%, l’albero così creato sostituisce il ”genitore“.
Gait divide il dataset iniziale in 3 parti: trainingset, testset, scoringset.
il trainingset viene utilizzato per creare la popolazione iniziale degli alberi;
ogni albero durante l’evoluzione viene misurato sullo scoringset, la fitness è definita semplicemente come la percentuale di classificazione corretta;
l’albero migliore alla fine dell’evoluzione viene misurato sul testset.
Gait è a popolazione fissa, in particolare la prima versione prevede 50 elementi: partendo da 50 elementi, alla fine di ogni generazione vengono eliminati quelli meno performanti, in modo da ottenere sempre una popolazione di 50 elementi.
Per come è definito il crossover si possono generare alberi sintatticamente corretti ma semanticamente insensati. E’ possibile che lungo la visita di un albero si incontrino check in contraddizione tra loro oppure delle tautologie, in quel caso esisterebbero dei sottoalberi che non vengono mai percorsi.
Per evitare questa situazione è possibile effettuare un controllo di coerenza subito dopo la creazione dell’albero: se l’albero si rivela semanticamente insensato lo si corregge eliminando i sottoalberi non percorsi. Un altro approccio molto più semplice è lasciare l’albero nella popolazione ignorando il problema, sarà la selezione genetica ad occuparsene. Nell’algoritmo implementato in questo lavoro di tesi ho usato quest’ultimo approccio.
E’ possibile effettuare un postpruning degli alberi per cercare di ridurne la taglia e aumentarne la generalizzazione. Il pruning avviene visitando l’albero per livelli partendo dall’ultimo. Ogni nodo decisionale viene sostituito con una foglia se questa sostituzione provoca un aumento del tasso di errore inferiore a una certa soglia (per esempio 0.5%). Nell’algoritmo implementato in questo lavoro di tesi, il pruning non viene utilizzato.
In costruzione