Was ist ein Entscheidungsbaum?

Was ist ein Entscheidungsbaum?

A Entscheidungsbaum ist ein nützlicher Algorithmus für maschinelles Lernen, der sowohl für Regressions- als auch für Klassifizierungsaufgaben verwendet wird. Der Name „Entscheidungsbaum“ rührt daher, dass der Algorithmus den Datensatz so lange in immer kleinere Teile aufteilt, bis die Daten in einzelne Instanzen unterteilt sind, die dann klassifiziert werden. Wenn Sie die Ergebnisse des Algorithmus visualisieren würden, würde die Art und Weise, wie die Kategorien unterteilt sind, einem Baum und vielen Blättern ähneln.

Das ist eine kurze Definition eines Entscheidungsbaums, aber lassen Sie uns einen tieferen Einblick in die Funktionsweise von Entscheidungsbäumen werfen. Wenn Sie besser verstehen, wie Entscheidungsbäume funktionieren und welche Anwendungsfälle sie haben, können Sie leichter erkennen, wann Sie sie in Ihren maschinellen Lernprojekten einsetzen sollten.

Format eines Entscheidungsbaums

Ein Entscheidungsbaum ist sehr ähnlich einem Flussdiagramm. Um ein Flussdiagramm zu verwenden, beginnen Sie am Startpunkt oder der Wurzel des Diagramms und wechseln dann basierend darauf, wie Sie die Filterkriterien dieses Startknotens beantworten, zu einem der nächstmöglichen Knoten. Dieser Vorgang wiederholt sich, bis ein Ende erreicht ist.

Entscheidungsbäume funktionieren im Wesentlichen auf die gleiche Weise, wobei jeder interne Knoten im Baum eine Art Test-/Filterkriterium darstellt. Die Knoten an der Außenseite, die Endpunkte des Baums, sind die Bezeichnungen für den betreffenden Datenpunkt und werden „Blätter“ genannt. Die Zweige, die von den internen Knoten zum nächsten Knoten führen, sind Features oder Konjunktionen von Features. Die zur Klassifizierung der Datenpunkte verwendeten Regeln sind die Pfade, die von der Wurzel bis zu den Blättern verlaufen.

Algorithmen für Entscheidungsbäume

Entscheidungsbäume basieren auf einem algorithmischen Ansatz, der den Datensatz anhand verschiedener Kriterien in einzelne Datenpunkte aufteilt. Diese Aufteilungen erfolgen mit unterschiedlichen Variablen oder den unterschiedlichen Merkmalen des Datensatzes. Wenn das Ziel beispielsweise darin besteht, festzustellen, ob ein Hund oder eine Katze durch die Eingabemerkmale beschrieben wird, könnten die Variablen, nach denen die Daten aufgeteilt werden, Dinge wie „Krallen“ und „Bellen“ sein.

Welche Algorithmen werden also verwendet, um die Daten tatsächlich in Zweige und Blätter aufzuteilen? Es gibt verschiedene Methoden, mit denen man einen Baum aufteilen kann, aber die gebräuchlichste Aufteilungsmethode ist wahrscheinlich eine Technik namens „rekursive binäre Aufteilung“. Bei dieser Aufteilungsmethode beginnt der Prozess an der Wurzel und die Anzahl der Features im Datensatz stellt die mögliche Anzahl möglicher Aufteilungen dar. Eine Funktion wird verwendet, um zu bestimmen, wie viel Genauigkeit jede mögliche Aufteilung kostet, und die Aufteilung erfolgt anhand der Kriterien, die die geringste Genauigkeit beeinträchtigen. Dieser Prozess wird rekursiv durchgeführt und Untergruppen werden nach derselben allgemeinen Strategie gebildet.

Um die Kosten der Aufteilung zu bestimmen, wird eine Kostenfunktion verwendet. Für Regressionsaufgaben und Klassifizierungsaufgaben wird eine andere Kostenfunktion verwendet. Ziel beider Kostenfunktionen ist es, die Zweige mit den ähnlichsten Antwortwerten bzw. den homogensten Zweigen zu bestimmen. Angenommen, Testdaten einer bestimmten Klasse sollen bestimmten Pfaden folgen, ist dies intuitiv nachvollziehbar.

In Bezug auf die Regressionskostenfunktion für die rekursive binäre Aufteilung lautet der zur Berechnung der Kosten verwendete Algorithmus wie folgt:

sum(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 durchlaufen die Kostenfunktion, um die Kosten für alle möglichen Aufteilungen zu ermitteln, und die Aufteilung mit den niedrigsten Kosten wird ausgewählt.

Bezüglich der Kostenfunktion für die Klassifizierung lautet die Funktion wie folgt:

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

Dies ist der Gini-Score und ein Maß für die Wirksamkeit einer Aufteilung, basierend darauf, wie viele Instanzen verschiedener Klassen sich in den aus der Aufteilung resultierenden Gruppen befinden. Mit anderen Worten: Es quantifiziert, wie gemischt die Gruppen nach der Aufteilung sind. Eine optimale Aufteilung liegt vor, wenn alle aus der Aufteilung resultierenden Gruppen nur aus Eingaben einer Klasse bestehen. Wenn eine optimale Aufteilung erstellt wurde, ist der „pk“-Wert entweder 0 oder 1 und G ist gleich Null. Möglicherweise können Sie vermuten, dass die Aufteilung im ungünstigsten Fall eine 50:50-Darstellung der Klassen in der Aufteilung im Fall der binären Klassifizierung ist. In diesem Fall wäre der „pk“-Wert 0.5 und G wäre ebenfalls 0.5.

Der Aufteilungsprozess ist beendet, wenn alle Datenpunkte in Blätter umgewandelt und klassifiziert wurden. Möglicherweise möchten Sie das Wachstum des Baumes jedoch frühzeitig stoppen. Große, komplexe Bäume neigen zur Überanpassung, es können jedoch verschiedene Methoden zur Bekämpfung eingesetzt werden. Eine Methode zur Reduzierung der Überanpassung besteht darin, eine Mindestanzahl von Datenpunkten anzugeben, die zum Erstellen eines Blatts verwendet werden. Eine andere Methode zur Kontrolle einer Überanpassung besteht darin, den Baum auf eine bestimmte maximale Tiefe zu beschränken, die steuert, wie lange sich ein Pfad von der Wurzel bis zu einem Blatt erstrecken kann.

Ein weiterer Prozess bei der Erstellung von Entscheidungsbäumen ist Beschneiden. Das Beschneiden kann dazu beitragen, die Leistung eines Entscheidungsbaums zu steigern, indem Zweige entfernt werden, die Merkmale enthalten, die eine geringe Vorhersagekraft bzw. geringe Bedeutung für das Modell haben. Auf diese Weise wird die Komplexität des Baums verringert, die Wahrscheinlichkeit einer Überanpassung verringert und der Vorhersagenutzen des Modells erhöht.

Beim Beschneiden kann der Vorgang entweder an der Spitze oder an der Unterseite des Baumes beginnen. Die einfachste Methode zum Beschneiden besteht jedoch darin, mit den Blättern zu beginnen und zu versuchen, den Knoten zu löschen, der die häufigste Klasse in diesem Blatt enthält. Wenn sich dabei die Genauigkeit des Modells nicht verschlechtert, bleibt die Änderung erhalten. Es gibt andere Techniken, die zum Beschneiden verwendet werden, aber die oben beschriebene Methode – reduziertes Fehlerbeschneiden – ist wahrscheinlich die gebräuchlichste Methode zum Beschneiden von Entscheidungsbäumen.

Überlegungen zur Verwendung von Entscheidungsbäumen

Entscheidungsbäume sind oft nützlich wenn eine Klassifizierung durchgeführt werden muss, die Rechenzeit jedoch eine große Einschränkung darstellt. Entscheidungsbäume können deutlich machen, welche Merkmale in den ausgewählten Datensätzen die größte Vorhersagekraft haben. Darüber hinaus können Entscheidungsbäume im Gegensatz zu vielen Algorithmen für maschinelles Lernen, bei denen die zur Klassifizierung der Daten verwendeten Regeln möglicherweise schwer zu interpretieren sind, interpretierbare Regeln darstellen. Entscheidungsbäume können außerdem sowohl kategoriale als auch kontinuierliche Variablen verwenden, was bedeutet, dass im Vergleich zu Algorithmen, die nur einen dieser Variablentypen verarbeiten können, weniger Vorverarbeitung erforderlich ist.

Entscheidungsbäume erbringen in der Regel keine besonders gute Leistung, wenn sie zur Bestimmung der Werte kontinuierlicher Attribute verwendet werden. Eine weitere Einschränkung von Entscheidungsbäumen besteht darin, dass der Entscheidungsbaum bei der Klassifizierung tendenziell ungenau ist, wenn es nur wenige Trainingsbeispiele, aber viele Klassen gibt.