Entscheidungsbäume vs. Random Forest vs. Boosting

Entscheidungsbäume sind eine einfache Möglichkeit, Klassifikations- oder Regressionsprobleme verständlich abzubilden. Der Nachteil ist die meist schlechtere Performance gegenüber moderneren Machine Learning Ansätzen.

Dieser Performancenachteil kann durch die Idee des Ensemblemodellierens und der darauf Basierenden Methode des Random Forest bzw. des Boostings aufgeholt werden. Das Ergebnis sind stabile mathematische Modelle.

Einfacher Entscheidungsbaum

Mit Entscheidungsbäumen ist es nicht nur möglich Klassifikationen durchzuführen. Sie können auch für Regressionsprobleme verwendet werden. Nachfolgend werden Daten eines Einzelhändlers verwendet, mit dem Ziel die Kundenanzahl pro Tag vorherzusagen. Dies stellt somit ein Regressionsproblem dar.

Der Entscheidungsbaum wurde für die Abbildung mit einem reduzierten Featuresatz trainiert. Die erste Ebene in Abbildung 1, ist die Wurzel mit 100% der Datensätze. Nach dem ersten Split entstehen zwei Nodes. Im Beispiel reduziert die Information, dass ein Shop am Sonntag geöffnet ist, den Anpassungsfehler am stärksten. Somit wird diese für den ersten Split verwendet. Der zweite Split wird über den Wochentag durchgeführt. Die obere Zahl in den Nodes ist die durchschnittliche Kundenzahl der Datensätze eines Blatts. Blätter sind im Beispiel die Nodes mit den Nummern [4,5,6,7]

Abbildung 1: Links: Klassische Tree Darstellung Rechts: Perspective Plot des Trainings Ergebnis mit Kundenanzahl auf der vertikalen Achse

Bei der Betrachtung des Entscheidungsbaums stellt sich die Frage, wie der Algorithmus entscheidet, welche Variable für den nächsten Split verwendet und wo auf der Skala dieser gesetzt werden soll.

Der Ansatz basiert auf einer Top-down, greedy Methode. Die Grundgesamtheit der Daten wird in einem initialen Split getrennt. Im nächsten Schritt wird wieder ein Split durchgeführt, dieser unabhängig von der Information, ob eine Änderung des vorausgegangenen Splits eine Auswirkung auf das Gesamtergebnis hat. Die Optimierung wird mithilfe einer Loss-Funktion durchgeführt.

\sum_{j=1}^{J} \sum_{i\in R_j}(y_i-\hat y_{r_j})^2

Diese ist die Summe der quadratischen Abweichungen eines Messwerts i zum Mittelwert der Region j, welchem der Messwert zugewiesen wird. Das Ziel ist die bestmögliche Minimierung der Abweichung in jedem Schritt. Die Regionen werden durch die Blätter des Entscheidungsbaumes festgelegt. Im oben dargestellten Beispiel sind dies die Nodes (4,5,6,7).

Für die Erhöhung der Geschwindigkeit wird in jedem Schritt nur ein Split pro Blatt durchgeführt (soweit Sinnvoll). Somit kann die bestmögliche Reduktion der Loss Funktion pro Split für jedes Feature an jedem Blatt lokal bestimmt werden. Der Split erfolgt dann jeweils über das Feature, welches die stärkste Reduktion der lokalen Loss Funktion bedingt. Das Verfahren wird als Binary Splitting bezeichnet.

Das Problem dieser Methode ist eine mögliche Überanpassung (Overfitting) an den Trainingsdatensatz. Um dem Modell eine bessere Generalität zu verleihen, wird das Pruning (Zurückschneiden) eingeführt. Die Methode basiert auf dem Cost complexity pruning und der Cross-Validation.

Das Cost complexity pruning ist ein Verfahren, um den Baum intelligent zurückzuschneiden. Im Wesentlichen werden die Splits nach der Reduktion der Loss Funktion sortiert. Über einen Threshold wird festgelegt, wie viele Schnitte beibehalten werden.

Die Cross-Validation ist ein Verfahren, bei denen der Trainingsdatensatz in k Teile geschnitten wird. Der Baum wird mithilfe der Daten von k-1 Teilen zurückgeschnitten. Mit dem übrig bleibenden Datensatz wird die Loss-Funktion berechnet.

Das Pruning wird mithilfe der beiden Methoden wie folgt durchgeführt:

  1. Im ersten Schritt wird der Baum voll ausgebaut, um die maximal mögliche Reduktion der Loss-Funktion zu erreichen
  2. Reduktion der Baum Komplexität durch cost complexity pruning
  3. Durchführen einer K-fold cross-validation. Bestimmen des optimalen \alpha.
  4. Ausgabe des reduzierten Baums, welcher nach der Cross-Validation am besten abgeschnitten hat.

Die Vorhersage von Kundenzahlen pro Tag mithilfe des oben trainierten Baumes erfolgt durch:

  1. Aufteilen des Vorhersagedatensatzes in Regionen, basierend auf den Splitschritten im Entscheidungsbaum
  2. Zuweisen der durchschnittlichen Kundenzahl des Blatts, welche zur jeweiligen Gruppe gehört

Vorteile des Entscheidungsbaums

Welche Vorteile bietet der Entscheidungsbaum gegenüber einem linearen Vorhersageverfahren? Besitzen die Daten einen linearen Zusammenhang, wird das lineare Verfahren eine bessere Vorhersagegüte haben, weil es die zugrundeliegende Struktur abbildet. Ist der Zusammenhang zwischen den Variablen hingegen nichtlinear, wird der Entscheidungsbaum die besseren Ergebnisse liefern.

Im Vergleich zu komplexeren nichtlinearen Methoden, schneidet der einfache Entscheidungsbaum in Bezug auf die Vorhersagegüte, schlechter ab. Um die Methode zu verbessern, wurden Erweiterungen wie der Random Forest und das Boosting entwickelt, welche Modelle mit einer besseren Generalität liefern.

Random Forest

Der einzelne Entscheidungsbaum bringt das Problem hoher Varianz mit sich. D.h. wird ein Baum auf einer Hälfte der Trainingsdaten trainiert und ein Baum auf der anderen Hälfte, können diese sehr unterschiedlich aussehen. Dies hat u.a. negative Auswirkungen auf die Generalität der Vorhersage eines Entscheidungsbaumes.

Für ein stabileres Vorhersageergebnis kann die Methode des Baggings verwendet werden. Dabei werden b Bäume auf durch Bootstraping erzeugten Samplen der Trainingsdaten trainiert. Diese Bäume f*b(x) werden über einen Mittelwert kombiniert.

f_{bag}(x) = \frac{1}{B}\sum_{b=1}^{B}f^{*b}(x)

Ist in den Daten ein sehr starker Prädiktor enthalten, wird dieser in jedem Baum einen starken Einfluss haben. Somit kommen Variablen mit einem weniger starken Einfluss, erst in unteren Baumebenen zum Tragen, mit der Konsequenz das diese beim Pruning weggeschnitten werden könnten. Um diesem Entgegenzuwirken wird in jedem Trainingsschritt nur ein Teil der Prädiktoren zugelassen. Die Anzahl der zugelassenen Prädiktoren wird z.B. auf m=\sqrt{p}, wobei p die Anzahl an Features im Datensatz ist, beschränkt. Es gilt weiterhin die Regel, dass im nächsten Split nur Features Verwendung finden, welche nicht im Split vorher verwendet wurden.

Boosting

Das Boosting Verfahren nutzt die Mechanismen des Random Forest. Der Unterschied liegt in der Durchführung des Baggings. Beim Random Forest wird der Mittelwert durch unabhängige Bäume erzeugt. D.h. alle Bäume werden unabhängig voneinander trainiert. Beim Boosting wird ein sequentielles Training verwendet. Die Bäume werden hierbei mit dem Vorwissen aus dem letzten trainierten Baum erstellt. Des Weiteren werden keine Bootstrap Samples für das Training verwendet, sondern modifizierte Versionen des Originaltrainingssatzes.

Das Training läuft wie folgt ab:

  1. \hat f(x) und die Residuen r_i = y_i
  2. Wiederhole für b = 1,2,…,B
    1. Erstelle ein Baum \hat f^b mit d Splits (d+1 Blätter) basierend auf den Trainingsdaten (X,r)
    2. Aktualisieren des Modells \hat f mit einem durch \alpha > 0 reduzierten Schritt \hat f(x) \leftarrow \hat f(x) + \lambda \hat f^b(x)
    3. Aktualisieren der Residuen r_i \leftarrow r_i - \lambda \hat f^b(x)
  1. Ausgabe des Boosting Modells\hat f(x) = \sum_{b=1}^{B} \lambda \hat f^b(x()

Das Vorwissen aus dem letzten Trainingsschritt wird über die Residuen weitergetragen, da der Baum b+1 nur noch die Residuen erklären muss, welche durch die Bäume 1,…,b nicht beschrieben wurden.

Der Algorithmus wird über 3 Parameter spezifiziert

  • B als die Anzahl an Trainingsschritten. Der Parameter wird durch Cross-Validation bestimmt.
  • \lambda als die Lernrate pro Schritt
  • d als die Anzahl Splits pro Baum.

Feature Relevanz

Bei einem einfachen Entscheidungsbaum ist es noch relativ einfach, die Relevanz der einzelnen Features zu bestimmen. Bei einem Random Forest oder Boosting Algorithmus ist dies durch die Komplexität schwierig.

Eine mögliche Lösung ist, die Summe der Reduktionen der Loss-Funktion über alle Splits eines Features aufzuaddieren. Diese können dann relativ zum Feature mit der größten Loss-Reduktion dargestellt werden.

Abbildung : Variablenwichtigkeit für die Vorhersage von Kundenzahlen

Benchmark der Methoden

Nachdem die Methoden beschrieben wurden, ist es Zeit einen Benchmark zwischen diesen zu erstellen. Als Maß für die Modellgüte wird der Root Mean Square Prediction Error (RMSPE) verwendet.

../../../Desktop/Screen%20Shot%202017-12-22%20at%2010.25.2

Abbildung : Vorhersage für eine Filiale. In Grau die tatsächlichen Besuchszahlen.

Dies ist der Vorhersagefehler auf einem Validierungsdatensatz, welcher nicht in das Training des Modelles einfließt. Der Test soll ein grobes Gefühl für die Leistung der Algorithmen geben, keine detaillierte Analyse. Das Ziel ist wieder die Vorhersage der Kundenbesuche pro Tag für einen Zeitraum von vier Wochen.

Entscheidungsbaum Random Forest Boosting
Parameter Maximale Baumtiefe: 10
Split Treshhold: 0.1
Anzahl Trees: 500
Split Treshhold : 0.1
Maximale Baumtiefe: 10
Anzahl Trees: 500
Updaterate: 0.015
RMSE 252.04 33.14 63.98
RMSPE 276.40 79.05 66.79

Für einen differenzierteren Benchmark müssen verschiedene Parameterkombinationen für die Algorithmen getestet werden. In den Benchmark würden dann jeweils die Modelle mit dem besten RMSPE eingehen.

Zusammenfassung

Die Versuche und der mathematische Hintergrund zeigen, dass Verfahren wie Random Forest und Boosting stabile Vorhersageergebnisse erzielen. Jedoch sind die Modelle recht schwer verständlich. Über die Feature Wichtigkeit ist es möglich, diese Komplexität einzudämmen.

Trotz der komplexeren Algorithmen wird der  einfache Entscheidungsbaum weiterhin seine Existenzberechtigung behalten. Nicht als Vorhersageinstrument, mehr im Umfeld der explorative Datenanalyse, wo es vor allem um das Datenverständnis geht.

Getagged mit: , , , , , , , , ,

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

*

*