Entscheidungsbäume – die überraschende Stärke verschachtelter Entscheidungsregeln

• Eine Struktur, die zur Datenklassifikation den Feature-Raum wiederholt aufteilt und dabei in jedem Schritt die Aufteilung mit dem größten Informationsgewinn auswählt
• Mit Entropie (Entropy) wird die Reinheit (purity) der Daten gemessen, und darauf basierend der Informationsgewinn (Information Gain) berechnet
• Der ID3-Algorithmus findet den optimalen Aufteilungspunkt, indem er die Entropiedifferenz zwischen Eltern- und Kindknoten berechnet, und erweitert den Baum rekursiv
• Anstelle von Entropie kann auch die Gini-Unreinheit verwendet werden; beide Methoden liefern meist ähnliche Ergebnisse, unterscheiden sich jedoch in der Recheneffizienz
• Übermäßige Aufteilungen führen zu Overfitting und Instabilität; dem wird mit Pruning oder Random Forest entgegengewirkt

---

Grundkonzept von Entscheidungsbäumen

• Entscheidungsbäume teilen Daten von oben nach unten auf und trennen sie in jedem Schritt mithilfe von Bedingungsregeln in gut unterscheidbare Bereiche
  • Jede Aufteilung wird durch ein bestimmtes Merkmal (feature) und einen Schwellenwert (cutoff value) bestimmt
  • Ziel ist es, bei der Klassifikation reine Knoten zu erzeugen, in denen sich die Klassen klar unterscheiden

Definition und Eigenschaften der Entropie (Entropy)

• Entropie ist ein Maß für die Unsicherheit von Information und wird für Wahrscheinlichkeiten (p_i) definiert als (H = -\sum p_i \log_2(p_i))
• Wichtige Eigenschaften
  1. Wenn nur ein Ereignis die Wahrscheinlichkeit 1 hat und alle anderen 0, dann gilt (H=0), also keine Unsicherheit
  2. Sind die Wahrscheinlichkeiten aller Ereignisse gleich, ist die Entropie maximal und steht für den unreinsten Zustand
  3. Je gleichmäßiger die Wahrscheinlichkeiten verteilt sind, desto größer ist die Entropie
• Daher haben reine Knoten eine Entropie von 0, während gemischte Knoten hohe Entropiewerte aufweisen

Informationsgewinn (Information Gain) und der ID3-Algorithmus

• Der Informationsgewinn wird als Entropiedifferenz vor und nach der Aufteilung berechnet und beschreibt die Effizienz der Datenaufteilung
  • Formel: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
• Schritte des ID3-Algorithmus
  1. Entropie jedes Merkmals berechnen
  2. Den Datensatz nach verschiedenen Aufteilungskriterien teilen und den Informationsgewinn berechnen
  3. Die Aufteilung mit dem größten Informationsgewinn auswählen und einen Entscheidungsknoten erzeugen
  4. Ein Blattknoten wird erzeugt, wenn keine weitere Aufteilung mehr möglich ist
  5. Rekursiv für alle Teilmengen wiederholen; abbrechen, wenn alle Elemente derselben Klasse angehören
• Im Beispiel wurde die Bedingung Diameter ≤ 0.45 als erste Aufteilung gewählt, weil sie mit 0.574 den größten Informationsgewinn lieferte

Gini-Unreinheit und alternative Messgrößen

• Gini-Unreinheit (Gini impurity) ist eine Alternative zur Entropie und eine weitere Methode zur Messung von Unreinheit in Informationen
  • Da keine Logarithmen berechnet werden müssen, ist sie schneller in der Berechnung
  • Bei unausgeglichenen Datensätzen kann Entropie die vorsichtigere Wahl sein
• Beide Methoden liefern im Allgemeinen ähnliche Ergebnisse

Probleme mit Overfitting und Instabilität

• Der ID3-Algorithmus führt fortlaufend weitere Aufteilungen aus, um die Entropie zu minimieren; dadurch kann der Baum übermäßig tief werden
  • Das verursacht Overfitting, wodurch die Generalisierungsleistung auf neue Daten sinkt
• Außerdem gibt es das Problem der Instabilität (high variance), bei dem sich die Baumstruktur schon durch kleine Änderungen in den Daten stark verändern kann
  • Beispiel: Schon das Hinzufügen von leichtem Gaußschem Rauschen zu 5 % der Trainingsdaten kann einen völlig anderen Baum erzeugen
• Als Gegenmaßnahme lässt sich per Pruning die Tiefe des Baums, die Anzahl der Blätter oder die Mindestzahl an Samples begrenzen

Erweiterung zu Random Forest

• Um die Instabilität eines einzelnen Entscheidungsbaums zu verringern, wird ein Ansatz verwendet, bei dem mehrere Bäume auf unterschiedlichen Datensamples trainiert und ihre Vorhersagen kombiniert werden
  • Dieser Ansatz ist der Random Forest, der hohe Stabilität und gute Generalisierungsleistung bietet
• Damit werden die Schwächen von Entscheidungsbäumen kompensiert, und das Verfahren gilt bis heute als einer der erfolgreichsten Machine-Learning-Algorithmen

Fazit und weiterführendes Lernen

• Entscheidungsbäume sind leicht interpretierbare Modelle mit schneller Lernzeit und einfacher Vorverarbeitung
• Um die Probleme von Overfitting und Instabilität zu lösen, sind jedoch Pruning oder Ensemble-Methoden nötig
• Themen wie Regressionsbäume, End-Cut Preference, Hyperparameter usw. werden im Artikel nicht behandelt; für vertiefendes Lernen werden ergänzende Materialien empfohlen