Evoluzione genetica applicata agli alberi di classificazione
|
|
Soluzione proposta, miglioramenti di Gait
A partire da un implementazione di C4.5 in Java ( J48, presente all’interno del framework Weka) si è progettato interamente in Java un Framework per l’esecuzione di algoritmi evolutivi basati sul modello di Gait. Il framework è progettato in modo modulare per permettere di variare le singole parti dell’algoritmo evolutivo, in particolare si sono implementate diverse strategie di selezione e di calcolo della fitness. La strategia originale però (selezione Etilist) si è rivelata migliore malgrado la sua semplicità.
La Rappresentazione dei cromosomi
Il cromosoma rappresenta un albero di decisione binario linearizzato in una lista. Partendo da un albero salvato in una struttura ricorsiva, la linearizzazione avviene nel modo seguente:
Per prima cosa l’albero viene reso completamente numerico. poi lo si linearizza attraverso una visita in profondità a sinistra (visita in pre-ordine). Ad i nodi vengono associate altre informazioni che permettono di determinarne la natura. Nel caso di un nodo decisionale, l’informazione permette di determinare il vincolo, nel caso di una foglia si metterà l’attributo a NaN. Fatto questo, la lista viene ripercorsa per dotare i singoli nodi di un puntatore alla fine del sottoalbero. Benché questo non sia strettamente necessario, rende più veloce lo scorrimento all’interno del cromosoma. La lista ottenuta ( esportata in formato Yaml) è la seguente:
!!tesi.models.Cromosoma cromosoma: - {attributo: 9, fine: 10, punto: 4650.0, taglio: Continuo} - {attributo: 4, fine: 9, punto: 0.0, taglio: Discreto} - {attributo: 5, fine: 4, punto: 7.0, taglio: Discreto} - {attributo: 0, fine: 0, punto: .NaN, taglio: Continuo} - {attributo: 5, fine: 6, punto: 8.0, taglio: Discreto} - {attributo: 0, fine: 0, punto: .NaN, taglio: Continuo} - {attributo: 3, fine: 8, punto: 12.0, taglio: Discreto} - {attributo: 1, fine: 0, punto: .NaN, taglio: Continuo} - {attributo: 0, fine: 0, punto: .NaN, taglio: Continuo} - {attributo: 0, fine: 0, punto: .NaN, taglio: Continuo} - {attributo: 1, fine: 0, punto: .NaN, taglio: Continuo}
Albero corrispondente al dump YAML precedente.
Il vantaggio fondamentale di questa struttura dati è che i sottoalberi sono sempre rappresentati da una sottosequenza di nodi adiacenti, quindi uno scambio di sottoalberi si traduce in uno scambio di sottostrighe, il processo verrà spiegato in dettaglio quando si parlerà delle operazioni di crossover e mutazione.
Questa struttura dati è la versione lineare di quella ricorsiva utilizzata in GAIT che a sua volta è una generalizzazione di quella utilizzata in [cit. kennedy1997contruction ], l’albero di partenza è generato con J48
Un vantaggio secondario di questa struttura è la facilità delle operazioni di serializzazione-deserializzazione che permettono di esportare un cromosoma in un formato facilmente leggibile e modificabile a mano.
Strutture dati per l’implementazione
Un cromosoma è implementato come una lista di geni, per la popolazione
invece si sono scelti due approcci differenti in funzione del tipo di
sampling e selezione che dovrà avere l’algoritmo. La popolazione è
sempre divisa in due sottoinsiemi: quello dei padri e quello dei figli.
I figli sono sempre salvati in una struttura dati lineare ( una
$LinkedList
Implementazione attraverso un albero ordinato : Ha il vantaggio di mantenere un ordinamento crescente nella popolazione (rispetto alla fitness), si utilizza quando il sampling richiede di accedere agli elementi in base al loro ordinamento. ( elitaria, rank )
Implementazione attraverso un array : Ha il vantaggio di essere più veloce, si utilizza quando il sampling non richiede un ordinamento della popolazione. ( torneo)
Crossover e mutazione
Grazie all’implementazione dei cromosomi le procedure di crossover sono molto semplici. Si scelgono i due sottoalberi che sono rappresentati da due sottoliste contigue e si effettua lo scambio. Successivamente l’albero viene ristrutturato per mantenere aggiornati i puntatori ai confini dei sottoalberi. Nel caso entrambi i sottoalberi consistano in delle foglie il crossover non viene eseguito (è una specifica di Gait) e viene creato un clone di uno dei due genitori.
La mutazione è definita come il crossover fra due sottoalberi uguali.
Controllo del Bloat
Utilizzando l’algoritmo di programmazione genetica GAIT sul dataset di esempio Adult (i dettagli su questo dataset verranno dati in [datasets]) per 100 generazioni ci si accorge che a fronte di un miglioramento della fitness di 0.015977 (da 0.830776 a 0.846753, 1%) si ottiene un incremento dell’altezza degli alberi di 8.08 ( da 15.72 a 23.80, 51% ). Questo comportamento costituisce un bloat e suggerisce che applicando delle tecniche per limitare l’altezza degli alberi si possa ottenerne una sostanziale riduzione in altezza senza intaccare molto le performance del classificatore.
Confronto fra pesi e prestazioni nel dataset Adult (zoom sulle prime 25 generazioni)
L’illustrazione successiva visualizza la presenza di bloat colorando i nodi in base al loro utilizzo confrontando 3 alberi con le stesse prestazioni.
Visualizzazione del Bloat, tutti e 3 gli alberi hanno la stessa percentuale di classificazione pari al 83,7%.
Utilizzando una scala cromatica viene evidenziato l'uso dei singoli nodi decisionali. In un albero di classificazione ideale l'uso dei singoli nodi decresce esponenzialmente.
Una sequenza dello stesso colore o un sottoalbero non utilizzato (in blu) sono tipici di alberi affetti da Bloat.
Ottimizazione multiobiettivo
[def:funzione] Per effetuare il controllo del Bloat si è scelto di utilizzare una forma di ottimizzazione multiobiettivo
$$Fitness(i)=f(i) \cdot \alpha + \beta \cdot \sqrt{\frac{1}{\gamma + h(i)}}$$
Dove
f(i)
h(i)
α , β , γ
Si è cercato di tarare α , β , γ con due profili diversi per ottenere due diverse finalità:
Mantenere l’altezza degli alberi il più possibile simili a quelli della prima generazione ( quindi un puro controllo del bloat)
Per questa configurazione si è scelto: α=15; β=1; γ=15.
Ridurre l’altezza degli alberi durante il processo evolutivo cercando di intaccare il meno possibile le prestazioni ( quindi una vera ottimizzazione multiobiettivo )
Per questa configurazione si è scelto: α=5; β=1; γ=15.
Applicazione del metodo Tarpeian
Si è provato ad applicare il metodo tarpeian per controllare il Bloat, creando quindi una variante antibloat di Gait che usa una funzione di fitness semplice. I parametri sono stati impostati in questo modo:
La soglia di attivazione : che stabilisce il limite oltre il quale un cromosoma è candidato all’esclusione è stato settato pari alla media delle altezze della popolazione iniziale
La probabilità di attivazione : che permette di stabilire quanto spesso una generazione è soggetta all’applicazione del metodo è stata fissata al 80%.
La probabilità di selezione : di un singolo cromosoma che supera la dimensione di soglia è stata settata al 20%.
Il numero di generazioni : Per le quali un cromosoma viene escluso dalla selezione è settato a 2.
Metodi alternativi per la selezione
Si è provato a implementare altri metodi di selezione tra cui la SPF.
Selezione a fitness proporzionale
In gait la probabilità di crossover dipende unicamente dal fitness (che è espresso come semplicemente come percentuale di elementi correttamente classificati). La scelta viene effettuata generando dei numeri casuali in [0,1] e selezionando i cromosomi se hanno un fitness superiore. Si ottiene quindi la lista dei genitori da cui vengono estratte a caso le coppie.
Questa strategia ha il difetto di non tenere conto della distribuzione della fitness all’interno della popolazione, la probabilità di selezione cresce con le generazioni.
Un metodo diffuso il letteratura per superare questo problema è la selezione a fitness proporzionale che però da scarsi risultati applicata a GAIT.
In costruzione