Unterschiede zwischen Decision Tree, Random Forest und Boosting Algorithmen

Wer sich mit dem Thema Data Science beschäftigt kommt sehr schnell auf Begriffe wie z.B. Decision Trees, Random Forest und verschiedene Boosting Algorithmen ( AdaBoost, lightGBM, XGBoost). Dabei ist oft unklar was das Prinzip hinter diesen Algorithmen ist und worin diese sich unterscheiden. Das möchte ich gerne versuchen in diesem Artikel zu erklären.

Decision Trees sind der Einstieg in Machine Learning Verfahren. Oft beginnt man den Einstieg mit einfachen Methoden wie einer Linearen Regression. Als nächstes werden Decision Trees oder ein Random Forest Algorithmus eingeführt. Allerdings wird häufig nicht erklärt was die Prinzipien hinter diesen Algorithmen sind. Also was ist der Nachteil von Decision Trees gegenüber Random Forest Algorithmen. In dem Artikel werden wir deshalb folgende Fragen beantworten:

  • Was ist ein Decision Tree?
  • Wie grenzen sich baumbasierte Algorithmen von anderen Algorithmen ab?
  • Was bedeutet Bagging oder Boosting?
  • Was ist ein Random Forest Algorithmus?
  • Was ist der XGBoost Algorithmus?



Was ist ein Decision Tree?

Nun was ist ein Decision Tree oder zu Deutsch: „Entscheidungsbaum“? Im Prinzip stellt ein Entscheidungsbaum alle möglichen Entscheidungen dar, die man in einer Umgebung treffen kann. Dabei werden alle Entscheidungen in Form eines Baums dargestellt. Man steht dabei immer vor zwei Entscheidungsoptionen. ( Gehe ich den linken oder den rechten Pfad). In dem Bild lässt sich ein einfacher Entscheidungsbaum nachvollziehen. Wichtig dabei: In dem Beispiel ist der Entscheidungsbaum nur als Symbolbild eingefügt und basiert nicht auf echten Daten.

Entscheidungsbaum Symbolbild
Beispiel Entscheidungsbaum [basiert nicht auf echten Daten]
Diese Entscheidungsbäume besitzen mehrere große Vorteile im Bereich Data Science.

  1. Sie lassen sich sowohl für Regressionen wie auch für Klassifikationen verwenden
  2. Sie lassen sich sehr schnell berechnen
  3. Sie liefern relativ gute Ergebnisse
  4. Sie lassen sich gut nachvollziehen.

Die Decision Tree Algorithmen generieren solche Entscheidungsbäume indem sie für jedes Feature die Aufteilung mit der größten Entropie, d.h. den größten Informationsgehalt, ermitteln. Also welche am besten die Gruppe in Untergruppen einteilt. Wer wissen will, wie genau das funktioniert dem empfehle ich die Kurse von Prof. Dr. Wil Van Der Aalst „Process Mining: Data Science in Action“ auf Coursera.org. Hier werden auch die statistischen Hintergründe zu diesen Entscheidungsbäumen sehr gut erklärt. Außerdem wird in dem Kurs vieles zum spannenden Thema Process Mining erläutert, was ebenfalls ein sehr spannendes Thema in der Data Science ist.

Also: Decision Trees hören sich ziemlich cool an oder? Aber leider haben Sie auch ein paar Schwächen.
So sind diese Algorithmen sehr anfällig für Varianz in den Daten. Kleine Änderungen in den zugrunde liegenden Daten führen zu großen Änderungen in den Ergebnissen.

Was sind die Unterschiede zu anderen Algorithmen?

Es gibt sehr viele weitere populäre Supervised-ML Algorithmen. Dazu gehören unter anderem:

  • Lineare Regression: Eignet sich für Daten bei denen ein linearer Zusammenhang zwischen der vorherzusagenden Variablen (Abhängige Variable) und den Features (unabhängige Variablen) besteht.
  • Support Vector Machines: Eignet sich für die Vorhersage von Daten wo die Trainingsmenge relativ gering ist. Gleichzeitig eine sehr große Anzahl von Features vorhanden ist.
  • K-Nearest Neigbours: Sehr einfaches ML Model – die Anzahl der Nachbarn ( K) die für jeden Datenpunkt ermittelt werden, sollte mit viel Bedacht gewählt werden. Bei großen Datenmengen sind die Berechnungskosten sehr hoch.
  • Decision Trees: Eignet sich sowohl für Regressionen wie auch Klassifikationen. Anfällig für Varianz. Relativ hohe Gefahr von Over-Fitting.
  • Naive bayes: Funktioniert auf relativ geringen Datenmengen. Bedient sich sich des Naive Bayes Theorems
  • Neural Networks: Benötigt relativ große Datenmengen. Bei hoher Komplexität lässt sich das Modell nur schwer nachvollziehen. Hohe Berechnungskosten.

Das ist natürlich nur ein sehr kurzer Abgleich und zu den jeweiligen Algorithmen gibt es noch viel mehr zu Wissen und Ich werde darauf eventuell in späteren Blogbeiträgen nochmal darauf eingehen. Hier sollte das erst einmal für einen ersten Überblick reichen.




Decision Trees, Bagging und Boosting

Bagging, Boosting? Was ist denn das jetzt? Ich will doch was über Random Forest Algorithmen wissen!

Ja das stimmt aber um Random Forest Algorithmen zu verstehen bzw. den Unterschied zu, zum Beispiel einen AdaBoost oder XGBoost Algorithmus zu verstehen, muss man erst die dahinter stehenden Konzepte kennen. Denn all diese Algorithmen sind im Prinzip Ensemble Machine Learning Algorithmen und basieren meistens auf Decision Trees.

Was  ist also ein Ensemble Algorithmus? Beim sogenannten Ensemble Learning werden mehrere Machine Learning Modelle mit einander kombiniert um so das Ergebnis eines Modells zu verbessern. Im Prinzip nehme ich also einfach viele Decision Trees und kombiniere die Ergebnisse z.B. in dem ich den Durchschnittswert aus allen Decision Trees verwende, und das Ergebnis davon ist dann mein Vorhersagewert meines finalen Modells. Beim Ensemble Learning wird dabei vor allem zwischen zwei Verfahren unterschieden.

  • Dem Bagging: Bagging steht für Bootstrapping Aggregating. Es werden mithilfe mehrerer Stichproben aus dem Datensatz verschiedene Modelle trainiert (Bootstrapping Verfahren). Danach werden die Ergebnisse ggf. noch gewichtet und dann Aggregiert.
  • Dem Boosting: Hier werden mehrere schwache Klassifikatoren verwendet. Diese werden, anders als beim Bagging, nicht parallel und weitgehend unabhängig voneinander trainiert sondern sequentiell. Dabei lernen die Klassifikatoren aus den Fehlern der vorherigen Modelle und versuchen den Fehler den diese Modelle gemacht haben zu minimieren.
Bagging Beispiel
Boosting Beispiel

Es gibt noch eine dritte Methode dem Stacking. Sie entspricht soweit dem Vorgehen des Baggings. Während beim Bagging aber gleichartige Modelle genutzt werden ( z.B. nur Decision Trees). Werden beim Stacking verschiedenartige Modelle verwendet (z.B. Decision Trees und K-Nearest Neighbours). Aus diesen Ergebnissen wird dann ein Meta Modell erzeugt, welches die Schwächen der jeweiligen einzelnen Algorithmen besser berücksichtigen kann.



Was ist ein Random Forest Algorithmus?

Der Random Forest Algorithmus bedient sich dem Bagging Verfahren um die Schwächen von Decision Trees auszugleichen. Um also gegenüber Daten die eine große Varianz besitzen besser zu werden, werden viele Decision Trees kombiniert. Allerdings versucht der Random Forest auch ein Over-Fitting zu verhindern durch ein Aufteilen der Trainingsdaten in sog. Teilmengen. Also nicht alle Decision Trees werden mit den gleichen Trainingsdaten trainiert. Dadurch werden die Decision Trees durch zufällige Teilmengen trainiert und es wächst ein Random Forest heran. Aus diesem Wald an Entscheidungsbäumen wird nun eine Entscheidung getroffen, wobei die Ergebnisse aller einzelnen Bäume herangezogen werden. Dadurch erklären sich auch die verschiedenen Hyperparameter, die zusätzlich zu den bekannten Hyperparametern aus Decision Trees ( z.B. max. Tiefe, minimale Blattgröße etc.) hinzukommen.

Vor allem die Anzahl der Decision Trees die kombiniert werden sollen ist ein wichtiger Hyperparameter für das Tuning eines Random Forests. Außerdem lässt sich das Training durch das Prinzip des Baggings sehr gut parallelisieren. Jeder Entscheidungsbaum kann unabhängig von den restlichen trainiert werden. So lassen sich in kurzer Zeit eine große Anzahl an Entscheidungsbäumen für den Random Forest trainieren.

Für den Random Forest Algorithmus gibt es auch eine Implementierung in der bekannten Python Library Sci-Kit Learn. Wenn ihr mehr zu der Statistik hinter Random Forests wissen wollt. Dann empfehle ich euch das Paper von Leo Breiman, 2001, „Random Forests“. Leo Breiman ist einer derjenigen die den Algorithmus quasi entwickelt haben.

Was ist der XGBoost Algorithmus?

Der XGBoost (Xtreme Gradient Boosting) Algorithmus ist neben dem AdaBoost (Adaptive Boosting) ein weit verbreiteter Algorithmus der auf dem Prinzip des Boostings basiert. Dabei werden mehrere Decision Trees hintereinander angelernt. Zur Berechnung der Fehler der vorherigen Modelle bzw. zur Minimierung der Fehler, wird ein Gradient-Descent Algorithmus verwendet. Das Ziel ist dabei immer einen geringeren Fehler zu erzeugen als die vorhergehenden Modelle. Am Ende steht dann das Endergebnis des Algorithmus, welches genauer ist als eines der einzelnen Modelle hätte vorhersagen können.

Für die Hyperparameter sind besonders die Learning_Rate wichtig. Also wie sehr sollen die Werte der vorherigen Modelle für jeden Lernschritt wieder mit einfließen. Wenn das XGBoost Modell Over-Fitted, dann lassen sich durch das Verringern der Learning Rate die Gefahr des Over-Fittings reduzieren. Auch die Tiefe der Decision Trees und die minimale Größe der einzelnen Blätter beeinflussen den Algorithmus.

Für den XGBoost Algorithmus gibt es eine eigene Bibliothek in Python. XGBoost Library ist außerdem Kompatibel mit den Funktionen aus Sci-Kit Learn. Es lassen sich also auch mit dieser Library eigene Machine Learning Pipelines oder Preprocessing Pipelines aufbauen.

Wenn ihr mehr zu diesem Algorithmus und seiner Funktionsweise bzw. der Statistik dahinter lesen wollt. Dann empfehle ich euch hier ebenfalls ein wissenschaftliches Paper von den Erfindern. Und zwar von Tianqi Chen, Carlos Guestrin, 2016, XGBoost A Scalable Tree Boosting System.

Ich hoffe ich konnte euch damit einen Überblick verschaffen und zu eurem besserem Verständnis für die unterschiedlichen Arten von Supervised Machine Learning Algorithmen beitragen. Man kann zwar auch ohne dieses Verständnis solche Algorithmen verwenden. Die Optimierung und richtige Anwendung wird aber erst dann wirklich funktionieren, wenn man grundsätzlich versteht was da passiert.