Einleitung: Entscheidungsbäume und das Bedürfnis nach Reinheit

Entscheidungsbäume sind eine der intuitivsten und am weitesten verbreiteten Algorithmen für überwachtes Lernen im maschinellen Lernen. Sie modellieren Entscheidungen als Baumstruktur, wobei interne Knoten Tests zu Merkmalen darstellen, Zweige Ergebnisse dieser Tests darstellen und Blattknoten endgültige Vorhersagen darstellen. Ob Sie nun klassifizieren, ob es sich bei einer E-Mail um Spam handelt oder Hauspreise vorhersagen, Entscheidungsbäume bieten einen transparenten, vom Menschen lesbaren Ansatz.

Die zentrale Herausforderung beim Aufbau eines Entscheidungsbaums ist die Entscheidung , wo die Daten an jedem Knoten aufgeteilt werden. Der Algorithmus muss das Merkmal und den Split-Wert auswählen, der die Zielklassen am besten trennt. Hier kommt die entropie ins Spiel. Entropie, die aus der Informationstheorie übernommen wurde, liefert ein mathematisches Maß für Unsicherheit oder Unreinheit in einem Datensatz. Durch die Minimierung der Entropie nach jedem Split erzeugen Entscheidungsbäume zunehmend homogene Untermengen, was zu genauen und effizienten Modellen führt.

Was ist Entropie? Ein Maß für Unordnung

Im Alltagssprache bezieht sich Entropie auf Zufälligkeit oder Chaos. Im Zusammenhang mit Entscheidungsbäumen quantifiziert Entropie die Menge an Unvorhersehbarkeit in einem Datensatz in Bezug auf die Zielvariable. Wenn alle Beispiele in einem Knoten zur gleichen Klasse gehören, ist der Knoten rein und seine Entropie ist Null. Umgekehrt, wenn die Klassen gleichmäßig gemischt sind, erreicht die Entropie ihr Maximum.

Für ein binäres Klassifizierungsproblem (z. B. positiv vs. negativ) wird Entropie definiert als:

Entropie = –p+ log2(p+) – p− log2(p−)

Die Logarithmusbasis 2 wird verwendet, weil Informationen in Bits binär gemessen werden. Wenn es mehr als zwei Klassen gibt, verallgemeinert sich die Formel auf:

Entropie = –Σ pi log2(pi) für alle Klassen i.

Der resultierende Wert reicht von 0 (perfekt rein) bis log2 (k) für k Klassen (maximale Verunreinigung). Für einen binären Fall beträgt die maximale Entropie 1,0, wenn p+ = p- = 0,5 ist.

Ein schnelles Beispiel

Betrachten wir einen Datensatz von 10 Proben mit 5 positiven und 5 negativen Ergebnissen. Entropie = –0,5 log2(0,5) – 0,5 log2(0,5) = –0,5 * (–1) – 0,5 * (–1) = 0,5 + 0,5 = 1,0. Betrachten wir nun einen Datensatz mit 9 positiven und 1 negativen Ergebnissen: Entropie = –0,9 log2(0,9) – 0,1 log2(0.1) ≈ –0,9 * (–0.152) – 0,1 * (–3.322) ≈ 0,137 + 0,332 = 0,469. Der zweite Datensatz ist viel vorhersehbarer.

Warum Base 2?

Die Wahl der Basis 2 basiert auf der Informationstheorie von Claude Shannon. Ein Bit ist die grundlegende Informationseinheit, die eine binäre Wahl darstellt. Die Verwendung von Basis 2 bedeutet Entropie gibt die durchschnittliche Anzahl von Bits, die benötigt werden, um die Klasse einer Zufallsstichprobe zu codieren. Wenn Sie die Verteilung bereits kennen, bedeutet niedrigere Entropie, dass weniger Bits benötigt werden, um das Ergebnis zu kommunizieren.

Information Gain: Wie Entropie Guides Splits

Die Berechnung der Entropie ist nicht genug; das Ziel ist es, sie nach dem Aufteilen zu reduzieren. Der Informationsgewinn (IG) misst die erwartete Verringerung der Entropie, die durch die Partitionierung der Daten nach einem Feature verursacht wird. Das Feature und der Split-Wert, die den höchsten Informationsgewinn ergeben, werden für den Knoten ausgewählt.

Die Formel für den Informationsgewinn lautet:

Information Gain = Entropy(parent) – Σ (|Si| / |S|) * Entropy(Si)

Dabei ist S der übergeordnete Datensatz, Si die Child-Untermengen nach der Aufteilung und |.| die Anzahl der Proben. Die Summe ist ein gewichteter Durchschnitt der Entropien der Kinder.

Bearbeitetes Beispiel

Stellen Sie sich einen übergeordneten Knoten mit 30 Samples vor: 16 Klasse A und 14 Klasse B. Entropy(parent) = -(16/30) log2(16/30) - (14/30) log2(14/30) ≈ 0,996.

Betrachten wir nun eine Aufteilung auf Feature X, die zwei Kinder erzeugt: Child1 hat 20 Samples (15 A, 5 B) → Entropie = -0,75 log2 (0,75) - 0,25 log2 (0,25) ≈ 0,811; Child2 hat 10 Samples (1 A, 9 B) → Entropie = -0.1 log2 (0,1) - 0,9 log2 (0,9) ≈ 0,469. Gewichtete Kinderentropie = (20/30) * 0,811 + (10/30) * 0,469 ≈ 0,541 + 0,156 = 0,697. Informationsgewinn = 0,996 - 0,697 = 0,299.

Wenn ein anderer Split höhere IG ergibt, wird dieser Split bevorzugt, der Algorithmus wertet alle Merkmale und möglichen Splitschwellen aus, um den besten zu finden.

Grenzen des Informationsgewinns

Informationsgewinn neigt dazu, Merkmale mit vielen unterschiedlichen Werten zu bevorzugen (z. B. eine eindeutige ID-Spalte), weil das Aufteilen auf ein solches Merkmal viele reine Kinder erzeugt, was zu einem Überfitting führen kann. Um dem entgegenzuwirken, normalisieren Varianten wie Gain Ratio (verwendet in C4.5) IG durch die intrinsischen Informationen des Splits. Ein anderer Ansatz ist die Verwendung der Gini-Verunreinigung, die rechnerisch billiger ist und oft ähnliche Ergebnisse liefert.

Vergleich der Entropie mit der Gini-Verunreinigung

Die Gini-Verunreinigung ist ein alternatives Aufteilungskriterium, das im CART-Algorithmus (Classification and Regression Trees) verwendet wird und die Wahrscheinlichkeit misst, dass eine zufällig ausgewählte Probe falsch klassifiziert wird, wenn sie nach dem Zufallsprinzip gemäß der Klassenverteilung im Knoten markiert wird.

Gini = 1 – Σ pi2

Für einen Binärfall ist Gini = 2p+ (1 – p+). Maximaler Gini ist 0,5 (ausgewogene Klassen) und Minimum ist 0 (rein).

Sowohl die Entropie als auch die Gini-Verunreinigung sind konvexe Funktionen, was bedeutet, dass sie sich in der Praxis ähnlich verhalten. Die Wahl zwischen ihnen hängt oft von der Recheneffizienz ab: Gini benötigt keine Logarithmen, daher kann es etwas schneller sein. Die Entropie hat jedoch eine stärkere informationstheoretische Rechtfertigung. Viele Bibliotheken, einschließlich des Scikit-Learning, können beides wählen; empirisch gesehen sind die Unterschiede gering.

Entropie in Regressionsbäumen

Entscheidungsbäume können auch Regressionsprobleme lösen (vorhersagen von kontinuierlichen Werten). Bei der Regression ist Entropie nicht angemessen, weil das Ziel nicht kategorisch ist. Stattdessen verwendet der Algorithmus Varianzreduktion oder den mittleren quadrierten Fehler (MSE) als Splitting-Kriterium. Die Idee ist analog: Bei jedem Knoten teilen wir uns auf, um die gewichtete Summe der Varianzen der untergeordneten Knoten zu minimieren. Dies maximiert die Homogenität der Zielwerte in jeder Region.

Für die Regression wird die Menge oft als FLT:0 bezeichnet; die Fehlerreduktion im Quadrat wird als FLT:1 oder FLT:2 bezeichnet; das Prinzip ist genau dasselbe wie der Informationsgewinn: Messen Sie die Unreinheit (Varianz) des Elternteils, dann den gewichteten Durchschnitt der Kinder und maximieren Sie die Differenz.

Bauen Sie einen vollständigen Entscheidungsbaum: Von der Wurzel zum Blatt

Nun, da wir Entropie und Informationsgewinn verstehen, lassen Sie uns durchgehen, wie ein typischer Entscheidungsbaumlernalgorithmus (wie ID3, C4.5 oder CART) einen Baum erstellt:

  1. Beginnt mit dem gesamten Dataset am Root-Knoten.
  2. Berechnen Sie die Verunreinigung der Wurzel mit Entropie (für die Klassifizierung) oder Varianz (für die Regression).
  3. Für jedes Feature, bewerten Sie jeden möglichen Split-Punkt (für numerische Features, Sortierwerte und betrachten Sie Mittelpunkte zwischen aufeinanderfolgenden unterschiedlichen Werten; für kategorische Features, betrachten Sie Untermengen oder One-Hot-Codierung).
  4. Berechnen Sie den Informationsgewinn (oder das Gewinnverhältnis, die Gini-Reduktion usw.) für jeden Split.
  5. Wähle die Aufteilung, die den höchsten Gewinn bringt.
  6. Partitionieren Sie die Daten und wiederholen Sie rekursiv die Schritte 2-5 für jeden Kindknoten.
  7. Stopping-Kriterien verhindern unendliches Wachstum: maximale Tiefe, minimale Proben pro Blatt, minimale Verunreinigungsabnahme oder wenn alle Proben in einem Knoten zu einer Klasse gehören.
  8. Prune den Baum (entweder Pre-Pruning über Hyperparameter oder Post-Pruning durch Zurückschneiden von Zweigen, die die Leistung eines Validierungssatzes nicht verbessern), um Überanpassungen zu bekämpfen.

Umgang mit kategorischen und numerischen Merkmalen

Entropie-basiertes Splitting funktioniert für beide Arten von Features, aber der Ansatz unterscheidet sich:

  • Numerical features: Der Algorithmus sortiert die eindeutigen Werte und testet jeden möglichen Schwellenwert. Aus Gründen der Effizienz berücksichtigt er oft nur Schwellenwerte zwischen aufeinanderfolgenden sortierten Werten, bei denen sich das Klassenlabel ändert.
  • Kategorische Merkmale: Für binäre Splits kann der Algorithmus die Gruppierung von Kategorien in zwei Untergruppen in Betracht ziehen. Für Mehrweg-Splits (wie in ID3) wird jede Kategorie zu einem Zweig. Mehrweg-Splits fragmentieren jedoch Daten schnell und sind anfällig für Überanpassungen, so dass die meisten modernen Implementierungen binäre Splits sogar für kategorische Merkmale verwenden.

Umgang mit fehlenden Werten

Reale Datensätze enthalten oft fehlende Werte. Entscheidungsbäume können sie auf verschiedene Arten behandeln:

  • Surrogate splits: Beim Aufteilen auf ein Feature wird ein Backup-Feature, das am besten den Split nachahmt, für Samples verwendet, die das primäre Feature vermissen.
  • Fraktionale Instanzen: Weisen Sie eine Stichprobe mehreren Kindern zu, deren Gewichte proportional zur Wahrscheinlichkeit jedes Kindes sind, basierend auf nicht fehlenden Daten.
  • Einfache Imputation: Ersetzen Sie fehlende Werte durch den Modus oder Median, bevor Sie den Baum erstellen.

Viele Bibliotheken, wie scikit-learn, behandeln fehlende Werte intern nicht und erwarten, dass sie vorher unterstellt werden. XGBoost und LightGBM lernen jedoch während des Trainings die beste Richtung für fehlende Werte.

Überanpassung und Beschneidung

Ein Entscheidungsbaum, der bis zur maximalen Tiefe gewachsen ist, wird die Trainingsdaten, einschließlich Lärm, perfekt auswendig lernen, was zu einer schlechten Generalisierung führt. Die Entropiereduktion wird fortgesetzt, bis jedes Blatt rein ist, aber dies kommt der Testleistung selten zugute.

Pre-Pruning (Frühes Stoppen)

Stoppen Sie das Baumwachstum, bevor es sich überschneidet, indem Sie Einschränkungen anwenden: Begrenzen Sie die maximale Tiefe, erfordern Sie eine Mindestanzahl von Proben pro Blatt oder eine Mindestverringerung der Verunreinigung (z. B. muss die Entropieabnahme > 0,01 sein).

Nachbeschneidung (Kostenkomplexitätsbeschneidung)

Der Algorithmus berücksichtigt einen Kompromiss zwischen Baumkomplexität (Anzahl der Blätter) und Trainingsfehler. Ein Komplexitätsparameter (alpha) bestraft zusätzliche Blätter. Scikit-learns bietet Kostenkomplexitäts-Beschneidung über .

Beide Schnitttechniken helfen sicherzustellen, dass Entropie-getriebene Spaltungen nicht zu granular sind und dass der Baum interpretierbar bleibt, während er gut verallgemeinert wird.

Entropie in Ensemble-Methoden

Während ein einzelner Entscheidungsbaum instabil sein kann (geringfügige Datenänderungen können zu einem sehr unterschiedlichen Baum führen), bleibt die Entropie ein grundlegendes Konzept in Ensemble-Methoden:

  • Random Forests: Baue viele Bäume mit Bootstrap-Proben und zufälligen Merkmals-Untergruppen. Jeder Baum verwendet typischerweise Entropie oder Gini, um sich aufzuteilen. Der Wald durchschnittlich Vorhersagen, wodurch die Varianz reduziert wird.
  • Gradient Boosting: Bäume werden nacheinander gebaut, um Fehler früherer Bäume zu korrigieren.

Das Verständnis der Entropie hilft zu interpretieren, warum eine bestimmte Aufteilung in einem einzelnen Baum gewählt wurde, was für das Debuggen von Modellen und die Analyse der Merkmalswichtigkeit unerlässlich ist.

Praktische Überlegungen bei der Verwendung von Entropie

Erstens, berechnen Sie Entropie mit Logarithmen sorgfältig — vermeiden Sie undefinierte log(0) durch Definition von 0 log2(0) als 0. Zweitens, beachten Sie, dass Entropieberechnungen empfindlich auf Klassenungleichgewicht sind; ein Knoten mit 99% einer Klasse und 1% einer anderen Klasse hat eine niedrige Entropie, zeigt aber möglicherweise keine gute Aufteilung an, wenn die Minderheitsklasse wichtig ist. In diesem Fall ist es ratsam, Klassen zu gewichten oder alternative Metriken (z. B. F1) für die Auswertung zu verwenden.

Entscheidungsbäume mit Entropie können auch für große Datensätze speicherintensiv sein, da sie alle Merkmale und Split-Punkte auswerten. Bibliotheken verwenden Algorithmen wie sort-and-scan, um die Entropie für numerische Merkmale in O(n log n) Zeit zu berechnen.

Externe Referenzen für tieferes Lesen:

Jenseits der Klassifikation: Entropie und Informationsgewinn bei der Feature-Auswahl

Entropie wird nicht nur innerhalb von Entscheidungsbäumen verwendet, sondern unterstützt auch die Auswahl von Feature-Techniken. Gegenseitige Informationen zwischen Feature und Ziel stehen in direktem Zusammenhang mit dem Informationsgewinn. Sie können Merkmale anhand ihrer gegenseitigen Informationen einordnen, um die Dimensionalität zu reduzieren, bevor Sie andere Modelle trainieren. Dies ist eine nichtlineare Alternative zur Korrelationsanalyse.

Wenn Merkmal X beispielsweise eine hohe gegenseitige Information mit Ziel Y hat, dann reduziert das Wissen um X die Unsicherheit über Y erheblich. Dies ist genau die Verringerung der Entropie, die durch die Aufteilung auf X erreicht wird. Bibliotheken wie scikit-learn bieten und .

Grenzen von Entropie-basierten Entscheidungsbäumen

Trotz ihrer Macht haben Entscheidungsbäume, die mit Entropie gebaut wurden, einige Nachteile:

  • Instability: Kleine Datensatzvariationen können die Baumstruktur drastisch verändern.
  • Bias in Richtung Features mit vielen Levels: Informationsgewinn begünstigt High-Cardinality-Features. Gain Ratio oder die Verwendung nur binärer Splits hilft.
  • Schlechte Handhabung der additiven Struktur: Bäume sind stückweise konstante Modelle, so dass sie Schwierigkeiten haben, lineare Beziehungen zu lernen.
  • Greedy nature: Der Algorithmus macht lokal optimale Splits, die global möglicherweise nicht optimal sind.

In der Praxis ergibt die Kombination von Entropie-basierten Entscheidungsbäumen mit geeigneten Hyperparameter-Tuning- und Ensemble-Methoden robuste Modelle für viele tabellarische Datensätze.

Fazit: Entropie als Grundlage für aufschlussreiche Spaltungen

Entropie bietet eine prinzipielle, informationstheoretische Möglichkeit, die Qualität einer Teilung beim Erstellen eines Entscheidungsbaums zu bewerten. Durch die Messung der Störung in einem Datensatz und das Ziel, sie bei jedem Schritt zu reduzieren, können wir Bäume bauen, die den Feature-Raum effizient und genau unterteilen. Ob Sie ein lernender maschineller Lernprozess sind oder ein Praktiker, der Modelle einsetzt, vertieft das Verständnis der Entropie Ihr Verständnis davon, wie Entscheidungsbäume "denken". Es verbindet sich auch mit breiteren Konzepten wie gegenseitige Information, Merkmalsauswahl und sogar Datenkomprimierung.

Wenn Sie Entscheidungsbäume anwenden, denken Sie daran, dass Entropie ein Werkzeug ist – kein Ziel. Kombinieren Sie es mit geeigneten Validierungs-, Beschneidungs- und Ensembletechniken, um sein volles Potenzial zu entfalten. Und wenn Sie Datenpipelines für maschinelles Lernen verwalten, können Tools wie Directus Ihnen helfen, die hochwertigen Datensätze zu sammeln, zu organisieren und zu bedienen, von denen Entscheidungsbäume abhängen.