Was versteht man unter einem Decision Tree?

Wie Sie dem folgenden Diagramm entnehmen können, beginnt ein Decision Tree mit einem Stammknoten, der keine eingehenden Zweige hat. Die vom Stammknoten ausgehenden Zweige münden dann in die inneren Knoten, auch Entscheidungsknoten genannt. Basierend auf den verfügbaren Funktionen führen beide Knotentypen Auswertungen durch, 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, Sie überlegen, ob Sie surfen gehen sollten oder nicht. In diesem Fall können Ihnen die folgenden Entscheidungsregeln helfen:

Diese Art von Flussdiagrammstruktur ermöglicht auch eine leicht verständliche Darstellung der Entscheidungsfindung. Verschiedene Gruppen in einem Unternehmen können also besser verstehen, warum eine Entscheidung getroffen wurde.

Beim Lernen mit Decision Trees wird eine „Teile und herrsche“-Strategie angewendet: Mit einer Greedy-Suche (auch „gierige“ Suche genannt) werden die optimalen Trennpunkte innerhalb eines Baums ermittelt. Dieser Aufteilungsprozess wird dann in einer rekursiven Top-Down-Methode wiederholt, bis alle oder die Mehrheit der Datensätze unter bestimmten Klassenbezeichnungen klassifiziert wurden.

Ob alle Datenpunkte als homogene Mengen klassifiziert werden, hängt weitgehend von der Komplexität des Decision Trees ab. Kleinere Bäume sind eher in der Lage, reine Blattknoten zu erreichen, d. h. Datenpunkte in einer einzelnen Klasse. Je größer ein Baum jedoch wird, desto schwieriger wird es, diese Reinheit aufrechtzuerhalten, und in der Regel fallen dann zu wenige Daten in einen bestimmten Teilbaum. In dem Fall spricht man von Datenfragmentierung, die häufig zu Überanpassung führt.

Daher werden in Decision Trees kleine Bäume bevorzugt, was mit dem Prinzip der Sparsamkeit in Ockhams Rasiermesser übereinstimmt, d. h. „Entitäten sollten nicht über das Notwendige hinaus vervielfacht werden“. Anders ausgedrückt: Decision Trees sollten nur dann komplexer werden, wenn es notwendig ist, da die einfachste Erklärung oft die beste ist. Um die Komplexität zu reduzieren und eine Überanpassung zu verhindern, wird in der Regel ein Beschneiden („Pruning“) durchgeführt. Dabei werden Zweige entfernt, die sich an Merkmalen mit geringer Bedeutung aufteilen. Die Passform des Modells kann dann durch den Prozess der Kreuzvalidierung bewertet werden.

Eine weitere Möglichkeit, die Genauigkeit von Decision Trees zu erhalten, ist die Bildung eines Ensembles mithilfe eines Random-Forest-Algorithmus. Dieser Klassifikator liefert genauere Ergebnisse, insbesondere, wenn die einzelnen Bäume nicht miteinander korrelieren.

Der in den 1960er Jahren entwickelte Algorithmus von Hunt modelliert das menschliche Lernen in der Psychologie. Er bildet die Grundlage vieler beliebter Decision-Tree-Algorithmen, wie z. B. der folgenden:

- ID3: Ross Quinlan wird die Entwicklung von ID3 zugeschrieben, was für „Iterative Dichotomiser 3“ steht. Dieser Algorithmus nutzt Entropie und Informationsgewinn als Metriken zur Bewertung von Kandidatenaufteilungen. Einige von Quinlans Forschungsarbeiten von 1986 zu diesem Algorithmus finden Sie hier.

– C4.5: Dieser Algorithmus gilt als eine spätere Iteration von ID3 und wurde ebenfalls von Quinlan entwickelt. Er kann mit Informationsgewinn oder Gewinnverhältnissen Trennpunkte innerhalb der Decision Trees bewerten.

– CART: Der Begriff CART ist eine Abkürzung für „Classification and Regression Trees“ und wurde von Leo Breiman eingeführt. Dieser Algorithmus verwendet in der Regel die Gini-Verunreinigung, um das ideale Attribut für die Aufteilung zu ermitteln. Die Gini-Verunreinigung misst, wie oft ein zufällig ausgewähltes Attribut falsch klassifiziert wird. Bei der Bewertung mit der Gini-Verunreinigung ist ein niedrigerer Wert idealer.

Es gibt zwar mehrere Möglichkeiten, das beste Attribut an jedem Knoten auszuwählen, aber die beiden Methoden des Informationsgewinns und der Gini-Verunreinigung sind beliebte Aufteilungskriterien für Decision-Tree-Modelle. Sie helfen bei der Bewertung der Qualität jeder Testbedingung und wie gut Proben in eine Klasse eingeteilt werden können.

Um den Begriff Informationsgewinn zu erklären, muss vorher der Begriff Entropie erörtert werden. Entropie ist ein Konzept aus der Informationstheorie und misst die Verunreinigung der Stichprobenwerte. Sie wird durch die folgende Formel definiert, wobei:

• S den Datensatz darstellt, in dem die Entropie berechnet wird
• c für die Klassen in der Menge S steht
• p(c) der Anteil der Datenpunkte ist, die zur Klasse c gehören, im Verhältnis zur Anzahl der gesamten Datenpunkte in der Menge S

Entropiewerte können zwischen 0 und 1 liegen. Wenn alle Proben im Datensatz S zu einer Klasse gehören, ist die Entropie gleich Null. Wenn die Hälfte der Proben einer Klasse zugeordnet wird und die andere Hälfte einer anderen Klasse, ist die Entropie mit 1 am höchsten. Um das beste Merkmal für die Aufteilung auszuwählen und den optimalen Decision Tree zu finden, sollte das Attribut mit der geringsten Entropie verwendet werden.

Der Informationsgewinn stellt die Differenz der Entropie vor und nach einer Aufteilung bei einem bestimmten Attribut dar. Das Attribut mit dem höchsten Informationsgewinn führt zur besten Aufteilung, da es die Trainingsdaten am besten gemäß seiner Zielklassifizierung gruppieren kann. Der Informationsgewinn wird in der Regel mit der folgenden Formel dargestellt,

wobei gilt:

• a steht für ein bestimmtes Attribut oder eine Klassenbezeichnung
• Entropie(S) ist die Entropie des Datensatzes S
• |Sv|/|S| stellt den Anteil der Werte in S_v an der Anzahl der Werte im Dataset S dar.

Folgendes Beispiel verdeutlicht diese Konzepte. Stellen Sie sich vor, wir haben den folgenden, zufällig ausgewählten Datensatz:

Für diesen Datensatz beträgt die Entropie 0,94. Dies lässt sich berechnen, indem man den Anteil der Tage ermittelt, an denen „Tennis spielen“ „Ja“ ist, was 9/14 entspricht, und den Anteil der Tage, an denen „Tennis spielen“ „Nein“ ist, was 5/14 entspricht. Dann können diese Werte in die obige 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. Zum Beispiel wäre der Informationsgewinn für das Attribut „Luftfeuchtigkeit“ wie folgt:

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

Zusammenfassend:

- 7/14 stellt den Anteil der Werte dar, bei denen die Luftfeuchtigkeit „hoch“ ist, im Vergleich 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 einer Luftfeuchtigkeit von „hoch“

- 0,59 ist die Entropie bei einer Luftfeuchtigkeit von „normal“

Wiederholen Sie dann die Berechnung für den Informationsgewinn für jedes Attribut in der obigen Tabelle und wählen Sie das Attribut mit dem höchsten Informationsgewinn als ersten Aufteilungspunkt im Decision Tree aus. In diesem Fall bietet „Outlook“ (Vorhersage) den größten Informationsgewinn. Von dort aus wird der Vorgang für jeden Teilbaum wiederholt.

Die Gini-Verunreinigung ist die Wahrscheinlichkeit, dass zufällige Datenpunkte im Datensatz falsch klassifiziert werden, wenn sie auf der Grundlage der Klassenverteilung des Datensatzes gekennzeichnet würden. Ähnlich wie bei der Entropie ist die Verunreinigung null, wenn die Menge S rein ist – d. h. zu einer Klasse gehört. Dies wird durch die folgende Formel bestimmt:

Während Decision Trees für eine Vielzahl von Anwendungsfällen eingesetzt werden können, übertreffen andere Algorithmen in der Regel diejenigen für Decision Trees. Allerdings sind Decision Trees besonders nützlich für Data Mining und Aufgaben zur Wissensentdeckung. Lassen Sie uns im Folgenden die Hauptvorteile und Herausforderungen der Verwendung von Decision Trees untersuchen:

• Einfache Interpretation: Die boolesche Logik und die visuelle Darstellung von Decision Trees erleichtern das Verständnis und die Nutzung. Durch die hierarchische Natur eines Decision Trees lässt sich einfach erkennen, welche Attribute am wichtigsten sind, was bei anderen Algorithmen, beispielsweise neuronalen Netzen, nicht immer der Fall ist.
  
  
• Es ist nur wenig bis gar keine Datenaufbereitung notwendig: Decision Trees weisen eine Reihe von Merkmalen auf, die sie flexibler machen als andere Klassifikatoren. Sie können verschiedene Datentypen verarbeiten – d. h. diskrete oder kontinuierliche Werte, und kontinuierliche Werte können durch die Verwendung von Schwellenwerten in kategorische Werte umgewandelt werden. Darüber hinaus können sie auch Werte mit fehlenden Werten verarbeiten, im Gegensatz zu anderen Klassifikatoren, wie z. B. Naïve Bayes.
  
  
• Flexibler: Decision Trees können sowohl für Klassifizierungs- als auch Regressionsaufgaben eingesetzt werden, wodurch sie flexibler sind als manch andere Algorithmen. Außerdem sind sie unempfindlich gegenüber zugrunde liegenden Beziehungen zwischen Attributen: Weisen zwei Variablen eine hohe Korrelation auf, wählt der Algorithmus nur eines der Merkmale zur Aufteilung aus.

• Anfällig für Überanpassung: Komplexe Decision Trees neigen zur Überanpassung und lassen sich nicht gut auf neue Daten verallgemeinern. Dieses Szenario kann durch Vor- oder Nachschnitt vermieden werden. Durch das Vorschneiden wird das Baumwachstum gestoppt, wenn nicht genügend Daten vorliegen, während durch das Nachschneiden Teilbäume mit unzureichenden Daten nach dem Aufbau des Baums entfernt werden.
  
  
• Schätzer mit hoher Varianz: Geringe Abweichungen innerhalb der Daten können zu einem völlig anderen Decision Tree führen. Bagging, oder die Mittelung von Schätzungen, kann eine Methode zur Reduzierung der Varianz von Decision Trees sein. Dieser Ansatz ist jedoch nur begrenzt einsetzbar, da er zu stark korrelierten Prädiktoren führen kann.
• Teurer: Da Decision Trees während der Erstellung einen Greedy-Suchansatz verfolgen, kann das Trainieren im Vergleich zu anderen Algorithmen aufwändiger sein.