Klassifizierung

Entscheidungsbäume sind eine nichtparametrische Methode zur grafischen Darstellung eines Regelsatzes. Sie sind die Grundlage für Modelle wie Random Forest oder Boosted Decision Trees.

Ein Entscheidungsbaum besteht aus Wurzelknoten, inneren Knoten und Blättern. Die Knoten repräsentieren eine logische Regel für das Treffen einer Entscheidung, in den Blättern werden die Ergebnisse repräsentiert.

Ein bekannter Lernalgorithmus für die Erzeugung von Entscheidungsbäumen ist Classification and Regression Trees (CART). CART Modelle unterscheiden sich von anderen Modellen darin, dass sie nicht nur kategorische, sondern auch reelle Variablen verarbeiten können. Bei kategorischen Variablen werden die Entscheidungen anhand der Kategorie getroffen, reelle Variablen werden an einem Schwellenwert diskretisiert. Die Repräsentation der Daten ist ein binärer Entscheidungsbaum, das heißt, jeder Regelausdruck kann nur eine von zwei Werten annehmen.

Die Regeln lernt der Algorithmus induktiv aus dem gegebenen Trainingsdatensatz. Dafür wird für jeden Knoten diejenige Variable gefunden, die die Beobachtungen am saubersten in die gesuchten Klassen aufteilen kann.

Damit wird der Datensatz Schritt für Schritt immer weiter aufgeteilt, bis in jeder Teilmenge nur noch Objekte einer Klasse vorhanden sind. Als Maß für die Güte der Teilung werden der Gini-Koeffizient oder Information Gain verwendet.

Ist der Baum erstellt, kann eine neue Beobachtung klassifiziert werden, indem der Baum von der Wurzel bis in ein Blatt durchlaufen wird und an jedem Knoten anhand des Wertes der Variablen im Knoten und der Beobachtung entschieden wird, welcher Knoten als nächstes ausgewählt wird.

Der fertige Baum kann als Grafik oder als Satz von Regeln abgespeichert werden.

Wird nur ein einzelner Baum verwendet, kommt es höchstwahrscheinlich zu einem Overfitting, da er den Feature-Raum anhand jedes einzelnen Features perfekt aufteilt und dabei nicht generalisiert.  Das Modell lernt nicht nur die tatsächlichen Beziehungen in den Trainingsdaten, sondern auch das Rauschen. Damit ist die Varianz sehr hoch, weil die gelernten Parameter sehr stark mit den gegebenen Daten variieren. Im Extremfall gibt es für jede Beobachtung ein Blatt mit der entsprechenden Klasse. Dies kann mit einer Beschränkung der Tiefe des Baumes verhindert werden, was wiederum das Bias erhöhen kann.

Um das Problem zu umgehen, können mehrere Bäume in einem Ensemble verwendet werden. Beispiele für Ensembles aus Entscheidungsbäumen sind Random Forest und Boosted Decision Trees. Diese zeigen eine hervorragende Performance auf vielen verschiedenen Problemen inklusive nichtlinearer Probleme.

Random Forests sind random, weil für jeden Baum ein zufällig gewählter Teil der Beobachtungen und zufällig gewählte Subsets von Features verwendet werden. Nachdem jeder Baum seine Vorhersagen gemacht hat, werden diese gemittelt. Dieser Prozess der Zufallsauswahl und dem Mitteln der Ergebnisse wird Bagging (Kurz für Bootstrap Aggregating) genannt.

Einzig bei der Interpretation gibt es Nachteile; ein einzelner Baum kann grafisch dargestellt werden und ist einfach zu interpretieren, dies trifft nicht mehr auf das Ensemble zu.

Ein großer Vorteil ist, aufgrund der Lernweise, das eine Feature Selection im Modell integriert ist und sogenannte Features Importances zur Interpretation ausgegeben werden können. Auch bei Random Forest kann Kollinearität ein Problem darstellen. Sind zwei Variablen stark kollinear, wird eine der Variablen auf Kosten der anderen höher gewichtet werden, auch wenn beide gleich wichtig sind.

Bei der Anwendung von Entscheidungsbäumen müssen die Daten nur wenig vorbereitet werden; der Algorithmus kann gut mit unskalierten Daten und Ausreißern umgehen. Wird mit Scikit-Learn gearbeitet, sollten die kategorischen Variablen kodiert werden, dies ist jedoch nicht immer nötig, manche Implementierungen, wie H2O können kategorische Variablen direkt verarbeiten.