Entscheidungsbäume

Zweck

Der Entscheidungsbaum zeichnet die Logik einer einzelnen, wiederholbaren Entscheidung: die Menge der Regeln, die aus einer Menge von Datenelementen ein Ergebnis unter mehreren auswählen. Sein eigener Wert ist räumlich. Wo eine Tabelle die Regeln in Zeilen ausrichtet, entfaltet der Baum sie als Pfade, sodass eine Anspruchsgruppe einer Folge von Bedingungen bis zu einem Ergebnis folgt, ohne ein Raster lesen zu müssen. Diese Anordnung macht lesbar, was eine Tabelle implizit lässt: Regeln, die ihre ersten Bedingungen teilen, teilen dieselben oberen Knoten.

Das erklärt die Stärke, die der BABOK der Technik zuschreibt: die Segmentierung. Eine Anfrage, ein Dossier oder einen Kunden entlang eines Pfades bis zu dem Segment oder der Handlung zu leiten, die ihm zukommt, ist genau das, was ein Baum gut zeigt. Die Entscheidung bleibt atomar, pro Durchlauf wird ein einziges Ergebnis gewählt, doch der Pfad, der dorthin führt, bleibt für jemanden lesbar, der die Notation nicht kennt.

Das Liefergut ist der Baum selbst: eine Wurzel, Entscheidungsknoten, die je ein Datenelement prüfen, Äste, die die Bedingungen tragen, und Blätter, die die Ergebnisse tragen, mit der Garantie, dass jede gültige Menge von Eingaben genau ein Blatt erreicht. Eine Variante beantwortet ein anderes Ziel, den Vergleich von Optionen, deren Folgen ungewiss sind. Sie fügt Zufallsknoten hinzu, eine Wahrscheinlichkeit je ausgehendem Ast und eine Auszahlung an jedem Blatt, und wählt dann die Option mit dem höchsten Erwartungswert. Beide teilen die Baumform, sie beantworten nicht dieselbe Frage, und sie zu verwechseln ist der erste Fallstrick der Technik.

Anwendung

Wann einsetzen

• Regeln, die ihre ersten Bedingungen teilen: die oberen Knoten machen die gemeinsame Struktur sichtbar.
• Segmentierung eines Kundenstamms oder eines Dossier-Flusses: jede Eingabe zu ihrem Segment oder ihrer Handlung leiten.
• Kleine oder mittlere Regelmenge zur Kommunikation: einem Pfad folgt man schneller als einem dichten Raster.
• Entscheidung mit sequenziellen, abhängigen Bedingungen: wenn die Reihenfolge der Auswertung selbst Bedeutung trägt, zeigt der Baum sie.
• Wahl zwischen Optionen unter Unsicherheit: die Variante mit Zufallsknoten vergleicht die Erwartungswerte.

Wann nicht einsetzen

• Viele unabhängige Bedingungen auf gemeinsamen Daten: der Baum explodiert und dupliziert seine Teilbäume, besser eine Entscheidungstabelle.
• Komplexe Entscheidung, die sich in Teilentscheidungen zerlegt: ein einzelner Baum verbirgt die Abhängigkeiten, zuerst mit einem Entscheidungsanforderungsdiagramm kartieren.
• Aus historischen Daten zu lernende Logik: das ist statistische Klassifikation, sie gehört zum Data Mining.

Beschreibung

Die Elemente des Baums

Vier Elemente bilden den Baum, und jedes trägt eine Bedingung, die eingehalten werden muss, sonst entsteht ein Baum, der lügt. Die Entscheidungsknoten sind die inneren Knoten; jeder prüft ein einziges Datenelement, eine Bedingungsvariable wie den Betrag eines Kredits, ein Alter oder eine Verschuldungsquote. Ihre Reihenfolge zählt: das trennschärfste Element wird nahe der Wurzel platziert, weil es die Fälle am frühesten trennt und den Baum klein hält. Die Äste, die einen Knoten verlassen, tragen je eine Bedingung auf dem geprüften Element, und die Äste desselben Knotens müssen wechselseitig ausschliessend und erschöpfend sein: kein Wert fällt in zwei Äste, kein Wert fällt aus allen heraus. Die Blätter tragen die Ergebnisse, eines je Pfad, und die Menge der Blätter muss ebenfalls wechselseitig ausschliessend und gemeinsam erschöpfend bleiben, sodass jede gültige Menge von Eingaben auf genau einem Blatt landet. Die Ebenen schliesslich entsprechen konventionsgemäss je einem Datenelement: eine Ebene fragt nach dem Betrag, die nächste nach der Verschuldungsquote und so weiter. Der BABOK formuliert die Eigenschaft, die das Ganze zusammenhält, so: jeder vollständige Pfad, von der Wurzel bis zum Blatt, ist eine Regel und nur eine.

Den Baum aufbauen

Der Standard gibt die Elemente an, nicht eine nummerierte Prozedur. Die Praxis ordnet sie zu einer Abfolge.

1. Die Entscheidung und ihre Ergebnismenge benennen
   Die Entscheidung als eindeutige Aussage formulieren und die möglichen Handlungen auflisten, die zu den Blättern werden.
2. Die Datenelemente auflisten
   Jene, von denen die Entscheidung abhängt, nur jene, die das Ergebnis kippen.
3. Die Elemente ordnen
   Nahe der Wurzel das trennschärfste Element platzieren, oder jenes, das die meisten Regeln teilen, damit die gemeinsame Struktur an die Spitze des Baums steigt.
4. Den Baum zeichnen
   Ein Datenelement je Ebene, ein Ast je Bedingungswert, bis jeder Pfad ein Ergebnis erreicht.
5. Mit drei Kontrollen validieren
   Die Vollständigkeit, jeder Pfad endet auf einem Blatt und kein Wert bleibt ohne Ast; die Konsistenz, keine Menge von Eingaben erfüllt zwei Pfade, die zu unterschiedlichen Ergebnissen führen; die Ausschliesslichkeit, die Äste jedes Knotens überschneiden sich nicht.

Die Variante der Entscheidungsanalyse

Dieselbe Form dient einem anderen Ziel, wenn die Folgen einer Wahl ungewiss sind, und die Notation erhält dann zwei Knotenformen, die auseinandergehalten werden müssen. Ein Entscheidungsknoten, als Quadrat gezeichnet, ist ein Punkt, an dem der Analyst zwischen Optionen wählt. Ein Zufallsknoten, als Kreis gezeichnet, ist ein Punkt, an dem das Ergebnis der Wahl entzogen ist: jeder ausgehende Ast trägt eine Wahrscheinlichkeit, und die Wahrscheinlichkeiten desselben Zufallsknotens summieren sich zu 1. Jedes Blatt trägt eine Auszahlung, in der Regel einen Wert in Franken. Der Baum wird durch Rückwärtsrechnung ausgewertet, von den Blättern zur Wurzel: an jedem Zufallsknoten wird der Erwartungswert berechnet, die Summe der Wahrscheinlichkeiten mal den Auszahlungen, und an jedem Entscheidungsknoten wird der Ast mit dem besten Erwartungswert gewählt. Das ist die Analyse über den Erwartungswert des Geldwerts, die das PMI zu den Werkzeugen der quantitativen Risikoanalyse zählt. Die beiden Knotenformen zu beschriften trägt den Sinn: eine Wahrscheinlichkeit auf einem Ast, den der Analyst steuert, ergibt keinen Sinn, und es ist die Unterscheidung von Quadrat und Kreis, die dies verbietet.

Baum, Tabelle und Anforderungsdiagramm

Drei Techniken der Entscheidungsmodellierung ähneln sich genug, um verwechselt zu werden, und die Grenze entscheidet über die richtige Wahl. Die Entscheidungstabelle trägt dieselbe Regellogik einer atomaren Entscheidung, in tabellarischer Form: eine Zeile je Regel, eine Spalte je Bedingung oder Handlung. Gleiche Logik, andere Form. Die Tabelle gewinnt, wenn die Regeln zahlreich und unabhängig sind und man Vollständigkeit und Widerspruchsfreiheit kontrollieren will; der Baum gewinnt, wenn die Regeln Bedingungen teilen und man den Pfad und die Segmentierung zeigen will. Das Entscheidungsanforderungsdiagramm ist etwas anderes: die Karte davon, was was speist. Es zeigt, wie sich eine komplexe Entscheidung in Teilentscheidungen, Eingabedaten, Geschäftswissensmodelle und Wissensquellen zerlegt, in einem Netz verbunden. Ein einzelner Knoten dieses Diagramms, ein Wissensmodell, kann selbst einen Baum oder eine Tabelle enthalten. Tabelle und Baum sind zwei Zeichnungen der Regeln einer Entscheidung; das Anforderungsdiagramm ist die Zeichnung davon, wie sich mehrere Entscheidungen verbinden.

Die Fallstricke

Kombinatorische Explosion

Jedes neue Datenelement kann die Zahl der Blätter vervielfachen, und der Baum wird unlesbar. Ein Baum, der über die Seite hinausgewachsen ist, zeigt an, dass zu einer Tabelle gewechselt werden muss.

Duplizierte oder unausgewogene Teilbäume

Dieselbe Teilentscheidung, die unter mehreren Ästen wiederkehrt, ist ein starkes Zeichen dafür, dass die Logik in Wahrheit tabellarisch ist, oder dass eine geteilte Teilentscheidung in ein Anforderungsdiagramm ausgelagert werden sollte.

Unvollständigkeit

Ein fehlender Ast, ein nicht vorgesehener Wert lässt eine Eingabe ohne Ergebnis: die Entscheidung scheitert stumm oder rutscht durch, ohne dass sie jemand entschieden hätte.

Regeln, die sich überschneiden oder widersprechen

Zwei Pfade, die eine reale Eingabe erfüllt, ergeben zwei Ergebnisse. Der Baum verbirgt das weniger als eine Tabelle, doch verschachtelte Bedingungen können es dennoch verdecken.

Verborgene oder vermengte Wahrscheinlichkeiten

Den Regelbaum und den Erwartungswertbaum zu vermischen, ohne zu sagen, welchen man zeichnet, führt den Leser in die Irre. Ein Regelbaum trägt keine Wahrscheinlichkeit; die Äste eines Zufallsknotens in einem Erwartungswertbaum summieren sich zu 1. Die Knotenformen zu beschriften vermeidet die Verwechslung.

Handgemachte Überanpassung

Für jeden Sonderfall des letzten Quartals einen eigenen Ast hinzuzufügen, meisselt am Ende Anekdoten statt einer Richtlinie ein. Ein Sonderfall gehört in der Regel zu einer Ausnahmeregel.

Schlechte Wurzelwahl

Eine schlecht gewählte Reihenfolge der Datenelemente macht denselben Baum um ein Mehrfaches grösser und schwerer lesbar, als er sein müsste.

KI-Betrachtungen

Eine Schwierigkeit, die dieser Technik eigen ist, rührt daher, dass eine andere Disziplin ihr Form und Namen entlehnt hat. Der Entscheidungsbaum eines Business Analysten ist eine konstruierte und gesteuerte Kodierung bekannter Regeln. Der Entscheidungsbaum des maschinellen Lernens (CART, ID3, C4.5 oder ein Ensemble wie der Random Forest oder das Gradient Boosting) wird aus historischen Daten induziert: ein Algorithmus wählt die Schnitte, die den Informationsgewinn maximieren oder die Unreinheit minimieren, um ein Ergebnis zu prognostizieren. Gleiche Zeichnung, umgekehrte Erkenntnislehre, die eine aus der Richtlinie geschrieben, die andere aus den Daten erschlossen.

Die Unterstützung dient drei Aufgaben. Sie erzeugt einen ersten Entwurf eines Baums aus einem dokumentierten Regelbestand oder einer Entscheidungstabelle und wandelt das eine in das andere um. Sie führt eine mechanische Prüfung durch: einen Pfad ohne Blatt aufspüren, einen unerreichbaren Ast, zwei sich überschneidende Regeln. Sie schlägt eine Reihenfolge der Schnitte vor, aus vergangenen Entscheidungen gezogen, als Ausgangspunkt, den der Analyst danach steuert. Das sind Gewinne bei Aufbereitung und Kontrolle. Das Urteil bleibt beim Analysten.

Drei Grenzen sind fest. Ein induzierter Baum darf niemals stillschweigend zur gesteuerten Entscheidungslogik werden: in einem regulierten Schweizer Rahmen, einer Kreditvergabe nach dem Konsumkreditgesetz, einer Regel zur Versicherungsberechtigung, muss die Entscheidung erklärbar und im Hinblick auf Richtlinie und Gesetz vertretbar sein. Die Verzerrungen der Trainingsdaten und verborgene Stellvertretervariablen gehen unsichtbar in einen induzierten Baum ein, wo ein gesteuerter Regelsatz prüfbar ist. Schliesslich sind die Wahrscheinlichkeiten eines Erwartungswertbaums ein Urteil über die Welt: ein Modell kann sie vorschlagen, eine Anspruchsgruppe besitzt sie.

Beispiele

Einen Konsumkreditantrag weiterleiten

Eine Entscheidung über die Vergabe eines Konsumkredits nach dem Konsumkreditgesetz wird über zwei Datenelemente weitergeleitet, den beantragten Betrag und die Verschuldungsquote des Antragstellers. Der Baum trägt vier Regeln, eine je Pfad, und die beiden Regeln unter jedem Ast des Betrags teilen ihre erste Bedingung, wobei dieser gemeinsame Knoten nur einmal gezeichnet wird: das ist der Musterfall von Regeln, die eine Bedingung teilen, was die Zeichnung besser zeigt als ein Raster. Dieselben vier Regeln liessen sich ebenso gut als Entscheidungstabelle schreiben; der Baum wird gewählt, weil der Pfad einem Schalter den Verlauf eines Antrags auf einen Blick gibt.

Unter Unsicherheit über eine Ausschreibung entscheiden

Ein KMU wägt ab, ob es ein Angebot auf eine öffentliche Ausschreibung einreichen soll. Die Entscheidung, ein Quadratknoten, stellt Bieten und Nicht-Bieten gegenüber. Bieten führt zu einem Zufallsknoten, einem Kreis: der Auftrag wird mit einer Wahrscheinlichkeit von 0.35 für eine Auszahlung von CHF 52'000 gewonnen (Nettomarge des Auftrags von CHF 60'000 abzüglich CHF 8'000 Angebotskosten), mit einer Wahrscheinlichkeit von 0.65 für einen Verlust von CHF 8'000 verloren, die vergeblich aufgewendeten Angebotskosten. Der Erwartungswert von Bieten beträgt 0.35 × 52'000 + 0.65 × (−8'000), also CHF 13'000, gegenüber CHF 0 für Nicht-Bieten: es wird geboten. Der einzige Punkt, den ein Leser übersehen könnte, ist, dass die Schlussfolgerung an der Wahrscheinlichkeit hängt: unterhalb einer Rentabilitätsschwelle von etwa 0.13 fällt der Erwartungswert unter null und die Entscheidung kehrt sich um.

Visualisierungen

Der Regelbaum wird als rechteckige Knoten gezeichnet, die durch beschriftete Äste verbunden sind, gelesen von der Wurzel, links oder oben, zu den Blättern. Der Fächer der Äste an einem Knoten ist der Ort, an dem sich die Ausschliesslichkeit ablesen lässt: jeder ausgehende Ast ist ein Wert des geprüften Elements, und zusammen müssen sie alle Werte abdecken. Der geteilte Teilbaum liest sich als gemeinsamer Vorfahr, ein wurzelnaher Knoten, der auf dem Pfad jeder Regel unter ihm liegt, was eine Tabelle nicht auf einen Blick zeigt.

Die Variante der Entscheidungsanalyse verwendet zwei verschiedene Formen: ein Quadrat für einen Knoten, den der Analyst steuert, ein Kreis für einen Knoten, den die Welt steuert. Die Unterscheidung zu verlieren heisst den Sinn zu verlieren, denn eine Wahrscheinlichkeit auf einem Ast, den der Analyst steuert, wäre widersinnig. Die Zeichnung trägt die Natur des Knotens; eine Tabelle derselben Zahlen trägt sie nicht.

Jenseits einer Handvoll Datenelemente läuft der Baum über die Seite hinaus und dupliziert seine Teilbäume. Das ist das Signal, die Darstellung zu wechseln: die Logik, die den Baum zum Explodieren brachte, ist jene, die eine Tabelle kompakt hält, und der Übergang vom einen zum anderen ändert nur die Zeichnung, die Regeln bleiben dieselben.

Aufwand

Werkzeuge

Whiteboard und Papier genügen für erste Entwürfe und Workshops: solange die Reihenfolge der Elemente noch diskutiert wird, ist das Verschieben eines Astes gratis.

Die Tabellenkalkulation trägt dieselben Regeln als Entscheidungstabelle, sobald sie sich vermehren, und sie hält die Rückwärtsrechnung der Erwartungswertvariante, eine Spalte mit Wahrscheinlichkeiten, eine Spalte mit Auszahlungen, einen Erwartungswert je Knoten.

Die Diagrammwerkzeuge (draw.io/diagrams.net, Lucidchart, Visio) erzeugen einen sauberen Baum zum Veröffentlichen, Prüfen oder Einbinden in ein Dokument. Sie zeichnen, sie prüfen weder Vollständigkeit noch Ausschliesslichkeit.

Die DMN- und Entscheidungsmanagement-Plattformen (Camunda, Drools/KIE, Signavio) sind die Ebene, auf der die Entscheidung ausgeführt wird. Sie normieren sich auf die Entscheidungstabelle und das Anforderungsdiagramm, sodass ein Baum dort in der Regel zuerst entworfen und dann für die Ausführung in eine Tabelle übertragen wird.

Die Werkzeuge der Entscheidungsanalyse (PrecisionTree und @RISK, TreeAge, das Paket dtree unter R) dienen der Variante mit Zufallsknoten: sie halten die Wahrscheinlichkeiten, die Auszahlungen und die Rückwärtsrechnung des Erwartungswerts und berechnen die Rentabilitätsschwelle, jenseits derer sich die Entscheidung umkehrt.

Quellen

• IIBA, A Guide to the Business Analysis Body of Knowledge (BABOK Guide) v3, §10.17 Decision Modelling: die Definition des Entscheidungsbaums, die Eigenschaft, die jeden Pfad zu einer Regel macht, das Teilen der Bedingungen, die Stärke in der Segmentierung und die Grenzen der Entscheidungsmodellierung.
• Object Management Group, Decision Model and Notation (DMN): der Kontext der Familie der Entscheidungsmodellierung und ihrer Nachbarn. Die OMG normiert die Entscheidungstabelle und das Entscheidungsanforderungsdiagramm, nicht eine Baumnotation.
• PMI, A Guide to the Project Management Body of Knowledge (PMBOK Guide): die Behandlung des Entscheidungsbaums über den Erwartungswert des Geldwerts innerhalb der quantitativen Risikoanalyse, die die Variante mit Entscheidungs- und Zufallsknoten begründet.
• Howard Raiffa, Decision Analysis: Introductory Lectures on Choices under Uncertainty, Addison-Wesley, 1968: die primäre Referenz für den Baum der Entscheidungsanalyse, Entscheidungs- und Zufallsknoten, Erwartungswert und Auswertung durch Rückwärtsrechnung.