MOELIGA: a multi-objective evolutionary approach for feature selection with local improvement

1. Probleemstelling

In het huidige machine learning-landschap worden onderzoekers geconfronteerd met steeds hogere dimensionaliteit in data, terwijl het aantal beschikbare steekproeven vaak beperkt blijft (bijvoorbeeld in biologische toepassingen). Dit leidt tot het "curse of dimensionality"-probleem, wat de generalisatie van modellen verslechtert en de interpretatie bemoeilijkt.

Feature Selection (FS) is een cruciale techniek om een subset van de meest relevante kenmerken te selecteren, waardoor de modelcomplexiteit daalt en de prestaties verbeteren. Het centrale probleem is echter dat het vinden van de optimale subset een multi-objectieve optimalisatieprobleem is:

1. Maximalisatie van classificatie-accuraatheid.
2. Minimalisatie van het aantal geselecteerde kenmerken (dimensionaliteit).

Deze doelen staan vaak in conflict. Traditionele methoden (zoals filter-methoden of eenvoudige genetische algoritmen) hebben moeite om dit evenwicht te vinden, vaak doordat ze vastlopen in lokale optima of geen rekening houden met de interactie tussen kenmerken. Daarnaast vereisen veel bestaande methoden dat de gebruiker a priori het aantal te selecteren kenmerken specificeert, wat suboptimale resultaten kan opleveren als deze waarde niet overeenkomt met de intrinsieke dimensionaliteit van het probleem.

2. Methodologie: MOELIGA

De auteurs stellen MOELIGA (Multi-Objective Locally-Improved Genetic Algorithm) voor, een nieuw evolutionair algoritme dat specifiek is ontworpen voor multi-objectieve feature selection. De kern van de methode bestaat uit de volgende componenten:

A. Evolutionaire Lokale Verbetering (Evolutionary Local Improvement)

In plaats van alleen de hoofdbevolking te evolueren, introduceert MOELIGA een hiërarchische structuur:

• De beste individuen (chromosomen) uit de hoofdbevolking dienen als "templates".
• Voor deze templates worden subordinatiepopulaties gegenereerd die zich beperken tot de actieve kenmerken van de template.
• Deze subordinatiepopulaties ondergaan een lokaal evolutionair proces om de specifieke subset van kenmerken te verfijnen.
• Dit proces fungeert als een intensificatiemechanisme dat de zoektocht verdiept in veelbelovende gebieden van de zoekruimte.

B. Drie Doelfuncties

MOELIGA optimaliseert drie objectieven tegelijkertijd:

1. Classificatie-accuraatheid (UAR): Gemeten via Unweighted Average Recall (ook wel Balanced Accuracy). Dit zorgt voor robuustheid tegen onbalans in klassen. De evaluatie gebeurt via kruisvalidatie om overfitting te voorkomen.
2. Compactheid (Sigmoid-transformatie): Een functie die het aantal geselecteerde kenmerken bestraft. Het gebruik van een sigmoidale transformatie zorgt ervoor dat het verschil tussen kleine subsets (bijv. 10 vs. 15 kenmerken) significant groter wordt gewaardeerd dan bij grote subsets (bijv. 1000 vs. 1005). Dit drijft het algoritme aan om zeer compacte oplossingen te vinden.
3. Classificator-onafhankelijkheid (Geometrische afstand): Een nieuwe objectief gebaseerd op de afstand tussen nearest hits (zelfde klasse) en nearest misses (verschillende klasse) in de geselecteerde kenmerkruimte. Een hoge score hierop betekent dat de kenmerken de klassen goed scheiden, ongeacht welke classifier later wordt gebruikt. Dit helpt overfitting op een specifieke classifier te voorkomen.

C. Diversiteitsbehoud (Fitness Sharing)

Om te voorkomen dat de populatie convergeert naar een enkel punt op de Pareto-front, gebruikt MOELIGA een crowding-based fitness sharing mechanisme.

• Individuen worden bestraft als ze in dichtbevolkte gebieden van de zoekruimte (zowel in objectieve ruimte als beslissingsvariabele ruimte) zitten.
• Dit bevordert een gediversifieerde Pareto-front, waardoor de gebruiker een breed scala aan trade-offs tussen nauwkeurigheid en complexiteit kan kiezen.

D. Gestructureerde Initialisatie

De populatie wordt gestart met een "staggered initialization": verschillende delen van de populatie worden geïnitieerd met verschillende percentages actieve genen (3%, 15%, 35%). Dit garandeert dat de zoektocht direct begint met een breed scala aan subsetgroottes.

3. Belangrijkste Bijdragen

1. Nieuwe Local Improvement Strategie: Een hybride aanpak waarbij subordinatiepopulaties worden gebruikt om de beste oplossingen lokaal te optimaliseren binnen hun eigen kenmerkruimte.
2. Sigmoid Transformatie voor Kenmerkselectie: Een innovatieve manier om de druk op het vinden van zeer kleine subsets te vergroten zonder de zoektocht te blokkeren bij grote datasets.
3. Geometrische Objectief: Een derde doel dat classifier-onafhankelijkheid promoot door de geometrische scheidbaarheid van klassen te maximaliseren.
4. Automatische Dimensionaliteit: In tegenstelling tot veel state-of-the-art methoden, bepaalt MOELIGA het optimale aantal kenmerken automatisch tijdens het optimalisatieproces.

4. Experimentele Resultaten

De auteurs hebben MOELIGA getest op 14 diverse datasets (van synthetisch tot real-world, met 14 tot 20.000 kenmerken) en vergeleken met 11 state-of-the-art methoden (waaronder RFE, SFFS, Boruta, ReliefF, Mutual Information, en verschillende SURF-varianten).

• Prestaties: MOELIGA behaalde superieure resultaten (hogere UAR) op 9 van de 14 datasets. De verbeteringen liepen op tot 30% vergeleken met de beste concurrenten. Op de overige datasets was de prestatie vergelijkbaar of slechts marginaal lager (<3%).
• Statistische Significantie: Een Friedman-test met Iman-Davenport correctie en Wilcoxon signed-rank tests bevestigden dat MOELIGA statistisch significant beter presteert dan alle 10 concurrenten.
• Kenmerkreductie: MOELIGA vond aanzienlijk kleinere subsets dan concurrenten (vaak een reductie van 50-80% in hoog-dimensionale datasets) terwijl de nauwkeurigheid behouden bleef of verbeterde.
• Generalisatie: De subsets geselecteerd door MOELIGA (geoptimaliseerd met een Decision Tree) presteerden consistent goed over verschillende andere classifiers (Random Forest, SVM, Naive Bayes, MLP), wat aantoont dat het algoritme classifier-onafhankelijke kenmerken selecteert.
• Efficiëntie: Hoewel MOELIGA meer rekentijd kost voor kleine datasets, is het voor zeer hoog-dimensionale problemen even efficiënt of zelfs efficiënter dan methoden die de gebruiker een subsetgrootte moeten laten specificeren, omdat het vermijdt dat men meerdere keren het algoritme moet draaien met verschillende subsetgroottes.

5. Betekenis en Conclusie

MOELIGA vertegenwoordigt een significante stap voorwaarts in multi-objectieve evolutionaire feature selection. Het lost het fundamentele compromis op tussen nauwkeurigheid en dimensionaliteit door een geavanceerde zoekstrategie te combineren met een geometrische regularisatie.

De belangrijkste implicaties zijn:

• Robuustheid: Het algoritme is minder gevoelig voor overfitting op specifieke classifiers dankzij de geometrische objectief.
• Automatisering: Het elimineert de noodzaak voor gebruikers om het aantal kenmerken handmatig te kiezen, wat een grote bron van suboptimale resultaten bij andere methoden is.
• Toepasbaarheid: Het is bijzonder effectief voor complexe, hoog-dimensionale problemen (zoals genomics en beeldherkenning) waar de interpretatie en efficiëntie van het model cruciaal zijn.

De auteurs erkennen wel dat de rekentijd hoger is dan bij simpele methoden voor zeer kleine datasets, en dat de prestaties kunnen dalen bij datasets met extreem weinig steekproeven ten opzichte van het aantal klassen. Toekomstig werk richt zich op adaptieve mechanismen voor de parameters en verdere parallelisatie.