Return to site

Random Forests

Warum viele Entscheidungsbäume zusammen noch besser funktionieren

· ML Algorithmen

Einleitung

Eines der beliebtesten maschinellen Lernverfahren sind Entscheidungsbäume, da sie gut zu lesen und interpretieren sind und gleichzeitig in einer Struktur vorliegen, die gut von Computern verarbeitet werden kann. Da Entscheidungsbäume nicht besonders gut mit fehlerhaften Daten bzw. Rauschen in den Daten umgehen können, kann man mittels Ensemble Learning viele Bäume zu einem "Wald" zu kombinieren, woher auch der Name Random Forest stammt. Diese Bäume werden unter verschiedenen Bedingungen erlernt und dabei möglichst einfach gehalten, weshalb einzelne Entscheidungsbäume auch als Weak Learner bezeichnet werden. Die zwei Ansätze, um Weak Learners zu einem Random Forest zu kombinieren, heißen Bagging und Boosting.

Bagging

Bagging steht für "Bootstrap Aggregation" und ist ein Begriff, der über Random Forests hinaus bekannt ist. Dabei werden aus den Trainingsdatensätzen zufällig Beispiele herausgenommen und zu neuen Datensätzen fester Größe zusammengesetzt. Aus jedem neuen Datensatz wird ein Entscheidungsbaum gelernt, der folglich nur einen Teil aller Trainingsdaten kennt.

Wie im Artikel über Entscheidungsbäume erklärt wurde, wird anhand der Trainingsbeispiele bestimmt, welches Attribut am besten geeignet ist, um eine Vorhersage der Klasse zu treffen. Verschiedene Bäume treffen dadurch z.T. unterschiedliche Entscheidungen darüber, welche Zusammenhänge wichtig sind, um gute Vorhersagen zu treffen. Hierdurch entstehen viele strukturell verschiedene Bäume bzw. Entscheidungsprozesse, die gebündelt besser Vorhersagen zu neuen Beispielen treffen können.
Im Falle der Random Forests werden die Bäume nicht nur mit einer zufälligen Auswahl an Trainingsbeispielen angelernt, sondern auch mit einer zufälligen und beschränkten Auswahl an Attributen. Das macht die Bäume simpler in ihrer Struktur und ist notwendig, da bei Random Forests kein abschließendes Pruning stattfindet.

Jeder erzeugte Weak Learner macht dann seine eigene Vorhersage für ein Beispiel. Im Falle einer Klassifizierung wird beispielsweise die Klasse gewählt, die die meisten Stimmen bekommen hat, während bei der Regression der Durchschnitt aller vorhergesagten Werte errechnet wird. Dadurch fällt eine eventuell falsche Vorhersage eines Baums nicht mehr so stark ins Gewicht. Alternativ zu diesen relativ einfachen Verfahren der Konsensbildung können auch kompliziertere Ansätze gewählt werden, z.B. eine gewichtete Abstimmung.

Boosting

Im Gegensatz zum Bagging werden beim Boosting die Bäume nicht parallel erlernt, sondern sequentiell. Jeder Baum konzentriert sich dabei speziell auf die Beispiele, die vom Vorgänger nicht korrekt eingeordnet wurden. Zur Veranschaulichung wird der Boosting Algorithmus AdaBoost im nachfolgenden Abschnitt erklärt. Eine Alternative zu AdaBoost stellt das sogenannte Gradient Boosting dar, dessen erweiterte Form XGBoost ("Extreme Gradient Boosting") unter Praktikern auf Grund guter Performance sehr beliebt ist.

Klassifizierung mit AdaBoost

AdaBoost steht für Adaptive Boosting und ist ein spezieller Boosting Algorithmus, der sich dadurch auszeichnet, dass die einzelnen Weak Learners sogenannte Stumps ("Baumstümpfe") sind. Stumps sind Bäume, die aus nur einem Entscheidungsknoten bestehen. Im Nachfolgenden soll die grundsätzliche Funktionsweise des Algorithmus kurz skizziert werden.

In jedem Schritt wird das Attribut für einen neuen Knoten gewählt, dass am besten mit der vorherzusagenden Klasse korreliert. In AdaBoost wird der erste Baum bzw. der erste Knoten genauso erlernt. Danach wird das eigentliche Boosting durchgeführt. Die Beispiele, die der erste Baum fehlerhaft klassifiziert hat, werden stärker gewichtet. Die richtig klassifizierten Beispiele werden dementsprechend weniger berücksichtigt. Durch die Gewichtung fokussiert sich der nächste Entscheidungsbaum stärker auf die vorher falsch klassifizierten Beispiele. Bei der Vorhersage einer Klasse wird diejenige Klasse ausgewählt, die nach Berücksichtigung der Gewichtungen die meisten Stimmen erhalten hat.

Vergleich von Bagging und Boosting

Beide Verfahren eignen sich vor allem für strukturierte Klassifizierungsprobleme und sollen die Anfälligkeit von einzelnen Entscheidungsbäumen für Overfitting minimieren. Weil beim Bagging alle Entscheidungsbäume als vollwertig betrachtet werden und auf verschiedenen Datensätzen trainiert werden, kommt dieses Verfahren gut mit Rauschen und Fehlern in den Daten zurecht. Boosting hat eine höhere Genauigkeit und kommt besser mit Bias zu Recht, es kann jedoch leicht zu Overfitting führen. Das liegt daran, dass falsch klassifizierte Beispiele solange stärker gewichtet werden, bis ein Baum gelernt wird, der sie klassifiziert. Dies kann über die Anzahl der gelernten Bäume reguliert werden.

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OK