Evoluzione genetica applicata agli alberi di classificazione
10. Risultati ottenuti

Risultati ottenuti

Dataset utilizzati

Si è testato il comportamento dell’algoritmo su diversi dataset presi dall’archivio del ”UCI Machine Learning Repository”[cit. BacheLichman2013 ]

Prestazioni sul dataset Adult

Sono stati ripetuti dei test sul dataset Adult con modalità molto simili a quelle descritte in Gait, Si usa l’intero dataset, che viene diviso secondo le stesse percentuali avendo quindi:

• Un numero totale di 45222 elementi

• Un trainingset di 24667 elementi

• Un testset di 8222 elementi

• Uno scoringset di 12333 elementi

Il trainingset viene diviso in 50 alberi da 246 elementi che vengono fatti evolvere per 100 generazioni.

Evoluzione delle prestazioni. Evoluzione dei pesi
(definiti uguali alle altezze).

I grafici precedenti evidenziano come si possa controllare il bloat senza perdere precisione, GaitMulti(5-1-15) riesce a ottenere la stessa precisione di Gait generando alberi di taglia inferiore. Per le analisi dei tempi si sono eseguiti i test su un RaspberryPi (un single-board computer dotato di 256Mb di Ram e di un processore ARM da 700 MHz) in modo da avere contemporaneamente una macchina sufficientemente lenta e facilmente riproducibile.

Per prima cosa si è indagato sulla dipendenza del tempo di classificazione rispetto all’altezza dell’albero.

Contrariamente a quanto si possa supporre a prima vista un albero grande non implica necessariamente un tempo di classificazione maggiore. Questo fenomeno dipende dal fatto che Gait soffre del fenomeno del bloat e quindi crea alberi contenenti sottoalberi morti che non vengono mai percorsi.

Analisi della crescita dei tempi di classificazione al crescere dell’altezza degli alberi nel dataset adult.

Il fenomeno è evidenziato nel grafico precedente. Il grafico mostra due serie di box plot: Nella prima riga ci sono i box plot relativi ai tempi di esecuzione di alberi generati senza tener conto dell’altezza, mentre nella seconda i tempi di esecuzione di alberi generati con Gait(15-1-15).

Ogni colonna contiene un box plot per gli alberi di una determinata altezza. Solo negli alberi ottimizzati il tempo di classificazione cresce con l’altezza degli alberi.

Prestazioni e tempi su altri dataset

Tutti i tempi sono espressi in millisecondi e si riferiscono al tempo di classificazione medio di un generico albero migliore (prodotto da una singola esecuzione di un algoritmo evolutivo) sull’intero dataset, tranne nel caso del datset Covtype.

La prestazione è definita semplicemente come la percentuale di istanze correttamente classificate.

Sui dataset vengono testati vari algoritmi:

I grafici precedenti mostrano i risultati dei test per i vari dataset, ogni colonna contiene 3 righe che contengono i 3 grafici per il singolo dataset. In tutti i casi si verifica una diminuzione delle altezze medie degli alberi applicando sia un ottimizzazione multiobiettivo o il metodo Tarpeian. L’efficacia dei metodi non è però uguale nei vari dataset:

Per il dataset Adult si rivela migliore l’algoritmo “Gait Antibloat (15-1-15)” che genera un abbattimento dei tempi di classificazione ( da 198 a 182) a fronte di una perdita dello 0.21%.

Si rivela invece poco performante l’applicazione del metodo Tarpeian.

Per il dataset Parkinson Il dataset si rivela impossibile da ottimizzare, gli algoritmi tendono a ottenere risultati peggiori rispetto a Gait.

L’unica eccezione è l’algoritmo Tarpeian che lascia sostanzialmente invariati tutti i parametri.

Per il dataset Heart Similmente al caso Parkinson si rivela impossibile da ottimizzare, in questo caso però gli algoritmi tendono a lasciare invariate le prestazioni.

L’algoritmo Tarpeian che ottiene tempi di classificazione leggermente inferiori a fronte di alberi di altezza sostanzialmente identica a quelli di Gait. “Gait Antibloat (15-1-15)” si rivela particolarmente lento.

Per il dataset Covtype si rivela migliore l’algoritmo “Gait Antibloat (5-1-15)” che genera un abbattimento dei tempi di classificazione ( da 2189 a 1927) a fronte di una perdita dello 0.22%. Si rivela invece poco performante l’applicazione del metodo Tarpeian

Dai risultati ottenuti si evince superiore un approccio multiobiettivo al controllo del Bloat, applicato però a dataset sufficientemente grandi. Dataset particolarmente piccoli producono alberi già molto corti e difficili da ottimizzare, si corre quindi il rischio di provocare overfitting. In queste condizioni il metodo Tarpeian si rivela utile, quantomeno nel non peggiorare le cose.

Miglioramenti possibili e questioni aperte

La programmazione genetica si basa sull’utilizzare il caso per indurre il sistema a ricercare soluzioni in nuove zone dello spazio di ricerca, il ruolo della mutazione in questo processo è fondamentale: Essa permette di introdurre informazioni che non sono presenti nei cromosomi e non possono essere generate per Crossover.

Per come è progettata la mutazione in Gait (interna al singolo cromosoma) un nodo decisionale che non è presente negli alberi non potrà mai comparire. Infatti il classificatore iniziale potrebbe non far comparire mai una data condizione o addirittura non far comparire mai condizioni su una determinata dimensione.

Un possibile miglioramento si potrebbe ottenere implementando delle tecniche di mutazione più radicali che possano forzare l’ecosistema ad esplorare nuove zone dello spazio di ricerca.

Ad esempio utilizzando tecniche basate su ”headless chicken“ che costruisce nodi decisionali casuali.

Un altro modo per incrementare la diversità sarebbe il disabilitare il pruning di J48 e affidarlo all’algoritmo evolutivo (attraverso una vera procedura di pruning o attraverso un ottimizzazione multiobiettivo)

Sarebbero inoltre possibili altre analisi sulle caratteristiche degli alberi, in particolare:

• Analizzare i tempi di evoluzione oltre che quelli di classificazione.

• Analizzare il numero di nodi degli alberi oltre che l’altezza.

• Quantificare il bloat analizzando l’uso dei singoli nodi decisionali in modo da evidenziare i sottoalberi morti, questo tipo di analisi è stata svolta solo parzialmente.