Was ist ein Entscheidungsbaum?

Was ist ein Entscheidungsbaum?

Ein Entscheidungsbaum ist ein nützliches Machine-Learning-Algorithmus, der für Regressions- und Klassifizierungsaufgaben verwendet wird. Der Name “Entscheidungsbaum” kommt von der Tatsache, dass der Algorithmus das Dataset in immer kleinere Teile teilt, bis die Daten in einzelne Instanzen unterteilt sind, die dann klassifiziert werden. Wenn man die Ergebnisse des Algorithmus visualisieren würde, sähe die Art und Weise, wie die Kategorien unterteilt werden, wie ein Baum mit vielen Blättern aus.

Das ist eine kurze Definition eines Entscheidungsbaums, aber lasst uns einen tiefen Einblick in die Funktionsweise von Entscheidungsbäumen nehmen. Ein besseres Verständnis der Funktionsweise von Entscheidungsbäumen sowie ihrer Anwendungsfälle wird uns helfen, zu wissen, wann wir sie in unseren Machine-Learning-Projekten verwenden sollten.

Format eines Entscheidungsbaums

Ein Entscheidungsbaum ist ähnlich wie ein Flussdiagramm. Um ein Flussdiagramm zu verwenden, beginnt man am Startpunkt oder an der Wurzel des Diagramms und bewegt sich dann basierend auf den Filterkriterien des Startknotens zu einem der nächsten möglichen Knoten. Dieser Prozess wird wiederholt, bis ein Ende erreicht ist.

Entscheidungsbäume funktionieren im Wesentlichen auf die gleiche Weise, wobei jeder interne Knoten im Baum eine Art von Test- oder Filterkriterium darstellt. Die Knoten außen, die Endpunkte des Baums, sind die Labels für den Datenpunkt in Frage und werden als “Blätter” bezeichnet. Die Äste, die von den internen Knoten zu den nächsten Knoten führen, sind Merkmale oder Kombinationen von Merkmalen. Die Regeln, die zur Klassifizierung der Datenpunkte verwendet werden, sind die Pfade, die von der Wurzel zu den Blättern führen.

Algorithmen für Entscheidungsbäume

Entscheidungsbäume funktionieren auf einem algorithmischen Ansatz, der das Dataset in einzelne Datenpunkte teilt, basierend auf verschiedenen Kriterien. Diese Teilungen werden mit verschiedenen Variablen oder Merkmalen des Datasets durchgeführt. Zum Beispiel, wenn das Ziel darin besteht, zu bestimmen, ob ein Hund oder eine Katze durch die Eingabemerkmale beschrieben wird, können die Variablen, auf denen das Dataset geteilt wird, Dinge wie “Krallen” und “bellt” sein.

Welche Algorithmen werden verwendet, um das Dataset in Äste und Blätter zu teilen? Es gibt verschiedene Methoden, die verwendet werden können, um einen Baum zu teilen, aber die häufigste Methode der Teilung ist wahrscheinlich eine Technik, die als “rekursive binäre Teilung” bezeichnet wird. Wenn diese Methode der Teilung durchgeführt wird, beginnt der Prozess an der Wurzel und die Anzahl der Merkmale im Dataset stellt die mögliche Anzahl der möglichen Teilungen dar. Eine Funktion wird verwendet, um zu bestimmen, wie viel Genauigkeit jede mögliche Teilung kosten wird, und die Teilung wird durchgeführt, basierend auf den Kriterien, die die geringste Genauigkeit opfern. Dieser Prozess wird rekursiv durchgeführt und Untergruppen werden gebildet, indem die gleiche allgemeine Strategie verwendet wird.

Um die Kosten der Teilung zu bestimmen, wird eine Kostenfunktion verwendet. Eine andere Kostenfunktion wird für Regressions- und Klassifizierungsaufgaben verwendet. Das Ziel beider Kostenfunktionen ist es, zu bestimmen, welche Äste die ähnlichsten Antwortwerte oder die homogensten Äste haben. Betrachten Sie, dass Sie Testdaten einer bestimmten Klasse haben möchten, die bestimmte Pfade verfolgen, und dies macht intuitiv Sinn.

Im Hinblick auf die Regressionskostenfunktion für die rekursive binäre Teilung wird der Algorithmus wie folgt verwendet:

Summe(y – Vorhersage)^2

Die Vorhersage für eine bestimmte Gruppe von Datenpunkten ist der Mittelwert der Antworten der Trainingsdaten für diese Gruppe. Alle Datenpunkte werden durch die Kostenfunktion geführt, um die Kosten für alle möglichen Teilungen zu bestimmen, und die Teilung mit den geringsten Kosten wird ausgewählt.

Im Hinblick auf die Kostenfunktion für die Klassifizierung ist die Funktion wie folgt:

G = Summe(pk * (1 – pk))

Dies ist der Gini-Score, und es ist ein Maß für die Effektivität einer Teilung, basierend auf der Anzahl der Instanzen verschiedener Klassen in den Gruppen, die aus der Teilung resultieren. Mit anderen Worten, es quantifiziert, wie gemischt die Gruppen nach der Teilung sind. Eine optimale Teilung ist, wenn alle Gruppen, die aus der Teilung resultieren, nur aus Eingaben einer Klasse bestehen. Wenn eine optimale Teilung erstellt wurde, wird der “pk”-Wert entweder 0 oder 1 sein und G wird gleich 0 sein. Sie können sich vorstellen, dass die schlechteste Teilung eine ist, bei der es eine 50-50-Verteilung der Klassen in der Teilung gibt, im Falle der binären Klassifizierung. In diesem Fall wäre der “pk”-Wert 0,5 und G wäre auch 0,5.

Der Teilungsprozess wird beendet, wenn alle Datenpunkte in Blätter umgewandelt und klassifiziert wurden. Es kann jedoch sein, dass Sie das Wachstum des Baums frühzeitig stoppen möchten. Große, komplexe Bäume neigen zu Überanpassung, aber es gibt verschiedene Methoden, um dies zu vermeiden. Eine Methode, um Überanpassung zu reduzieren, besteht darin, eine Mindestanzahl von Datenpunkten zu spezifizieren, die zum Erstellen eines Blatts verwendet werden. Eine andere Methode, um Überanpassung zu kontrollieren, besteht darin, den Baum auf eine bestimmte maximale Tiefe zu beschränken, was bestimmt, wie lang ein Pfad von der Wurzel zu einem Blatt sein kann.

Ein weiterer Prozess, der bei der Erstellung von Entscheidungsbäumen involviert ist, ist das Beschneiden. Das Beschneiden kann die Leistung eines Entscheidungsbaums verbessern, indem es Äste entfernt, die Merkmale enthalten, die wenig Vorhersagekraft oder wenig Bedeutung für das Modell haben. Auf diese Weise wird die Komplexität des Baums reduziert, es wird weniger wahrscheinlich, dass er überanpasst, und die Vorhersageleistung des Modells wird verbessert.

Wenn das Beschneiden durchgeführt wird, kann der Prozess am oberen oder unteren Ende des Baums beginnen. Es ist jedoch am einfachsten, mit den Blättern zu beginnen und zu versuchen, den Knoten zu entfernen, der die häufigste Klasse in diesem Blatt enthält. Wenn die Genauigkeit des Modells nicht beeinträchtigt wird, wenn dies geschieht, wird die Änderung beibehalten. Es gibt andere Techniken, um das Beschneiden durchzuführen, aber die oben beschriebene Methode – reduzierte Fehlerrate – ist wahrscheinlich die häufigste Methode des Beschneidens von Entscheidungsbäumen.

Überlegungen für die Verwendung von Entscheidungsbäumen

Entscheidungsbäume sind oft nützlich, wenn Klassifizierung durchgeführt werden muss, aber die Rechenzeit ein wichtiger Faktor ist. Entscheidungsbäume können klar machen, welche Merkmale in den ausgewählten Datasets die meisten Vorhersagekraft haben. Darüber hinaus können Entscheidungsbäume im Gegensatz zu vielen Machine-Learning-Algorithmen, bei denen die Regeln, die zur Klassifizierung der Daten verwendet werden, schwer zu interpretieren sind, interpretierbare Regeln liefern. Entscheidungsbäume können auch sowohl kategorische als auch kontinuierliche Variablen verwenden, was bedeutet, dass weniger Vorverarbeitung erforderlich ist, im Vergleich zu Algorithmen, die nur eine dieser Variablentypen verarbeiten können.

Entscheidungsbäume neigen dazu, nicht sehr gut zu funktionieren, wenn sie verwendet werden, um die Werte kontinuierlicher Attribute zu bestimmen. Eine weitere Einschränkung von Entscheidungsbäumen ist, dass sie, wenn es wenige Trainingsbeispiele, aber viele Klassen gibt, ungenau sind.