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

 (mlu-explain.github.io)
3 Punkte von GN⁺ 2026-03-02 | 1 Kommentare | Auf WhatsApp teilen
  • 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
Anzeige

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
    Anzeige
  • 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

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2026-03-02
Hacker-News-Kommentare

  • Meine Geheimwaffe, die beim Lernen von Klassifikatoren für mich sehr gut funktioniert hat, war, zuerst einen guten linearen Klassifikator zu trainieren.
    Dann habe ich einen Entscheidungsbaum trainiert, wobei ich den nichtschwellwertigen Ausgabewert dieses linearen Klassifikators als zusätzliche Feature-Dimension verwendet und das Ganze anschließend in ein System aus geboosteten Bäumen eingebettet habe.
    So gleicht das lineare Modell die Schwächen des Entscheidungsbaums aus, und umgekehrt übernimmt der Baum die Teile, mit denen sich das lineare Modell schwertut.
    Man kann auch Datenrotation oder Achsennormalisierung in Betracht ziehen, aber meistens war das nicht nötig.
    Wenn die Features allerdings sehr spärlich sind, tut sich der Baum schwer damit, Aufteilungspunkte zu finden.

    • Wenn man darüber nachdenkt, ist das ein ähnlicher Ansatz wie im Reinforcement Learning.
      Man führt zusätzliche Berechnungen auf dem ursprünglichen Zustand aus und lernt dann mit dem beobachteten Zustand.
      Im Snake-Spiel würde man zum Beispiel nicht nur die Koordinaten der Schlange verwenden, sondern auch abgeleitete Features wie die Anzahl der Fluchtwege berechnen und damit trainieren.
    • Die Achillesferse von Entscheidungsbäumen ist letztlich Feature Engineering.
      Wenn man die Daten nicht bereinigt und die Features nicht gut entwirft, fallen die Ergebnisse deutlich schlechter aus als bei Blackbox-Modellen wie neuronalen Netzen.
      Ironischerweise finden neuronale Netze solche latenten Features selbst, aber warum sie so funktionieren, ist nur schwer zu interpretieren.
    • Es gibt verschiedene Baumvarianten für unterschiedliche Ziele.
      Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT) und Hierarchical Mixture of Experts (HME) sind Beispiele dafür.
    • Ich frage mich, was genau mit der Formulierung gemeint ist, dass die „Bereiche mit gleichen Labels eine aufgeteilte Struktur haben“.
    • Diese Idee ähnelt auch dem Kern des IRM-Papers, das Arjovsky, Bottou und andere geschrieben haben.

  • Als ich um 2010 bei CERN gearbeitet habe, war der Boosted Decision Tree der beliebteste Klassifikator.
    Das lag an der Balance zwischen Erklärbarkeit und Ausdrucksstärke, und damals war man kulturell eher zurückhaltend dabei, neuronale Netze in physikalischen Analysen einzusetzen.
    Inzwischen haben sich die Zeiten stark geändert.

    • Diese Entwicklung macht mir ein wenig Sorgen.
      In der Physik ist es wichtiger, kausale Mechanismen zu verstehen, als einfach nur Kurven gut zu fitten.
      Das System der Epizykel bei Ptolemäus passte Himmelsbewegungen zwar besser an, erklärte aber nicht ihre Ursache.
    • Ich komme ebenfalls aus der theoretischen Physik, und nachdem ich Entscheidungsbäume in anderen Bereichen eingesetzt habe, denke ich, dass ihre „Erklärbarkeit“ teilweise überschätzt wird.
      Schon bei etwas größerer Tiefe wird daraus fast ein undurchdringlicher Dschungel.
      Bei neuronalen Netzen ist es ähnlich: Man kann die internen Berechnungen verfolgen, weiß am Ende aber trotzdem nicht, warum genau diese Entscheidung getroffen wurde.
    • Ich frage mich, ob Boosted Decision Tree und Boosted Random Forest dasselbe sind.

  • Auf derselben Website gibt es auch eine Erklärung zu Random Forest → mlu-explain/random-forest

  • Interessante Tatsache: Ein 1-Bit-Neural-Netzwerk (single-bit neural network) ist im Grunde ein Entscheidungsbaum.
    Theoretisch kann man die meisten neuronalen Netze in if-else-Ketten „kompilieren“, aber wann das gut funktioniert, ist noch nicht klar.

    • Ich habe das Paper „Neuronale Netze sind Entscheidungsbäume“ (arXiv:2210.05189) gelesen, und in der Praxis wird der Baum extrem groß.
      Das wirkt eher wie eine Erweiterung des Konzepts, daher ist eine direkte Abbildung schwierig.
      Deshalb wäre es gut, genauer zu erklären, in welchem Sinn das gemeint ist.
    • Ich frage mich, ob es Software oder Paper gibt, die so eine Umwandlung tatsächlich durchführen. Wäre ein interessantes Wochenendprojekt.

  • Der größte Vorteil von Entscheidungsbäumen ist ihre Geschwindigkeit.
    In einer Umgebung mit niedriger Latenz wollte ich einen baumbasierten Klassifikator durch ein kleines neuronales Netz ersetzen, aber obwohl das neuronale Netz etwas genauer war, lag seine Inferenzlatenz mehr als 100-mal höher.

    • Außerdem lässt sich ein einzelner Entscheidungsbaum leicht direkt auf ein Edge-Gerät portieren.
      Geboostete oder gebaggte Bäume sind dagegen komplex, und auch andere klassische ML-Algorithmen sind weniger portabel.

  • In einem ML-Lehrbuch, wahrscheinlich ESL, wurden Entscheidungsbäume so beschrieben:
    „Interpretierbar, schnell, arbeitet gut mit verschiedenartigen Daten, unempfindlich gegenüber Skalierung, braucht nur wenige Tuning-Parameter, aber ... funktioniert nicht gut.“
    Mit Bagging oder Boosting kann man diesen Nachteil allerdings ausgleichen, verliert dabei jedoch einen Teil der ursprünglichen Vorteile.

  • Ich mag Entscheidungsbäume wirklich sehr. Sie sind mein bevorzugter klassischer ML-Algorithmus.
    Ich habe eine rein funktionale Parallelimplementierung in GNU Guile gebaut → Code-Link
    Allerdings gibt es in Guile nichts wie NumPy oder DataFrame, daher ist die Datenrepräsentation ineffizient.

    • Mich würde interessieren, worin NumPy oder DataFrame gegenüber Guile überlegen sind.
      Guile eignet sich gut zur Manipulation von Bäumen und wirkt daher für die Implementierung von Entscheidungsbäumen natürlich.
      Mit Kompilierung zu Maschinencode wäre es aber wahrscheinlich effizienter.
      Zur Referenz lohnen sich auch Lush (https://lush.sourceforge.net/) und aiscm (https://wedesoft.github.io/aiscm/).

  • Auch die unscharfe Entscheidungsfindung von Experten lässt sich oft mit einfachen Entscheidungsbäumen oder Entscheidungsketten modellieren.
    Die Experten selbst halten ihre Entscheidungen zwar für komplex, aber tatsächlich erklärt ein einfacher Baum sie oft besser.
    Früher wirkten Regression oder distanzbasiertes Clustering eleganter, doch Bäume sind viel effektiver.
    Mehr dazu steht ausführlich in Kapitel 7 des Oxford Handbook of Expertise.

    • In einer Visualisierung, die ich früher gesehen habe, wurden Entscheidungen als Raumaufteilung in einer 2D-Ebene dargestellt.
      Im Kern teilt ein Entscheidungsbaum wie ein kD-Tree den Möglichkeitsraum auf und weist jeder Region eine Aktion zu.
      Die feinen Urteile von Experten entstehen durch die Genauigkeit der Grenzflächen, aber auch ein Baum liefert eine ziemlich gute Approximation.

  • Die Website ist interessant und die Präsentation war gut.
    Allerdings war der Farbkontrast einiger Texte zu gering, sodass sie schwer zu lesen waren.

    • Sehe ich genauso. Die Firefox-Leseansicht hilft dabei sehr.
      Barrierefreiheit ist nicht nur für Menschen mit Behinderungen da, sondern ein grundlegendes Element für Lesbarkeit.

  • Im heutigen Deep-Learning-Zeitalter werden Entscheidungsbäume unterschätzt.
    Dabei sind sie immer noch interpretierbar, schnell und ausreichend praktisch.
    Ich habe ein baumbasiertes Bewertungssystem für die Analyse von Websites gebaut,
    das Bedingungen wie „Gibt es eine Meta-Beschreibung?“, „Lädt die Seite in unter 3 Sekunden?“ und „Ist sie mobilfreundlich?“ bewertet.
    Nutzer können sofort verstehen, warum sie diese Bewertung bekommen haben.
    Warum ein neuronales Netz 73 Punkte vergeben hat, lässt sich nicht erklären, bei einem Baum aber sehr leicht.