Ein Entscheidungsbaum ist ein nichtparametrischer überwachter Lernalgorithmus, der sowohl für Klassifizierungs- als auch für Regressionsaufgaben verwendet wird. Er verfügt über eine hierarchische, baumartige Struktur, die aus einem Wurzelknoten, Zweigen, internen Knoten und Blattknoten besteht.

Wie Sie aus dem obenstehenden Diagramm ersehen können, beginnt ein Entscheidungsbaum mit einem Wurzelknoten, der keine zu ihm hin verlaufende Zweige hat. Die vom Wurzelknoten ausgehenden Zweige münden dann in die internen Knoten, die auch als Entscheidungsknoten bezeichnet werden. Auf der Grundlage der verfügbaren Merkmale werden an beiden Knotentypen Bewertungen durchgeführt, um homogene Teilmengen zu bilden, die als Blattknoten oder Endknoten bezeichnet werden. Die Blattknoten stellen alle möglichen Ergebnisse innerhalb des Datensatzes dar. Nehmen wir zum Beispiel an, dass Sie versuchen zu beurteilen, ob Sie surfen gehen sollen oder nicht. In dieser Situation können Sie die folgenden Entscheidungsregeln anwenden, um eine Entscheidung zu treffen:

Diese Art von Flussdiagrammstruktur bietet außerdem eine leicht verständliche Darstellung für den Prozess der Entscheidungsfindung, die es verschiedenen Gruppen innerhalb eines Unternehmens ermöglicht, besser zu verstehen, warum eine Entscheidung getroffen wurde.

Beim Lernprozess anhand Entscheidungsbäumen wird sozusagen eine „Teile-und-Herrsche-Strategie" angewandt, bei der eine „gierige" Suche durchgeführt wird, um die optimalen Teilungspunkte innerhalb eines Baums zu ermitteln. Dieser Aufteilungsprozess wird dann rekursiv von oben nach unten wiederholt, bis alle oder die meisten Datensätze unter bestimmten Klassenbezeichnungen kategorisiert wurden. Ob alle Datenpunkte als homogene Mengen klassifiziert werden oder nicht, hängt weitgehend von der Komplexität des Entscheidungsbaums ab. Kleinere Bäume können leichter reine Blattknoten erreichen – d. h. die Datenpunkte in einer einzelnen Klasse. Mit zunehmender Größe eines Baums wird es jedoch immer schwieriger, diese Reinheit aufrechtzuerhalten, und dies führt normalerweise dazu, dass zu wenige Daten in einen bestimmten Teilbaum fallen. Wenn dies eintritt, wird dies als Datenfragmentierung bezeichnet und kann häufig zu Überanpassung führen. Infolgedessen werden Entscheidungsbäume bevorzugt bei kleinen Bäumen eingesetzt, was mit dem Prinzip der Sparsamkeit in Occams Razor übereinstimmt, demzufolge „Entitäten nicht unnötig vervielfacht werden sollten." Anders ausgedrückt, Entscheidungsbäume sollten die Komplexität nur bei Bedarf erhöhen, da die einfachste Erklärung oft die beste ist. Um die Komplexität zu reduzieren und eine Überanpassung zu verhindern, wird normalerweise der Prozess des „Zurechtschneidens" (Pruning) angewendet. Dies ist ein Prozess, der Zweige entfernt, die sich auf Features mit geringer Wichtigkeit aufteilen. Die Eignung des Modells kann dann durch den Prozess der Kreuzvalidierung bewertet werden. Eine andere Möglichkeit, wie Entscheidungsbäume ihre Genauigkeit beibehalten können, ist die Bildung eines Ensembles mittels eines Random-Forest-Algorithmus. Dieser Klassifikator sagt genauere Ergebnisse voraus, insbesondere wenn die einzelnen Bäume nicht miteinander korreliert sind.

Während es mehrere Alternativen gibt, das beste Attribut an jedem Knoten auszuwählen, sind zwei Methoden, Informationsgewinn und Gini-Unreinheit, beliebte Aufteilungskriterien für Entscheidungsbaummodelle. Sie helfen bei der Bewertung der Qualität jeder Testbedingung und wie gut Stichproben in eine Klasse kategorisiert werden können.  

Entropie und Informationsgewinn

Es ist schwierig, das Prinzip des Informationsgewinns zu erklären, ohne zuerst das Prinzip der Entropie zu diskutieren. Entropie ist ein aus der Informationstheorie stammender Begriff, der die Unreinheit der Stichprobenwerte misst. Entropie ist durch die folgende Formel definiert: 

• S stellt den Datensatz dar, anhand dessen die Entropie berechnet wird 
• c stellt die Klassen im Satz S dar
• p(c) stellt die Anzahl der Datenpunkte, die zur Klasse c gehören, im Verhältnis zur Gesamtzahl der Datenpunkte in Satz S dar

Entropiewerte können zwischen 0 und 1 liegen. Wenn alle Stichproben in Datensatz S zu einer Klasse gehören, dann ist die Entropie gleich Null. Wenn die Hälfte der Proben einer Klasse und die andere Hälfte einer anderen Klasse zugeordnet wird, ist die Entropie mit einem Wert von 1 am höchsten. Um das beste Aufteilungsmerkmal auszuwählen und den optimalen Entscheidungsbaum zu finden, sollte das Attribut mit der geringsten Entropie verwendet werden. Der Informationsgewinn stellt den Unterschied in der Entropie vor und nach einer Teilung anhand eines bestimmten Attributs dar. Das Attribut mit dem höchsten Informationsgewinn erzeugt die beste Aufteilung, da es die Trainingsdaten gemäß seiner Zielklassifikation am besten klassifiziert. Der Informationsgewinn wird normalerweise mit der folgenden Formel dargestellt, wobei: 

• a stellt ein bestimmtes Attribut oder eine Klassenbezeichnung dar
• Entropie(S) ist die Entropie des Datensatzes S
• |Sv|/ |S| stellt die Anzahl der Werte in S_v im Verhältnis zur Anzahl der Werte im Datensatz S dar
• Entropie(S_v) ist die Entropie des Datensatzes, S_v

Lassen Sie uns ein Beispiel durchgehen, um diese Konzepte zu vertiefen. Stellen Sie sich vor, wir haben den folgenden beliebigen Datensatz:

Für diesen Datensatz beträgt der Entropiewert 0,94. Dieser Wert kann berechnet werden, indem der Anteil der Tage ermittelt wird, an denen „Tennis spielen" „Ja" ist, also 9/14, und der Anteil der Tage, an denen „Tennis spielen" „Nein" ist, also 5/14. Dann können diese Werte in die obenstehende Entropieformel eingesetzt werden.

Entropie (Tennis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0,94

Wir können dann den Informationsgewinn für jedes der Attribute einzeln berechnen. Der Informationsgewinn für das Attribut „Luftfeuchtigkeit" wäre beispielsweise der folgende:

Informationsgewinn (Tennis, Luftfeuchtigkeit) = (0,94)-(7/14)*(0,985) – (7/14)*(0,592) = 0,151

Um es also zusammenzufassen:

• 7/14 steht für die Zahl der Werte, bei denen die Luftfeuchtigkeit „hoch" ist, im Verhältnis zur Gesamtzahl der Luftfeuchtigkeitswerte. In diesem Fall ist die Anzahl der Werte, bei denen die Luftfeuchtigkeit „hoch" ist, gleich der Anzahl der Werte, bei denen die Luftfeuchtigkeit „normal" ist.

• 0,985 ist die Entropie bei Luftfeuchtigkeit = „hoch"

• 0,59 ist die Entropie bei Luftfeuchtigkeit = „normal"

Wiederholen Sie dann die Berechnung des Informationsgewinns für jedes Attribut in der obenstehenden Tabelle und wählen Sie das Attribut mit dem höchsten Informationsgewinn als ersten Teilungspunkt im Entscheidungsbaum aus. In diesem Fall generiert „Outlook" (Wetteraussicht) den höchsten Informationsgewinn. Von diesem Startpunkt wird der Prozess für jeden Teilbaum wiederholt. 

Gini-Unreinheit 

Die Gini-Unreinheit ist die Wahrscheinlichkeit, zufällige Datenpunkte in einem Datensatz falsch zu klassifizieren, wenn sie basierend auf der Klassenverteilung des Datensatzes gekennzeichnet wurden. Ähnlich wie bei der Entropie ist, wenn der Satz S „rein" ist, d. h. zu einer Klasse gehört, die Unreinheit des Satzes gleich Null. Dies wird durch die folgende Formel angegeben: 

Während Entscheidungsbäume in einer Vielzahl von Anwendungsfällen verwendet werden können, sind andere Algorithmen in der Regel effektiver als Entscheidungsbaumalgorithmen. Entscheidungsbäume sind jedoch besonders nützlich für Aufgaben in den Bereichen Data-Mining und Wissensentdeckung. Lassen Sie uns im Folgenden die wichtigsten Vorteile und Herausforderungen bei der Verwendung von Entscheidungsbäumen untersuchen:

• Leicht zu interpretieren: Die boolesche Logik und die visuellen Darstellungen von Entscheidungsbäumen erleichtern das Verständnis und die Nutzung. Die hierarchische Natur eines Entscheidungsbaums macht es außerdem leicht zu erkennen, welche Attribute am wichtigsten sind, was bei anderen Algorithmen nicht immer klar ist, wie z. B. bei Neuronalen Netzen.

• Wenig bis keine Datenaufbereitung erforderlich: Entscheidungsbäume haben eine Reihe von Merkmalen, die sie flexibler als andere Klassifikatoren machen. Beispielsweise können verschiedene Datentypen verarbeitet werden – d. h. diskrete oder kontinuierliche Werte – und kontinuierliche Werte können durch die Verwendung von Schwellenwerten in kategoriale Werte umgewandelt werden. Darüber hinaus können auch Werte mit fehlenden Werten verarbeitet werden, was für andere Klassifikatoren wie Naïve Bayes problematisch sein kann.  

• Flexibler: Entscheidungsbäume können sowohl für Klassifizierungs- als auch für Regressionsaufgaben genutzt werden. Dies macht sie flexibler als einige andere Algorithmen. Sie sind weiterhin unempfindlich gegenüber zugrunde liegenden Beziehungen zwischen Attributen. Das bedeutet, dass der Algorithmus, wenn zwei Variablen stark korrelieren, nur eines der Merkmale für die Aufteilung auswählt. 

• Anfällig für Überanpassung: Komplexe Entscheidungsbäume neigen zu Überanpassung und lassen sich nicht gut auf neue Daten verallgemeinern. Dieses Szenario kann durch die Prozesse des Pre-Pruning oder Post-Pruning vermieden werden. Pre-Pruning stoppt das „Wachstum" des Baums, wenn nicht genügend Daten vorhanden sind, während Post-Pruning Teilbäume mit unzureichenden Daten nach der Baumkonstruktion entfernt. 

• Schätzer mit hoher Variabilität: Kleine Variationen innerhalb der Daten können einen sehr unterschiedlichen Entscheidungsbaum erzeugen. Bagging, oder die Mittelwertbildung von Schätzungen, ist ein möglicher Ansatz zur Verringerung der Variabilität von Entscheidungsbäumen. Dieser Ansatz hat jedoch Grenzen, da er zu stark korrelierten Prädiktoren führen kann.  

• Teurer: Da Entscheidungsbäume während der Konstruktion einen gierigen Suchansatz verfolgen, kann das Training im Vergleich zu anderen Algorithmen teurer sein. 

• In Scikit-learn nicht vollständig unterstützt:  Scikit-learn ist eine beliebte Bibliothek für maschinelles Lernen, die auf Python basiert. Diese Bibliothek verfügt zwar über ein Modul Entscheidungsbaum (DecisionTreeClassifier, Link führt zu einer Seite außerhalb von ibm.com), aber die aktuelle Implementierung unterstützt keine kategorialen Variablen.