Soccer Feature Madness

Im letzten Blog-Post haben wir Daten gesammelt, mit denen wir das Ergebnis der bevorstehenden WM vorhersagen wollen. Bevor wir diese Daten in einen Machine Learning Algorithmus gießen können, der uns dann auf magische Weise den neuen Fußball-Weltmeister präsentiert, fehlt noch ein wichtiger Schritt: Feature-Engineering.

Was ist Feature-Engineering

In klassischen Einführungsbeispielen zu Machine Learning (z.B. der Bestimmung von Immobilien-Preisen ) spielt Feature-Engineering keine wichtige Rolle. Es gibt eine vorgegebene, überschaubare Menge an Merkmalen (z.B. „Wohnfläche der Immobilie in qm“). Man muss nur eine mathematische Formel finden, die durch geschickte Kombination und Gewichtung der einzelnen Merkmale die Zielgröße möglichst gut vorhersagt. Machine Learning ist eine Möglichkeit, eine solche Formel zu finden.

Oft ist es aber so, dass die Menge der Features sehr groß und unüberschaubar ist. Ein Beispiel für ein solches hochdimensionales Problem ist die Bilderkennung. Fotos bestehen heute aus mehreren Millionen Pixeln. Um nun die Anzahl der Dimensionen zu reduzieren, verwendet man stattdessen abgeleitete Features . Ein gutes Beispiel für ein abgeleitetes Feature ist das Histogram eines Bildes, mit dem es z.B. möglich ist, Dokumente und Präsentationen von Fotografien zu unterscheiden .

Features für die WM

Während es in der Bildverarbeitung um Dimensionsreduzierung geht, haben wir bei unserer WM-Vorhersage das gegensätzliche Problem: Wir haben zu wenige Features. Die einzigen wirklich brauchbaren Informationen, die wir für alle Spiele in unserem Datensatz haben, sind die Kontrahenten, das Datum des Spiels und das Ergebnis des Spiels. Um mehr Features zu bekommen, kann man einfach mehr Daten sammeln. Zum Beispiel Spielort, die Aufstellung der Teams oder Informationen zu den einzelnen Spielern. Man kann auch die bestehenden Daten mit anderen Datenquellen verknüpfen.

FIFA-Rankings

Eine (hoffentlich guter) Indikator für die relative Stärke der Kontrahenten bei Fußball-Länderspielen ist die FIFA-Weltrangliste. Die Ranglisten werden monatlich veröffentlicht. Auf der FIFA-Homepage können alle vergangenen Ranglisten bis ins Jahr 1992 eingesehen werden. Mit einem kleinen R-Skript können nun die FIFA-Platzierung der Kontrahenten zum Zeitpunkt des Spiels zu ermittelt werden. Dabei leistet mapply gute Dienste. Im folgenden Histogramm sieht man die Verteilung von Siegen und Niederlagen abhängig vom Unterschied der FIFA-Platzierung der beiden Kontrahenten:

Statistik aus vergangenen Spielen

Die FIFA-Features sind durch die Hinzunahme externer Informationen entstanden. Tatsächlich verbergen sich aber auch in ursprünglichen Daten noch Informationen, die wir bisher nicht verwenden können. Durch die Datumsangabe ist es möglich, Spiele untereinander in Beziehung zu bringen. Intuitiv ist eine Mannschaft, die eine Siegesserie von zehn Spielen hinter sich hat, auch ein Favorit für das elfte Spiel. Ein abgeleitetes Feature ist eine Möglichkeit, dem Algorithmus diese Intuition „beizubringen“.

Die Features, die in dem Java-Projekt „League-Based-Features“ berechnet werden, basieren alle auf der Idee, dass vorhergehende Spiele gute Indikatoren für den Ausgang zukünftiger Spiele sind. Die berechneten Features sind in unserem GitHub-Projekt unter /2-compute-features/2-league-based/output/ zu finden. Folgende Features werden berechnet:

• b_last_X_games_points_average_weighted Gewichteter Durchschnitt der Punkte aus den letzten X Spielen. Gewichtet wird nach Position in der selbst berechneten Liga.
• b_last_X_games_goal_average_weighted Gewichteter Durchschnitt der geschossenen Tore aus den letzten >X Spielen. Gewichtet wird nach Position in der selbst berechneten Liga.
• b_last_X_days_points_average_weighted Gewichteter Durchschnitt der Punkte der letzten X Tage. Gewichtet wird nach Position in der selbst berechneten Liga.
• b_last_X_says_goal_average_weighted Gewichteter Durchschnitt der geschossenen Tore der letzten X Tage. Gewichtet wird nach Position in der selbst berechneten Liga.
• b_league_positions_points Punkte in der selbst berechneten Liga.

Graph Based Features

Das Projekt WM-Vorhersage ist ein Freizeitprojekt und als solches nutzt man natürlich jede Gelegenheit, neue Technologien auszuprobieren. Als ich die Liste der gesammelten Spiele und Ergebnisse zum ersten Mal sah, dachte ich sofort an einen Graphen. Ein Import-Skript für die Graphdatenbank Neo4J war schnell geschrieben.

Aus diesem Graphen lassen sich auch nützliche Features ableiten. Wieder bemühen wir unser Fußball-Expertenwissen: Wenn Deutschland gegen England gewonnen hat und Italien vor kurzem gegen England verloren hat, dann ist es doch wahrscheinlich, dass Deutschland auch gegen Italien gewinnt.

Technisch gesehen, suchen wir im Graphen mit allen Länderspielen die Pfade vom Knoten Deutschland zum Knoten Italien. Davon gibt es sehr viele. Deshalb einige Einschränkungen: Die maximale Länge der Pfade wird auf MAX_PATH_LENGTH begrenzt. Außerdem werden nur Spiele betrachtet, die maximal MAX_YEARS_BACK Jahre in der Vergangenheit liegen. Zusätzlich werden noch zwei Faktoren zur Gewichtung verwendet: Je größer PATH_LENGTH_WEIGHT gewählt wird, desto weniger stark werden lange Pfade gewichtet. Je größer TIME_WEIGHT gewählt ist, desto weniger stark werden lange zurück liegende Spiele gewichtet. Die berechneten Features sind unter der Bezeichnung b_graph_score_[MAX_YEARS_BACK]_[MAX_PATH_LENGTH]_[TIME_WEIGHT]_[PATH_LENGTH_WEIGHT] in der finalen Feature-Datei /2-compute-features/3-graph-based/output/games-with-graph-features.csv zu finden.

Summary

Daten einfach in Weka oder RapidMiner pumpen und hoffen, dass etwas sinnvolles herauskommt, reicht nicht aus. Machine Learning Algorithmen können helfen, interessante Zusammenhänge zu erkennen und auszunutzen. Das mächtigste Werkzeug bleibt aber weiterhin unser Verstand. Expertenwissen kann den Algorithmen in Form von abgeleiteten Features zur Verfügung gestellt werden.

Es bleibt die Frage, ob unsere berechneten Features tatsächlich so aussagekräftig sind, wie wir es hoffen. Dieser Frage werden wir in unserem nächsten Artikel auf den Grund gehen. Stay tuned!

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