Entscheidungsbäume: Funktionsweise und Optimierung

Funktionsweise von Entscheidungsbäumen

Entscheidungsbäume sind Klassifizierungstechniken, die wie folgt arbeiten:

• Wählen Sie eines der Attribute aus.
• Teilen Sie die Daten durch eine Prüfung des gewählten Attributs:
  • Wenn kategorial (nominal): Bilden Sie für jede mögliche Kategorie eine Teilmenge von Beispielen.
  • Wenn numerisch: Wählen Sie einen Schwellenwert. Bilden Sie eine Menge mit den Beispielen, deren Attribut unterhalb der Schwelle liegt, und eine andere für diejenigen, deren Attribut größer als die Schwelle ist.
• Setzen Sie den Prozess für die erzeugten Teilmengen fort, bis die Abbruchkriterien erfüllt sind.

Das Ziel ist es, endgültige Teilmengen mit einer Vorherrschaft einer Klasse (Baumblätter) zu erhalten.

Wichtige Entscheidungen bei der Umsetzung

1. Kriterien für die Auswahl des besten Attributs.
2. Kriterien für die Beendigung des Algorithmus.

1) Kriterien für die Auswahl des besten Attributs

• In der Regel wählt man das Attribut mit dem höchsten Informationsgewinn.
• Dieser Gewinn ist die Differenz zwischen den Entropien vor und nach der Teilung der Menge durch das Attribut.
• Das Attribut mit dem größten Gewinn ist dasjenige, welches die Entropie am stärksten verringern kann:
  • Es bildet Teilmengen mit unverhältnismäßig hohen Anteilen zwischen den Klassen.
  • Beispiel: Viele Muster in Klasse A und nur wenige in Klasse B.
• Daher bevorzugen wir Attribute, die für die Unterscheidung zwischen den Klassen wichtig sind.

2) Kriterien für die Beendigung des Algorithmus

Es ist wichtig, diese zu definieren, um Überanpassung (Overfitting) zu vermeiden:

• Der Baum wird sonst so komplex, dass er die Trainingsdaten zu genau modelliert, was zu falschen Klassifizierungen bei neuen Daten führt.
• Pre-Pruning: Das Wachstum des Baumes frühzeitig hemmen.
  • Beispiel: Stoppen, wenn die Anzahl der Beispiele in einer Teilmenge einen bestimmten Wert unterschreitet.
  • Wenn die Teilmenge zu klein ist, beschreibt die entsprechende Regel nur eine sehr geringe Menge von Beispielen.
• Post-Pruning: Aufbau eines komplexen Baumes, der anschließend beschnitten wird.
  • Beispiel: Umwandlung in Blattknoten, wenn deren Klassifizierungsfehler kleiner ist als die Summe der Fehler der nachfolgenden Knoten.