Wer wird Weltmeister – Logistische Regression und Random Forests

Heute – rechtzeitig zum ersten Spiel der Fußball WM – wollen wir unserer Blog Serie zur Einführung in Data Science Methoden am Beispiel der Fußball WM mit einigen Vorhersagen fortsetzen.

Kurz zur Erinnerung: In den letzten Blog Posts hatten wir unseren Datensatz vorgestellt , die Frage untersucht ob Deutschland eine Turniermannschaft ist , dann die Feature Generierung beschrieben und schließlich hatten wir dann noch Features zur Vorhersage ausgewählt .

Logistische Regression

Logistische Regression ist einer der ältesten und am besten verstandenen Algorithmen den man für die Klassifikation verwenden kann. Ganz grob gesagt werden Parameter b0 … bN für eine Gleichung e^(b0 + b1x1 + … bNxN) berechnet (wo x1…xN die verschiedenen Feature sind), so dass die Wahrscheinlichkeit für die Klassenzugehörigkeit eines Elementes möglichst gut geschätzt werden kann. Logistische Regression ist weit verbreitet, schnell zu trainieren und auch vielfältig anpassbar – ein Nachteil ist allerdings, dass für die Anpassung große Erfahrung und Sachverstand notwendig ist. Ohne besonders darüber zu sprechen, hatten wir auch schon im letzten Post logistische Regression als Algorithmus für die Auswahl der Features verwendet (im letzten Teil bei der Backwards Stepwise Selection).

Der Code für den Aufbau und das Lernen eines logistischen Regressionsmodells ist in R sehr einfach (hier verwenden wir jetzt das einfache Modell mit nur den Features die wir ausgewählt hatten).

1trainData <- read.csv("soccerDataWithFeatures.csv",header=T,na.strings="-",sep=";")
2  testData <- read.csv("testData2.csv",header=T,na.strings="-",sep=";")
3  formula <- r_game_outcome_before_penalties ~ b_fifa_ranking_home + b_fifa_ranking_away + b_last_3_games_goal_average_home_team
4  testModel <- lrm(formula, data=trainData)
5  testPred <- predict(testModel, newdata = testData, type="fitted.ind")

Die Genauigkeit dieses Modells auf den Testdaten (hier den letzten 400 Spielen) ist – wie wir schon beim letzten mal gesehen haben – ca. 60% (und die konkreten Vorhersagen für die Gruppenspiele mit diesem Algorithmus sind hier ).

Random Forest

Bessere Ergebnisse versprechen wir uns von dem auf Entscheidungsbäumen aufsetzenden Random Forest Algorithmus – ein Verfahren, das allgemein für seine Genauigkeit und die Einfachheit der Anwendung geschätzt wird.

Bei Entscheidungsbäumen wird, wie der Name schon sagt, ein (Binär-)Baum aufgebaut, bei dem jeder Knoten mit einer Entscheidungsregel verknüpft ist. Für eine Vorhersage wird der Baum beginnend von der Wurzel durchlaufen. Bei jedem Knoten bestimmt die assoziierte Entscheidungsregel, ob der rechte oder der linke Teilbaum weiter durchlaufen wird. Der Endknoten bestimmt dann das Ergebnis der Vorhersage. Bei Random Forests werden viele verschiedene Entscheidungsbäume auf kleineren Teilen der Daten trainiert und für die Vorhersage zusammengefasst. Für eine detailliertere Erklärung von Entscheidungsbäumen und Random Forests sei an dieser Stelle auf die entsprechenden Wikipedia-Artikel verwiesen.

Zum Trainieren eines Random Forest Modells haben wir das R Package CARET verwendet. CARET erleichtert insbesondere die Evaluierung des Modells (z.B. durch 10-Fold-Cross-Validiation) und unterstützt bei der Suche nach guten Parametern für das Modell. Im Falle von Random Forests gibt es zum Beispiel den Parameter „mtry“, der angibt wie viele Features maximal in eine Entscheidungsregel (d.h. an einem Knoten) einfließen dürfen. Mit CARET kann man eine Liste möglicher Parameter vorgeben. Für jede Parameterkombination wird dann ein Modell trainiert und evaluiert. CARET wählt unter diesen Modellen automatisch das beste aus. Die Performance für unterschiedliche Parameterkombinationen kann auch gut in Diagrammen (siehe unten) dargestellt werden.

1library(caret)
2train(
3  r_game_outcome_before_penalties ~ b_fifa_ranking_home + b_fifa_ranking_away + ...
4  data=trainData,
5  method="rf",
6  trControl=trainControl(
7    method="repeatedcv",
8    number=10,
9    repeats=1),
10  tuneGrid=expand.grid(mtry=c(1,2,3,5,7)),
11  verbose=FALSE)

1Random Forest 
2 
32154 samples
4 105 predictors
5   2 classes: 'AWAY_WIN', 'HOME_WIN' 
6 
7No pre-processing
8Resampling: Cross-Validated (5 fold, repeated 1 times) 
9 
10Summary of sample sizes: 1701, 1700, 1701, 1701, 1701 
11 
12Resampling results across tuning parameters:
13 
14  mtry  Accuracy  Kappa  Accuracy SD  Kappa SD
15  1     0.751     0.468  0.0224       0.0487  
16  2     0.754     0.479  0.0209       0.0442  
17  3     0.757     0.487  0.0208       0.0452  
18  5     0.758     0.49   0.024        0.0506  
19  7     0.761     0.496  0.0247       0.0533  
20 
21Accuracy was used to select the optimal model using  the largest value.
22The final value used for the model was mtry = 7.

Ein großer Vorteil von Random Forests ist, dass die Feature-Selection quasi in den Algorithmus integriert ist, da zum Trainieren der einzelnen Entscheidungsbäume immer nur eine Teilmenge der verfügbaren Features verwendet wird. Trotzdem macht es auch hier Sinn, die Liste der Features etwas einzugrenzen. Machine-Learning Algorithmen haben grundsätzlich Probleme damit, wenn die Trainingsdaten redundante Features enthalten. Im Falle unserer Fußball-Features zum Beispiel das Feature „b_fifa_ranking_difference“ linear abhängig von „b_fifa_ranking_home“ und „b_fifa_ranking_difference“. Das Random-Forest Modell wird deshalb auch auf zwei Teilmengen der Features trainiert: Eine Feature-Teilmenge enthält die absoluten Werten für FIFA-Ranking (zweite Zeile im Diagramm), Liga-Position, usw. Die andere Teilmenge enthält nur die Differenz-Features (dritte Zeile).

Um das Modell weiter zu optimieren, werden auch die Trainingsdaten nochmal unter die Lupe genommen. Beim Sammeln der Daten haben wir alles genommen, was wir kriegen konnten: WM-Spiele, EM-Spiele, Qualifikation, Endrunde, Africa Cup, Ostasienmeisterschaft, Freundschaftsspiele, … Nun stellt sich die Frage, ob diese bunt gemischten Daten wirklich geeignet sind, um ein Modell zur Vorhersage der WM zu finden. Bei einer WM treffen Mannschaften aufeinander, die ähnlich stark sind. Bei Freundschaftsspielen ist der Unterschied zwischen Mannschaften dagegen oft riesig. Eine Gefahr könnte sein, dass Spiele zwischen extrem unterschiedlichen Mannschaften (wie z.B. Deutschland – Faröer Inseln) das Ergebnis verzerren und die Qualität des WM-Modells eher verschlechtern als verbessern. Um das zu bestätigen (oder zu widerlegen) verwenden wir die Spiele der WM 2010 als Testdaten und trainieren das Modell einmal mit dem kompletten Datensatz inklusive Freundschaftsspiele (erste Spalte), einmal nur mit EM- und WM-Endrundenspielen (zweite Spalte) und letztendlich mit EM- und WM-Spielen inklusive Qualifikationsspielen (dritte Spalte).

Die Diagramme spiegeln die Performance der trainierten Modelle wieder. Als Performance-Maß verwenden wir Accuracy, d.h. der Anteil korrekt klassifizierter Samples. Die Accuracy ist auf der Y-Achse abgetragen. Auf der X-Achse der Diagramme ist der Wert des Parameters „mtry“ abgetragen. Die schwarze Linie spiegelt die Accuracy der Modelle auf zufälligen Testdaten wieder (10-Fold Cross Valication). Die rote Linie ist die Accuracy, die das jeweils beste Modell (d.h. des Modells mit optimalem „mtry“ Parameter) auf den WM-2010 Testdaten erreicht hat.

Wie man sehen kann, wurden unsere Vermutungen größtenteils bestätigt. Die Modelle der ersten Spalte (trainiert mit allen verfügbaren Daten) schneiden zwar auf einem zufällig gewählten Testdatensatz sehr gut ab, haben aber Probleme mit der Vorhersage der WM 2010. Dagegen sind die Vorhersagen der Modelle der dritten Spalte (trainiert mit den EM- und WM-Spielen inkl. Qualifikation) sowohl bei zufälligen Testdaten als auch bei dem WM-2010 Datensatz recht gut. Die Modelle der zweiten Spalte (trainiert nur mit EM- und WM-Endrundenspielen) schneiden ziemlich schlecht ab, was wahrscheinlich daran liegt, dass der Datensatz einfach zu klein ist.

Ebenso können wir bestätigen, dass ein Trainieren mit allen verfügbaren Features wenig Sinn macht. Die Modelle der ersten Zeile (trainiert mit allen Features) sind nicht besser als die anderen Modell. Bei der Vorhersage der WM-2010 schneiden die Modelle der zweiten und dritten Zeile sogar besser ab.

Vorhersage

Wir haben verschiedene Modelle trainiert und die Performance verglichen. Was bleibt ist die Anwendung auf neue, nicht klassifizierte Daten. Erster Kandidat: Das Eröffnungsspiel der WM 2014 (das in wenigen Stunden beginnt). Für dieses Spiel und die weiteren Vorrundenspiele haben wir die nötigen Features (z.B. FIFA-Platzierung) berechnet. Mit folgendem R-Schnipsel wird ein Modell auf die neuen Daten angewandt und wir erhalten eine Vorhersage:

1wm2014 <- subset(data, b_date=="2014-06-12")
2prediction = predict(
3  test_results$em_and_wm_with_qualification.all.notdiff.randomForest$fitted, 
4  newdata=wm2014)
5result <- cbind(wm2014[,c("b_team_home","b_team_away")], prediction)

1b_team_home b_team_away prediction
2...
34142         BRA         HRV   HOME_WIN
4...

Brasilien wird also das Eröffnungsspiel gewinnen. Wer hätte das gedacht;-) Aber wie sicher ist diese Vorhersage? Bei vielen Klassifizierungsalgorithmen kann man zusätzlich zu einem binären (HOME_WIN oder AWAY_WIN) Klassifikationsergebnis einen Wert ermitteln, der angibt, wie wahrscheinlich das prognostizierter Ergebnis ist.

1prediction = predict(
2  test_results$em_and_wm_with_qualification.all.notdiff.randomForest$fitted, 
3  newdata=wm2014,
4  type="prob")

1b_team_home b_team_away HOME_WIN AWAY_WIN
24142         BRA         HRV    0.632    0.368
34153         DEU         GHA    0.792    0.208
44154         DEU         PRT    0.452    0.548
54181         USA         DEU    0.562    0.438

Das ist nun schon wesentlich aussagekräftiger. Unser Algorithmus ist sich ziemlich sicher, dass Brasilien gewinnen wird. Dagegen ist sich der Algorithmus beim Spiel Deutschland – USA nicht so sicher. Die Chancen stehen 56% zu 44%. Da wollen wir mal das beste hoffen. Die Vorhersagen für die restlichen Gruppenspiele gibt es übrigens (wie den kompletten R-Code) auf unserem GitHub-Projekt soccer-prediction-2014 .

Und wer wird nun Weltmeister?
Diese Frage beantworten wir im nächsten Artikel. Jetzt gehen wir erstmal Fußball gucken…

Autoren

Michael Lex und Valentin Zacharias

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