Wer wird Weltmeister – Feature Selection

Dies ist der dritte Beitrag in unserer Blog Serie zur Einführung in Data Science Methoden am Beispiel der Vorhersage der Fußball WM. Einleitung und ersten Teil findet sich hier und hier .

Kurz zur Erinnerung: Das Ergebnis beim letzten Mal war eine Datenbank mit Spielen von Nationalmannschaften – mit Ergebnissen und verschiedenen (teilweise generierten) Features von denen wir denken, dass sie für die Vorhersage nützlich sein könnten.

Heute soll es um Feature Selection gehen – die Auswahl von Features für die Verwendung in Vorhersagemodellen.

Feature Selection – Warum eigentlich?

Bei den Features hier (und im allgemeinen) ist klar, dass es immer solche geben wird die für eine konkrete Vorhersageaufgabe irrelevant sind (d.h. die einfach keine Vorhersagekraft haben). Ebenso wird es redundante geben (d.h. der gesamte Beitrag den ein Feature für die Vorhersage liefern kann ist auch über andere Features zugänglich).

Die Graphik oben zeigt ein Beispiel für ein irrelevantes Feature – hier die Anzahl der Zuschauer im Stadium als Feature für die Vorhersage des Spielergebnisses. Die Graphik nennt sich Bean Plot und ist wie folgt zu verstehen: für jede Klasse (in diesem Fall sind die Klassen: Heimmannschaft gewinnt, Unentschieden und Auswärtsmannschaft gewinnt – alles nach 90 Minuten) ist ein Graph gezeigt. Dieser Graph zeigt die Verteilung der Werte in der jeweiligen Klasse – dabei zeigen die grauen Striche an wo genau Werte sind und die blaue Form ist eine daraus geschätzte Dichtefunktion. Die Rote Linie ist der Durchschnitt pro Klasse, die gepunktete Linie (hier von der roten verdeckt) der Durchschnitt über alle Klassen hinweg. Mit einem solchen Bean Plot kann man schnell eine Übersicht über die Verteilung der Werte in den Klassen verschaffen und (über die Striche) auch eine Idee von Ausreißern und seltsamen Werten bekommen – wie hier dem einem Spiel mit angeblich ca. 180.000 Zuschauern (was aber kein Fehler ist – dieses Spiel der WM 1950 zwischen Uruguay und Brasilien wurde tatsächlich von so vielen Menschen besucht und gilt noch heute als die meistebesuchte Teamsport Veranstaltung die jemals stattgefunden hat . Das die Anzahl der Zuschauer nicht zu Vorhersage taugt mussten auch die – in erster Linie Brasilianischen – Zuschauer zu ihrer großen Verzweiflung feststellen, als Uruguay gewann und Weltmeister wurde. Es wird gesagt, dass diese Schmach der Grund dafür war, dass die Brasilianer ihre bis dahin übliche Weiße Trikot Farbe zu Gelb gewechselt haben).

Trotzdem stellt sich aber die Frage warum man nicht einfach alle Features nimmt und es dem verwendeten Lernalgorithmus überlässt diese entsprechend zu gewichten.

Üblicherweise werden drei Gründe genannt:

• Interpretier- und Anwendbarkeit: Eine Reduktion der Anzahl der Features macht das resultierende Modell einfacher zu verstehen und eventuell in der Anwendung einfacher und günstiger (z.B. wenn jedes Feature das Ergebnis eines separaten Bluttests ist der nicht automatisch durchgeführt wird, dann macht es einen großen Unterschied ob 30 oder 3 Tests für eine gute Vorhersage benötigt werden und eine ordentliche Vorhersage mit 3 Tests ist eventuell sogar deutlich wertvoller als eine richtig gute die nach 30 Tests zu spät kommt um noch etwas zu unternehmen).
• Verbesserte Generalisierung: In einem gegebenen Training Set werden auch eigentlich irrelevante Features schon rein durch Zufall eine gewissen Nutzen für die Vorhersage haben – ein Nutzen der sich im eigentlich Einsatz mit neuen Daten dann in das Gegenteil umkehrt (ein als Overfitting bekanntes Phänomen). Entfernt man vermutlich irrelevante features, so verliert man damit zwar ein wenig Genauigkeit auf den Trainingsdaten, man gewinnt jedoch in der eigentlichen Anwendung.
• Skalierbarkeit: Für große Datenmengen und eine hohe Anzahl von Features kann man durch die Reduktion der Anzahl der Features auch einen relevanten Geschwindigkeitsgewinn erzielen.

Zu diesen übliche Gründen möchte ich noch drei Ergänzen

• Feature Refinement: Über die hier beschriebenen Methoden kann man ein Verständnis für die Stärken und Schwächen der Feature entwickeln – dies erlaubt Feedback zurück ins Feature Engineering und vielleicht die Generierung von neuen / kombinierten / transformierten Features die besser funktionieren.
• Algorithmische Notwendigkeit: Einige Verfahren (wie z.B. Regression) können nicht (oder kaum) damit umgehen, wenn die Anzahl der Features nicht (deutlich) geringer ist als die Anzahl der Trainingsinstanzen (was aber in der Praxis nicht immer der Fall ist). Hier ist dann eine Reduktion der Anzahl der Features unumgänglich.
• Curse of Dimensionality: Sehr hochdimensionalen Problemen (d.h. solche mit sehr vielen Features) haben komische mathematische Eigenschaften bei denen unsere Intiution versagt und viele Algorithmen (wie insb. Nearest Neighbor) schlecht funktionieren – hier ist dann eine Reduktion der Features an sich wünschenswert.

Vorgehen

Im Prinzip gibt es vier verschiedenen Arten des Vorgehens:

• Filter/Proxy Based: Man berechnet Eigenschaften der Features die deren Relevanz und/oder Redundanz beschreiben (z.B. die Korrelation der Features untereinander und zwischen Features und Zielvariable). Ein Beispiel hierfür betrachten wir noch in diesem Artikel.
• Subset Selection: Hier wird ein Lernalgorithmus automatisch mit vielen verschiedenen Teilmengen der Features ausprobiert und darüber die beste Teilmenge gesucht. Bei sehr kleinen Problemen kann dafür jede mögliche Teilmenge (‚Best Subset‘) probiert werden, üblicherweise wird jedoch eine Suchstrategie verwendet die das Problem schneller lösbar macht (‚Forward Selection‘ oder ‚Backward Selection‘). Ein Beispiel ist am Ende dieses Artikels beschrieben.
• Embedded: Einige Algorithmen wie Lasso, Ridge Regression, Decision Trees und Random Forest beinhalten eine Reduktion der Features.
• Dimensionality Reduction: Letztlich lässt sich noch mit Verfahren wie Principal Component Analyses aus den Features eine geringere Anzahl neuer Features berechnen, die möglichst viel der ursprünglichen Information beinhalten.

Proxy Based Feature Selection

Hier wollen wir Features auf Basis von Proxies die ihre Relevanz oder Unabhängigkeit/Redundanz erfassen, auswählen.

Ein einfaches Instrument für diese Zwecke ist die Korrelation zwischen Feature und Ergebnis (das wir hier dann numerisch als Zahl verstehen – also z.B. -1 für Heimmannschaft gewinnt, 0 für unentschieden und +1 für Auswärtsmannschaft gewinnt). Macht man das für diesen Datensatz, so sind die besten Features (in Absteigender Reihenfolge) 1) der Unterschied im FIFA Ranking zwischen den Gegnern, 2) der Unterschied in FIFA Punkten zwischen den Teams) und 3) der Unterschied zwischen der Tordifferenz aus den letzten 10 Spielen der beiden Mannschaften – selbst die Buchmacher Quoten folgen erst später.

Mit diesen Korrelationen kann man nun eine Teilmenge der Features bestimmen – z.B. einfach über die Anzahl der Features die man nehmen möchte, eine minimale Korrelation oder über Cross-Validierung d.h. man testet Modelle mit den ersten N Features jeweils auf den Testdaten und wählt das Modell das am besten funktioniert.

Zuletzt noch eine Darstellung dieses Vorgehens im Bild: gezeigt ist die Korrelation zwischen (einem Teil der) Features und auch dem Spielergebnis (die Zeile ganz oben und die Spalte ganz rechts). Sehr gut sehen kann man sowohl den Zusammenhang zwischen Feature und Spielergebnis, wie auch die Korrelation der Features untereinander (eine hellere Farbe zeigt jeweils eine größere Korrelation).

Offensichtlich sind die Probleme in diesem Vorgehen: die Korrelation muss nicht vorhersagen wie gut sich ein Feature im Rahmen eines konkreten Algorithmus zur Vorhersage eignet und insbesondere wird die Redundanz nicht betrachtet (z.B. würde man erwarteten, dass es zwischen FIFA Punkt unterschied und FIFA Ranking Unterschied wieder eine große Korrelation gibt und das vielleicht eines dieser Features ausreichen würde. Auch dafür gibt es wieder Lösungen, jedoch geht das etwas über den Rahmen dieses Blog Posts hinaus.

Subset Selection

Hier wollen wir nun Beispielsweise zeigen wie man eine Reduktion von Features direkt mit Hilfe des verwendeten Klassifikationsalgorithmus durchführen kann. Das Vorgehen (‚Stepwise Backward Selection‘ genannt) ist das Folgende

1. Trainiere ein Modell mit allen verfügbaren Features auf Trainingsdaten
2. Probiere aus welches einzelne Feature du aus dem Modell entfernen kannst, so dass die Leistung auf den Trainingsdaten am wenigsten abnimmt. Merk Dir dieses Modell
3. Nimm das Modell was Du Dir eben gemerkt hast und gehe wieder zu Schritt 2 – bis am Ende nur noch ein Feature da ist
4. Probiere die verschiedenen in Schritt 2 gemerkten Modelle (wir haben ja eines mit einem Feature, eines mit zwei, eines mit drei usw) auf den Testdaten aus und wähle das, das die beste Performance zeigt.

Oder in R (hier nur verkürzt für den Kernschritt 2 – der komplette Code wäre etwas lang):

1step <- function(allFeatureNames,dataFrame) {
2  bestAccSeen <- 0
3  for (featureNameToTest in allFeatureNames) {
4    currentFeatureNames <- allFeatureNames[-which(allFeatureNames==featureNameToTest)]
5    formulaToTest <- makeFormula(currentFeatureNames)
6    testModel <- lrm(formulaToTest, data=dataFrame)
7    currentAcc <- evaluateModel(testModel,dataFrame)
8    if (currentAcc > bestAccSeen) {
9      bestAccSeen <- currentAcc
10      bestRemainingFeatureNames <- currentFeatureNames
11      bestModel <- testModel
12    }
13  }
14  return(list(bestAccSeen, bestRemainingFeatureNames,bestModel))
15}

Bei der Anwendung auf unseren Anwendungsfall bekommt man das Folgende Ergebnis:

Dargestellt ist die Genauigkeit (Anteil der Korrekt vorhergesagten Klassen) für die jeweils besten Modelle mit 1..71 Features (die Buchmacherquoten habe ich hier nicht mit verwendet). Die rote Linie zeigt die Leistung auf den Trainingsdaten (wie zu erwarten nimmt diese im großen und ganzen mit der Anzahl der Features zu), die grauen Punkte jeweils die Genauigkeit aller in einem Schritt betrachteten Modell. Die blaue Linie zeigt die Leistung auf den Testdaten – hier sieht man, dass das die maximale Genauigkeit eigentlich schon mit den richtigen 3 Features erreicht wird. Das Modell mit 3 Features wäre dann wohl auch das was man verwenden würde (oder sogar das mit 2, da der Unterschied zwischen diesen nicht statistisch signifikant ist und man in so einem Fall das einfachere Modell bevorzugen sollte).

Die auf diesem Weg ausgewählten Features sind dann:

1r_game_outcome_before_penalties ~ b_fifa_ranking_home + b_fifa_ranking_away + 
2    b_last_3_games_goal_average_home_team

Was nun aber rauskommt wenn man dieses Modell auf den Daten trainiert und auf die WM anwendet, damit beschäftigen wir uns im nächsten Blog Post.

Weitere Artikel der Data Analytics Serie

Teil 1 – Daten sammeln und bereinigen
Teil 2 – Ist Deutschland eine Turniermannschaft?
Teil 3 – Feature Engineering
Teil 4 – Feature Selection
Teil 5 – Logistische Regression und Random Forest
Teil 6 – Die Heimspielproblematik und Vorhersagen für die KO-Runde