Evoluzione genetica applicata agli alberi di classificazione
8. Algoritmi genetici applicati agli alberi di classificazione

128x128



Algoritmi genetici applicati 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

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.

Operatori in Gait

Selezione

La selezione è strettamente elitaria: ogni cromosoma ha una probabilità di riprodursi pari al suo fitness.

Crossover

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.

Mutazione

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“.

Calcolo della fitness

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.

Ridimensionamento della popolazione

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.

Controllo di coerenza (feasibility check)

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.

Un albero prima e dopo il controllo di coerenza, da [cit. fu2003genetic ]

Pruning

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.


Precedente Successivo


Copyright © 2014 Vincenzo La Spesa

Torna su