Entscheidungsbaum

Ein Entscheidungsbaum ist ein Modell des maschinellen Lernens, das Daten anhand aufeinanderfolgender Fragen in kleinere Gruppen aufteilt. Jeder Pfad führt von einem Startknoten über Merkmalsprüfungen zu einem Blatt mit einer Vorhersage. Bei einer Klassifikation ist das Ergebnis eine Kategorie; bei einer Regression ein Zahlenwert. Der Baum lernt die Fragen und Schwellenwerte aus Beispieldaten.

Quelle: datenbasiert.de

Was ist ein Entscheidungsbaum?

Ein Entscheidungsbaum bildet eine Folge von Wenn-dann-Regeln als Baumstruktur ab. Das Trainingsverfahren betrachtet Beispiele mit bekannten Zielwerten und sucht Merkmale, die diese Beispiele sinnvoll aufteilen. Ein trainierter Baum kann danach für neue Datensätze eine Klasse oder einen numerischen Zielwert berechnen. In der Statistik und im maschinellen Lernen wird diese Modellfamilie für überwachtes Lernen verwendet.

Beim Sortieren von Kundenanfragen könnten die Merkmale aus einem Formular stammen: Ist die Ware angekommen? Ist ein Artikel beschädigt? Aus historischen Tickets mit den richtigen Kategorien lernt der Algorithmus, welche Frage an welcher Stelle die Fälle trennt. Der spätere Entscheidungspfad lässt sich lesen, ohne dass man die komplette Trainingsdatei öffnen muss.

Ein Klassifikationsbaum unterscheidet Klassen wie „Rückgabe“ und „Rechnung“. Ein Regressionsbaum schätzt beispielsweise die Bearbeitungszeit eines Tickets in Minuten. Die Baumstruktur ist ähnlich; Zielvariable, Teilungskriterium und Vorhersage im Blatt ändern sich. Entscheidungsbäume gehören damit zu den Modellen, die auch in der Predictive Analytics für Vorhersagen eingesetzt werden.

Wie funktioniert ein Entscheidungsbaum?

Vom ersten Knoten zur Vorhersage

Oben beginnt der Baum am Wurzelknoten. Dort wird eine Bedingung geprüft, etwa Lieferung angekommen = ja. Das Ergebnis bestimmt, welchem Zweig der Datensatz folgt. Ein innerer Knoten kann eine weitere Frage stellen. Der Pfad endet an einem Blattknoten, der die Vorhersage enthält. Bei einem binären Baum teilt jede Frage die Fälle in zwei Gruppen.

Eine Vorhersage benötigt nur die Merkmale, die auf ihrem eigenen Pfad abgefragt werden. Ein Ticket kann nach der Frage zur Lieferung direkt in einem Blatt landen, während ein anderes Ticket zusätzlich eine Frage zum beschädigten Artikel durchläuft. Ein tieferer Baum stellt möglicherweise mehr Fragen und bildet feinere Gruppen. Die Baumtiefe bezeichnet den längsten Weg vom Startknoten zu einem Blatt.

Welche Frage ein Knoten stellt

Bei einem numerischen Merkmal wird häufig ein Schwellenwert getestet: Tage seit Bestellung ≤ 2?. Bei Kategorien kann eine Teilung beispielsweise prüfen, ob ein Formularfeld einen bestimmten Wert hat. Wie Kategorien und fehlende Werte verarbeitet werden, hängt von der konkreten Implementierung ab; manche Verfahren benötigen zuvor eine geeignete Kodierung. Der trainierte Baum speichert am Knoten das ausgewählte Merkmal und die Regel für die Verzweigung.

Eine Änderung knapp um den Schwellenwert kann zu einem anderen Blatt führen: 1,9 und 2,1 Tage seit Bestellung liegen auf unterschiedlichen Seiten der Frage ≤ 2 Tage. Innerhalb eines Blatts bleibt die Vorhersage dagegen gleich. Ein Regressionsbaum bildet die Eingabedaten deshalb in Bereiche mit jeweils konstantem Vorhersagewert ab. Er zeichnet keine glatte Prognosekurve.

Ein Entscheidungsbaum benötigt für numerische Merkmale gewöhnlich keine Skalierung auf ein gemeinsames Zahlenintervall: Ob ein Merkmal in Tagen oder Stunden gemessen wird, ändert die Reihenfolge der Fälle nicht, wenn der Schwellenwert entsprechend umgerechnet wird. Wichtiger ist die Verfügbarkeit der Eingabe beim späteren Einsatz. Die Bearbeitungszeit eines Tickets darf nicht als Merkmal dienen, wenn der Baum sie vor Beginn der Bearbeitung vorhersagen soll. Dagegen können Bestelldatum, Warenwert oder Formularauswahl bereits beim Eingang des Tickets bekannt sein.

Ein Beispiel: Kundenanfragen einordnen

Wie ein neuer Fall den Baum durchläuft

Die folgende kleine Datenmenge ist ein Rechenbeispiel. Von zwölf früheren Tickets gehören sechs zur Kategorie „Rückgabe“ und sechs zu „Rechnung“. Der Baum fragt zuerst: „Ist der Artikel bereits angekommen?“ Acht Tickets folgen dem Ja-Zweig; darunter sind sechs Rückgaben und zwei Rechnungsfragen. Die vier Tickets im Nein-Zweig betreffen Rechnungen.

Im Ja-Zweig kann eine zweite Frage helfen: „Ist der Artikel beschädigt?“ Unter den acht Tickets sind fünf mit beschädigtem Artikel; sie gehören in diesem Beispiel alle zur Rückgabe. Von den übrigen drei Tickets betrifft eines eine Rückgabe und zwei die Rechnung. Ein neues Ticket mit angekommenem, beschädigtem Artikel folgt also zwei Fragen und landet im Blatt „Rückgabe“.

Quelle: datenbasiert.de

Was die Vorhersage im Blatt bedeutet

Bei der Klassifikation liefert ein Blatt meist die häufigste Klasse der dort gelandeten Trainingsfälle. Im gemischten Blatt mit einem Rückgabe- und zwei Rechnungstickets wäre die Vorhersage „Rechnung“. Der Anteil der Rechnungstickets beträgt dort zwei von drei. Eine Software kann solche Klassenanteile als Wahrscheinlichkeit ausgeben; bei kleinen Blättern ist diese Zahl jedoch eine grobe Schätzung.

Wird statt der Kategorie eine Bearbeitungszeit vorhergesagt, enthält das Blatt bei einem üblichen Regressionsbaum einen aus den dortigen Trainingswerten abgeleiteten Zahlenwert, oft ihren Mittelwert. Neue Fälle im selben Blatt erhalten denselben Schätzwert. Das macht die Regel leicht lesbar, begrenzt aber die Genauigkeit innerhalb eines großen Blatts.

Wie lernt der Baum aus Beispieldaten?

Der Lernalgorithmus probiert an einem Knoten mögliche Merkmale und Teilungen aus. Er bewertet, wie gut die entstehenden Gruppen die Zielvariable trennen, wählt eine Teilung und wiederholt den Vorgang für die neuen Knoten. Dieses Vorgehen heißt rekursive Partitionierung. Eine lokal gute Teilung muss später nicht den weltweit kleinsten möglichen Baum ergeben; der Algorithmus trifft seine Wahl Schritt für Schritt.

Wie eine Teilung ausgewählt wird

Für eine binäre Teilung werden die Trainingsfälle in einen linken und einen rechten Kindknoten verschoben. Bei einem Klassifikationsbaum sollen die Klassen in diesen Gruppen möglichst eindeutig sein. Die Bewertung muss die Größe beider Gruppen berücksichtigen: Ein reiner Kindknoten mit nur einem Fall ist weniger aussagekräftig als eine Teilung, die viele Fälle klar trennt. Ein Split-Kriterium berechnet daher die gewichtete Unreinheit der Kindknoten.

Im Ticketbeispiel enthält der Startknoten gleich viele Rückgaben und Rechnungsfragen. Die Frage nach der angekommenen Lieferung erzeugt einen reinen Nein-Zweig mit vier Rechnungsfällen und einen gemischten Ja-Zweig mit acht Fällen. Der Algorithmus kann diese Teilung mit anderen möglichen Fragen vergleichen. Die tatsächliche Auswahl hängt vom gesamten Trainingsdatensatz und den geprüften Merkmalen ab.

Bei der verbreiteten CART-Variante besteht jeder Split aus zwei Kindknoten. Für numerische Merkmale werden mögliche Grenzen zwischen beobachteten Werten geprüft. Für ein kategoriales Merkmal muss die verwendete Software eine passende Aufteilung oder Kodierung bereitstellen. Ein Baum betrachtet die Merkmale an jedem Knoten erneut: Eine Preisgrenze kann weiter unten im selben Pfad erneut auftreten und einen kleineren Wertebereich abtrennen. Die resultierenden Blattbereiche lassen sich als Kombination der Bedingungen entlang des Pfads beschreiben.

Gini und Entropie bei Klassifikationsbäumen

Die Gini-Unreinheit misst, wie gemischt die Klassen an einem Knoten sind. Bei zwei Klassen mit Anteilen p und 1 − p lautet sie 1 − p² − (1 − p)². Enthält ein Knoten nur eine Klasse, ist der Gini-Wert null. Bei einer gleichmäßigen Verteilung der zwei Klassen beträgt er 0,5. Die Entropie bewertet die Klassenverteilung mit einer anderen Formel; auch hier ist eine reine Gruppe leichter vorherzusagen als eine gemischte.

Informationsgewinn bezeichnet die Verringerung der Unreinheit durch eine Teilung. Dafür wird die Unreinheit der Kindknoten nach ihrer Fallzahl gewichtet und vom Wert des Elternknotens abgezogen. Gini und Entropie sind also mögliche Maße der Unreinheit; der Gewinn beschreibt die Verbesserung nach dem Split. Je nach Verfahren und Einstellung kann sich die bevorzugte Frage unterscheiden.

Quelle: datenbasiert.de

Wie ein Regressionsbaum Fehler reduziert

Ein Regressionsbaum trennt keine Klassen, sondern numerische Zielwerte. Sollen etwa Bearbeitungszeiten vorhergesagt werden, prüft der Algorithmus, welche Teilung ähnliche Zeiten in denselben Blättern zusammenführt. Ein verbreitetes Kriterium ist der mittlere quadratische Fehler: Abweichungen der beobachteten Werte vom jeweiligen Blattmittelwert werden quadriert und gemittelt. Eine Teilung ist nützlich, wenn sie diesen Fehler über die Kindknoten senkt.

Dadurch kann eine Frage wie Bestellwert ≤ 80 Euro? für eine numerische Prognose anders bewertet werden als für eine Klassifikation. Beim Training zählen immer Zielvariable und Split-Kriterium. Ein hoher Bestellwert ist für sich genommen keine Erklärung für eine lange Bearbeitungszeit; der Baum nutzt zunächst nur den beobachteten Zusammenhang in den Trainingsdaten.

Die Blattwerte eines Regressionsbaums sind stufenförmig: Zwei Bestellungen können sich im Warenwert unterscheiden und trotzdem im selben Blatt dieselbe geschätzte Bearbeitungszeit erhalten. Ein weiterer Split kann diesen Bereich verfeinern, erzeugt aber wieder konstante Werte innerhalb der neuen Blätter. Außerhalb des im Training beobachteten Bereichs schreibt ein solcher Baum einen bisherigen Blattwert fort; er setzt keinen linearen Trend über die Trainingswerte hinaus fort. Für Nachfrageprognosen mit stark wachsendem Sortiment ist das eine relevante Eigenschaft der Modellform.

Wie verhindert man einen zu komplexen Baum?

Wachstum begrenzen und Äste zurückschneiden

Ein Baum kann so lange wachsen, bis sehr kleine Blätter fast nur noch einzelne Trainingsfälle enthalten. Dann passen die Entscheidungsregeln möglicherweise auch zufällige Besonderheiten des Datensatzes an. Diese Überanpassung (Overfitting) zeigt sich, wenn die Trainingsgenauigkeit steigt, während die Vorhersagen für neue Tickets schlechter werden.

Beim Pre-Pruning wird das Wachstum etwa durch eine maximale Tiefe oder eine Mindestzahl an Fällen pro Blatt begrenzt. Ein neuer Split kann außerdem eine Mindestverbesserung erfüllen müssen. Beim Post-Pruning werden nach dem Aufbau Äste entfernt, deren zusätzlicher Detailgrad die Vorhersage auf getrennten Daten nicht verbessert. Ein Baum mit weniger Knoten ist zudem leichter zu lesen. Die passende Grenze hängt von Datenmenge, Zielvariable und Fehlertoleranz ab.

Vorhersagen an neuen Fällen prüfen

Der Trainingsdatensatz dient zum Lernen der Regeln. Mit getrennten Validierungsdaten lassen sich Baumtiefe und Blattgröße auswählen; zurückgehaltene Testdaten prüfen danach die gewählte Variante. Bei kleinen Datensätzen kann Kreuzvalidierung helfen, Einstellungen über mehrere Aufteilungen zu vergleichen. Bei zeitabhängigen Daten sollte die Prüfung den späteren Einsatz nachbilden: Spätere Tickets gehören nicht in das Training eines Modells, das frühere Tickets vorhersagen soll.

Für eine Klassifikation reichen viele richtig zugeordnete Fälle allein nicht immer aus. Sind Rückgaben selten, muss man auch Precision und Recall für die Rückgabeklasse betrachten. Für eine numerische Bearbeitungszeit ist dagegen etwa der mittlere absolute Fehler in Minuten verständlich. Die Kennzahl muss zur Entscheidung passen, die auf die Vorhersage folgt.

Ein sinnvoller Vergleich beginnt mit einer einfachen Referenz: Für die Ticketkategorie könnte stets die häufigste Klasse vorhergesagt werden; für Bearbeitungszeiten der Mittelwert oder ein typischer Wert aus den Trainingsfällen. Erst wenn der Entscheidungsbaum auf zurückgehaltenen Fällen bessere Werte erzielt, rechtfertigen seine zusätzlichen Splits den Aufwand. Bei einem unausgeglichenen Datensatz sollte die Fehlermatrix zeigen, welche Zielklasse der Baum verpasst. Ein zufällig gemischter Testsatz kann für zeitliche Prognosen zu freundlich sein; hier müssen Trainings- und Testzeitraum zur späteren Vorhersage passen.

Was lässt sich aus dem Modell ablesen?

Den Pfad einer Vorhersage nachvollziehen

Ein einzelner Entscheidungspfad zeigt, welche Merkmale für genau diese Vorhersage geprüft wurden und welches Blatt erreicht wurde. Daraus lässt sich eine konkrete Regel lesen: „Artikel angekommen“ und „Artikel beschädigt“ führen im Beispiel zum Rückgabeblatt. Für ein anderes Ticket kann ein kürzerer Pfad gelten. Die Erklärbarkeit bezieht sich damit auf die tatsächlichen Fragen entlang des Pfads.

Die Regel beschreibt, was das Modell in den Trainingsdaten gelernt hat. Sie beweist keine Ursache. Wenn die Variable „Rechnungsnummer vorhanden“ bei Rechnungsfragen häufig vorkommt, darf daraus nicht geschlossen werden, dass die Nummer das Anliegen verursacht. Zusätzlich sollte geprüft werden, ob ein Merkmal beim späteren Einsatz überhaupt verfügbar ist; sonst entsteht Datenleckage (Data Leakage).

Merkmalswichtigkeit einordnen

Eine globale Merkmalswichtigkeit fasst zusammen, wie stark ein Merkmal im Baum zur Verringerung der Unreinheit beigetragen hat. Diese Zahl beantwortet eine andere Frage als ein einzelner Entscheidungspfad. Sie kann außerdem Merkmale mit vielen möglichen Teilungen begünstigen. Eine alternative Prüfung vertauscht die Werte eines Merkmals in getrennten Daten und misst, wie stark die Modellleistung danach sinkt. Auch dieses Verfahren beschreibt Vorhersagebeiträge, keine Ursache.

Die vertauschten Merkmalswerte sollten auf Validierungs- oder Testdaten geprüft werden, denn eine hohe Bedeutung im Training allein kann Überanpassung widerspiegeln. Sind zwei Eingabemerkmale eng korreliert, kann der Baum bei einem Split das eine wählen und das andere ignorieren. Die ausgewiesene Wichtigkeit wird dann zwischen den Merkmalen nicht zwingend gleich verteilt. Ein guter Bericht kombiniert deshalb die globalen Wichtigkeitswerte mit konkreten Entscheidungspfaden und der Modellgüte auf neuen Fällen.

Fehlende Werte und kategoriale Merkmale müssen vor der Anwendung zur gewählten Baumimplementierung passen. Manche Algorithmen leiten fehlende Werte selbst in einen Zweig; andere benötigen vorbereitete Ersatzwerte. Manche Systeme teilen Kategorien direkt, andere erwarten eine numerische Kodierung. Werden diese Regeln zwischen Training und Einsatz verändert, folgen neue Fälle möglicherweise anderen Pfaden.

Einzelner Baum und Baum-Ensembles

Ein einzelner Entscheidungsbaum erlaubt kurze, lesbare Regeln, kann aber empfindlich auf Änderungen in den Trainingsdaten reagieren. Ensemble-Verfahren kombinieren deshalb mehrere Bäume. Sie unterscheiden sich darin, wie die Bäume trainiert werden und wie ihre Vorhersagen zusammenkommen.

Random Forest

Ein Random Forest trainiert viele Entscheidungsbäume auf unterschiedlichen Stichproben der Trainingsfälle. Bei einem Split steht zudem nur eine zufällige Auswahl von Merkmalen zur Verfügung. Die Klassifikation entsteht aus den Stimmen der Bäume, eine Regression typischerweise aus dem Mittel ihrer Vorhersagen. Das Zusammenfassen kann die Schwankungen eines einzelnen tiefen Baums verringern; eine einzelne, kurze Gesamtregel liefert der Wald nicht mehr.

Die Stichproben entstehen häufig durch Ziehen mit Zurücklegen. So sieht jeder Baum eine andere Kombination der Trainingsfälle, und einzelne Fälle bleiben für diesen Baum außen vor. Diese Out-of-Bag-Fälle können zur zusätzlichen Prüfung verwendet werden. Die zufällige Merkmalsauswahl verhindert, dass bei jedem Baum immer dieselbe dominante Frage den ersten Split bestimmt. Für die abschließende Bewertung auf wirklich neuen Daten bleibt ein sauber getrenntes Testset hilfreich.

Gradient Boosting

Beim Gradient Boosting werden Bäume nacheinander ergänzt. Jeder neue Baum trägt dazu bei, die Fehler der bisherigen Modellkombination gemäß einer Verlustfunktion zu reduzieren. Anzahl und Tiefe der Bäume beeinflussen das Ergebnis; die Lernrate steuert den Beitrag einer neuen Baumstufe. Ein solcher Boosting-Verbund kann komplizierte Beziehungen in tabellarischen Daten erfassen, seine Gesamtvorhersage lässt sich jedoch nicht als ein einzelner Entscheidungspfad lesen.

Während im Random Forest viele Bäume weitgehend unabhängig entstehen und ihre Stimmen anschließend kombiniert werden, verändert Boosting die Modellvorhersage nach jeder neuen Baumstufe. Die Lernrate begrenzt den Beitrag eines neuen Baums; mehr Stufen können dann nötig sein. Zu viele Stufen oder zu tiefe Teilbäume können den Trainingsfehler senken und zugleich die Testleistung verschlechtern. Die Kombination aus Validierung und passender Baumkomplexität bleibt deshalb auch beim Ensemble entscheidend.

Entscheidungsbäume und ihre Ensembles sind damit konkrete Modelltypen innerhalb der Advanced Analytics. Die passende Variante hängt davon ab, ob eine einzelne lesbare Regel benötigt wird oder die Güte der Vorhersage auf neuen Daten stärker zählt.

Wo werden Entscheidungsbäume eingesetzt?

Entscheidungsbäume eignen sich für Aufgaben, bei denen strukturierte Merkmale und ein bekannter Zielwert vorliegen. Die Fragen des Baums können aus Kaufhistorie, Formularfeldern, Produktdaten oder Messwerten entstehen. Der Zielwert bestimmt, ob ein Klassifikations- oder Regressionsbaum trainiert wird.

• Anfragen verteilen: Ein Klassifikationsbaum ordnet Tickets nach Formularmerkmalen einem zuständigen Team zu.
• Kundenabwanderung einschätzen: Ein Baum nutzt Nutzungs- und Kaufmerkmale für die Vorhersage einer definierten Abwanderungsklasse.
• Nachfrage schätzen: Ein Regressionsbaum teilt historische Verkäufe nach Preis, Wochentag, Saison und Aktionen auf und liefert einen Zahlenwert.
• Leads priorisieren: Ein Klassifikationsmodell schätzt anhand verfügbarer Merkmale, welche Kontakte mit größerer Wahrscheinlichkeit ein festgelegtes Ziel erreichen.

Aus einer Vorhersage wird erst mit einer Regel für den nächsten Schritt eine operative Entscheidung. Eine Nachfrageprognose allein legt keine Bestellmenge fest; dafür müssen beispielsweise Lagerkapazität und Fehlmengenkosten berücksichtigt werden. Diesen Übergang von Prognosen zu Handlungsoptionen behandelt unser Artikel über Prescriptive Analytics. Für Kampagnen und Kundenanalyse bietet der Leitfaden zu Marketing Analytics den breiteren Kontext.

Fazit

Quelle: datenbasiert.de