💻 computer science

Ternary Decision Trees with Locally-Adaptive Uncertainty Zones

Dieser Beitrag stellt ternäre Entscheidungsbäume vor, die den Standard-CART durch das Hinzufügen lokal adaptiver Unsicherheitszonen an den Split-Knoten erweitern, wobei für mehrdeutige Instanzen eine gewichtete Mischung der Kindvorhersagen verwendet wird, und zeigt, dass dieser Ansatz die Entscheidungsgenauigkeit über diverse Datensätze hinweg signifikant verbessert und gleichzeitig handlungsrelevante Unsicherheitsflaggen bereitstellt, ohne externe Hyperparameter zu erfordern.

Ursprüngliche Autoren: William Smits

Veröffentlicht 2026-05-22

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: William Smits

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Richter, der über einen Gerichtssaal präsidiert. In einem Standard-Entscheidungsbaum (der Art, die Computer normalerweise verwenden) wird jeder Fall in eines von zwei Fächern gezwungen: Schuldig oder Nicht schuldig.

Der Richter trifft diese Entscheidung auf Basis einer einzigen, harten Linie. Zum Beispiel: „Wenn die Geschwindigkeit über 60 Meilen pro Stunde liegt, sind Sie schuldig."

Wenn Sie 61 Meilen pro Stunde gefahren sind, sind Sie schuldig.
Wenn Sie 100 Meilen pro Stunde gefahren sind, sind Sie ebenfalls schuldig.

Für den Standard-Richter fühlen sich diese beiden Fälle exakt gleich an. In der Realität befindet sich die Person, die 61 Meilen pro Stunde fährt, jedoch genau am Rand des Gesetzes. Vielleicht war der Tacho leicht falsch eingestellt, oder die Straßenverhältnisse waren tückisch. Die Person, die 100 Meilen pro Stunde fährt, ist jedoch eindeutig und mit Sicherheit schuldig. Standard-Entscheidungsbäume behandeln beide mit demselben Vertrauensniveau, was riskant sein kann.

Die neue Idee: Der Richter im „Graubereich"

Dieser Artikel stellt eine neue Art von Richter vor, die Ternärer Entscheidungsbaum genannt wird. Anstatt nur zwei Fächer zu haben, verfügt dieser Richter über eine dritte Option: einen „Graubereich" (oder einen „Unsicherheitsbereich").

So funktioniert es:

Die klaren Fälle: Wenn Sie 100 Meilen pro Stunde fahren, sagt der Richter: „Schuldig!" (Sicher). Wenn Sie 40 Meilen pro Stunde fahren, sagt der Richter: „Nicht schuldig!" (Sicher).
Der Graubereich: Wenn Sie 61 Meilen pro Stunde fahren (gerade eben über dem Limit), zwingt der Richter kein einziges Urteil auf. Stattdessen sagt er: „Unentschieden."

Wenn ein Fall im Bereich „Unentschieden" landet, wirft der Richter den Fall nicht weg. Er gibt Ihnen immer noch eine Vorhersage, aber es ist eine gemischte Vorhersage. Stellen Sie sich vor, der Richter fragt zwei andere Experten (einen, der zu „Schuldig" neigt, und einen, der zu „Nicht schuldig" neigt), um sich einzubringen. Sie mischen ihre Meinungen zusammen, um Ihnen eine endgültige Antwort zu geben, aber sie kleben auch einen großen Aufkleber auf Ihre Akte, der sagt: „Vorsicht: Dies war ein knapper Fall."

Wie weiß der Richter, wo er die Graue Linie ziehen soll?

Der schwierige Teil besteht darin zu entscheiden, wie breit dieser „Graubereich" sein soll. Sollte er 1 Meile breit sein? 5 Meilen breit?

Frühere Methoden verlangten, dass der Richter über ein Handbuch oder einen Sensor verfügt, der ihm genau sagt, wie viel Fehler im Tacho steckt. Doch dieser Artikel sagt: „Wir brauchen keine zusätzlichen Werkzeuge. Wir können es herausfinden, indem wir uns nur die Beweise ansehen, die bereits im Raum sind."

Die Autoren erfanden fünf verschiedene Methoden, mit denen der Richter die Größe dieses Graubereichs allein anhand der Daten des aktuellen Falls berechnen kann:

Die „Flache Spitze"-Methode (Qualitätsplateau): Wenn die Beweise für mehrere verschiedene Geschwindigkeitsbegrenzungen fast gleich gut sind, weiß der Richter, dass die Linie unscharf ist, und macht den Graubereich breiter.
Die „Vollgepackter Raum"-Methode (Klassenüberlappung): Wenn die „Schuldigen" und die „Nicht Schuldigen" alle direkt nebeneinander im Gerichtssaal stehen, weiß der Richter, dass es sich um einen unübersichtlichen Bereich handelt, und erweitert den Graubereich.
Die „Vertrauenswert"-Methode (Gain Ratio): Wenn die Aufteilung der Daten sehr schwach ist (die Beweise sind verwirrend), erweitert der Richter den Graubereich.
Die „Wiedergabe"-Methode (Node Bootstrap): Der Richter stellt sich vor, den Prozess 10 oder 20 Mal mit leicht unterschiedlichen Gruppen von Zeugen zu wiederholen. Wenn sich das Urteil jedes Mal ändert, weiß der Richter, dass die Linie instabil ist, und macht den Graubereich größer.
Die „Nächster Nachbar"-Methode (Margin): Der Richter betrachtet die beiden Personen, die auf gegenüberliegenden Seiten am nächsten an der Linie stehen. Wenn sie direkt nebeneinander stehen, ist der Graubereich winzig. Wenn zwischen ihnen eine große Lücke besteht, ist der Graubereich größer.

Was haben sie herausgefunden?

Die Autoren testeten diesen neuen „Graubereich"-Richter an 72 verschiedenen realen Datensätzen (wie medizinische Aufzeichnungen, Finanzdaten und synthetische Rätsel).

Das Ergebnis: Die neuen Richter waren viel besser darin, sicher zu sein, wenn sie recht hatten. Indem sie die „knappen Fälle" (die Graubereich-Fälle) markierten und sie anders behandelten, wurde das System bei den Fällen, die es entschied, genauer.
Der Gewinner: Eine Methode namens „Margin" (die „Nächster Nachbar"-Methode) war der beste Allrounder. Sie benötigte keine zusätzlichen Einstellungen, war schnell und funktionierte hervorragend. Sie markierte etwa 17 % der Fälle als „knappe Fälle", aber die verbleibenden 83 % wurden mit deutlich höherer Genauigkeit entschieden als bei Standardbäumen.
Medizinisches Beispiel: Bei einem Datensatz über Mammographien (Brustkrebs-Screening) markierte die neue Methode etwa 11 % der Fälle als „knappe Fälle". Für diese spezifischen Fälle schlug das System eine zweite Untersuchung vor. Dies ermöglichte dem System, bei den eindeutigen Fällen genauer zu sein, während diejenigen, die zusätzliche Aufmerksamkeit benötigten, hervorgehoben wurden.

Das Fazit

Standard-Entscheidungsbäume sind wie ein starrer Schalter: An oder Aus.
Dieser Artikel führt einen Dimmer ein. Er ermöglicht es dem Computer, bei den schwierigen Fällen zu sagen: „Ich bin ziemlich sicher, aber ich bin nicht zu 100 % sicher."

Indem diese „knappen Fälle" automatisch nur mit den vorliegenden Daten identifiziert werden, kann das System nachgelagerte Anwendungen (wie einen Arzt oder einen Kreditbeauftragten) warnen, diesen spezifischen Fällen besondere Aufmerksamkeit zu widmen, anstatt blind einem selbstbewusst klingenden, aber potenziell wackeligen Vorhersageergebnis zu vertrauen.

Technischer Zusammenfassung: Ternäre Entscheidungsbäume mit lokal-adaptiven Unsicherheitszonen

Problemstellung

Standard-Entscheidungsbäume, insbesondere solche, die auf dem CART-Algorithmus basieren, unterteilen den Merkmalsraum mittels harter binärer Schwellenwerte. Dieser Mechanismus weist Instanzen unabhängig von ihrer Nähe zur Entscheidungsgrenze identisches Vertrauen zu. Folglich wird eine Instanz, die weit entfernt vom optimalen Schwellenwert $\theta$ liegt, mit derselben Gewissheit behandelt wie eine, die direkt darauf sitzt. Diese „harte Verpflichtung" erzeugt eine bekannte Schwäche: Sie überhöht die Gewissheit für Instanzen in der Nähe von Grenzen, wo die gelernte Aufteilung am wenigsten zuverlässig ist, und signalisiert nachgelagerten Anwendungen nicht, dass eine Vorhersage möglicherweise mehrdeutig ist.

Bestehende Ansätze zur Behandlung von Unsicherheit verlassen sich häufig auf externe Rauschspezifikationen (z. B. bekannte Sensorfehler) oder globale Schwellenwerte, die aus datensatzweiten Statistiken abgeleitet werden. Diese Methoden passen sich nicht lokal an die spezifische Aufteilungsqualität oder Datenverteilung an jedem Knoten an. Darüber hinaus fehlen Ansätzen wie unscharfen Entscheidungsbäumen oder weichen Entscheidungsbäumen oft explizite, interpretierbare Unsicherheitszonen, die aus lokalen Aufteilungsstatistiken abgeleitet sind.

Methodik

Die Arbeit stellt Ternäre Entscheidungsbäume vor, die Standard-Binäraufteilungen um eine lokal-adaptive Unsicherheitszone mit der Halbbreite $\delta$ erweitern, die auf dem optimalen Schwellenwert $\theta^*$ zentriert ist.

Die ternäre Auswertung

Für ein Merkmal $x_f$ und einen Schwellenwert $\theta^*$ ist die Entscheidungslogik wie folgt definiert:

Wahr (Entschieden): $x_f > \theta^* + \delta$
Falsch (Entschieden): $x_f \leq \theta^* - \delta$
Undec (Grenze-unsicher): $\theta^* - \delta < x_f \leq \theta^* + \delta$

Instanzen, die in die Undec-Zone fallen, enthalten sich nicht der Vorhersage. Stattdessen erhalten sie eine Vorhersage, die durch eine distanzgewichtete Verschmelzung der Wahrscheinlichkeitsausgaben beider Kindunterbäume gebildet wird. Entscheidend ist, dass diese Instanzen als „grenzunsicher" gekennzeichnet werden, was es nachgelagerten Systemen ermöglicht, sie unterschiedlich zu behandeln (z. B. Weiterleitung zur menschlichen Überprüfung), ohne eine Klassenvorhersage zurückzuhalten.

Lokale Berechnung von $\delta$

Der wesentliche technische Beitrag besteht darin, $\delta$ lokal an jedem Knoten unter Verwendung von Statistiken abzuleiten, die bereits während der Standard-CART-Aufteilungsfindung berechnet werden, ohne externe Daten oder Rauschmodellen zu benötigen. Die Arbeit schlägt fünf Methoden vor und evaluiert diese:

Qualitäts-Plateau ( $\delta_{QP}$ ): Misst die Breite des „Plateaus" in der Kurve des Aufteilungskriteriums (z. B. Gini-Gewinn) um $\theta^*$ herum. Ein breites Plateau zeigt an, dass die Daten den optimalen Aufteilungsstandort nicht präzise einschränken.
Klassen-Überlappung ( $\delta_{CO}$ ): Berechnet die Breite des Bereichs, in dem sich die klassenbedingten Merkmalsverteilungen überlappen, basierend auf empirischen Perzentilen.
Gewinn-Verhältnis ( $\delta_{GR}$ ): Skaliert den Merkmalsbereich umgekehrt proportional zum Gewinnverhältnis (Informationsgewinn relativ zur Aufteilungs-Entropie). Niedrige Gewinnverhältnisse deuten auf mehrdeutige Aufteilungen hin, was zu einem größeren $\delta$ führt.
Knoten-Bootstrap ( $\delta_{NB}$ ): Misst die Standardabweichung des optimalen Schwellenwerts $\theta^*$ über Bootstrap-Resamples der Trainingsdaten des Knotens. Dies quantifiziert direkt die Instabilität des Schwellenwerts.
Rand ( $\delta_{M}$ ): Inspiriert von Support Vector Machines, definiert dies $\delta$ als den Abstand von $\theta^*$ zum nächsten Trainingsbeispiel der anderen Klasse (dem „Support Vector" an diesem Knoten). Wenn die Aufteilung perfekt sauber ist, wird der physische Abstand zwischen benachbarten Datenpunkten verwendet.

Routing-Architekturen

Zwei Architekturen wurden zur Weiterleitung unsicherer Instanzen evaluiert:

Probabilistisches Routing: Die Baumstruktur bleibt binär. Während der Vorhersage werden Instanzen in der Unsicherheitszone mit Gewichten, die umgekehrt proportional zu ihrem Abstand vom Schwellenwert sind, zu beiden Kindern weitergeleitet, und die Ausgaben werden verschmolzen.
Harter mittlerer Ast: Ein dritter Kindknoten wird zur Baumstruktur hinzugefügt, der ausschließlich auf Instanzen innerhalb der Unsicherheitszone trainiert wird.
Experimentelle Ergebnisse zeigten, dass das probabilistische Routing im Allgemeinen dem Ansatz mit hartem mittleren Ast überlegen ist, da Letzteres unsichere Beispiele aus den Trainingssets der linken und rechten Äste entfernt und deren Qualität verschlechtert.

Hauptbeiträge

Rahmenwerk: Einführung ternärer Entscheidungsbäume, die für jede Aufteilung eine prinzipielle, lokal-adaptive Unsicherheitszone bereitstellen.
Fünf Schätzmethoden: Herleitung von fünf unterschiedlichen Methoden zur Berechnung von $\delta$ unter Verwendung ausschließlich standardmäßiger CART-Aufteilungsstatistiken, wodurch externe Rauschmodelle überflüssig werden.
Routing-Evaluation: Vergleichende Analyse von probabilistischem versus hartem mittlerem Routing, die die Überlegenheit der probabilistischen Verschmelzung für die meisten Methoden nachweist.
Umfassende empirische Evaluation: Evaluation über 72 OpenML-CC18-Datensätze, drei synthetische Breiman-Benchmarks (mit bekannten Bayes-Fehlern) und vier hochriskante medizinische/finanzielle Datensätze.
Diagnostisches Rahmenwerk: Einführung des Undecided/Bayes (U/B)-Verhältnisses, um zu bewerten, wie gut die Kennzeichnungsrate einer Methode mit dem theoretisch irreduziblen Fehler eines Datensatzes übereinstimmt.

Ergebnisse

Breite Gültigkeit (OpenML-CC18)

Über 72 Datensätze hinweg übertrafen alle fünf Methoden mit probabilistischem Routing die Standard-CART-Baseline bei der Entschiedenen Genauigkeit (Genauigkeit, beschränkt auf nicht-unsichere Instanzen) signifikant mit $p \leq 0.001$ .

Rand-Methode: Erzielte die beste Effizienz (Genauigkeitsgewinn pro Einheit der Kennzeichnungsrate, $\eta = 0.104$ ). Sie gewann bei 42 von 72 Datensätzen, kennzeichnete nur 16,7 % der Instanzen als unsicher und benötigte keine zusätzlichen Hyperparameter.
Klassen-Überlappung & Gewinn-Verhältnis: Erzielten eine hohe entschiedene Genauigkeit, kennzeichneten jedoch einen großen Anteil der Instanzen (71 % bzw. 58 %) als unsicher, was zu einer geringeren Effizienz führte.
Knoten-Bootstrap: Leistete gut, war jedoch rechenintensiv und wurde aus Datensätzen mit $N > 20.000$ ausgeschlossen.

Theoretische Analyse (Breiman-Benchmarks)

Auf synthetischen Datensätzen mit bekannten Bayes-Fehlern:

Rand: Zeigte selbstkalibrierendes Verhalten auf geometrisch sauberen Daten, kennzeichnete sehr wenige Instanzen als unsicher (U/B-Verhältnisse < 0,5) und verhielt sich effektiv wie CART, wenn die Grenze klar ist.
Knoten-Bootstrap & Qualitäts-Plateau: Zeigten eine proportionale Kalibrierung und kennzeichneten auf schwierigeren Datensätzen (höherer Bayes-Fehler) mehr Instanzen als unsicher, obwohl alle Methoden im Vergleich zum theoretischen Bayes-Fehler zu viele kennzeichneten (U/B > 1).
Kalibrierungslücke: Keine Methode erreichte ein U/B-Verhältnis von 1,0, was darauf hindeutet, dass die lokale Schwellenwertunsicherheit nicht direkt dem globalen Bayes-Fehler entspricht.

Domänenanwendungen

Mammographie: Knoten-Bootstrap kennzeichnete 10,8 % der Fälle als unsicher und verbesserte gleichzeitig die entschiedene Genauigkeit um 0,71 % gegenüber CART. Dies ist wertvoll für die Identifizierung von Fällen, die einer sekundären Überprüfung bedürfen.
Diabetes: Knoten-Bootstrap erzielte einen Genauigkeitsgewinn von +9,8 %, kennzeichnete jedoch 63,4 % der Patienten, was einen Kompromiss zwischen Genauigkeit und Kennzeichnungsrate nahelegt. Die Rand-Methode bot einen konservativeren, praktischen Betriebspunkt (+0,4 % Gewinn, 9,5 % Kennzeichnung).
Einschränkungen: Auf dem kleinen Cleveland-Herzerkrankungsdatensatz ( $N=303$ ) schnitt Knoten-Bootstrap aufgrund unzuverlässiger Varianzschätzungen schlechter ab. Auf dem deutschen Kreditdatensatz schnitt die Rand-Methode schlechter als die Baseline ab, was auf Einschränkungen bei komplexen wirtschaftlichen Merkmalsinteraktionen hindeutet.

Bedeutung und Behauptungen

Die Arbeit behauptet, den ternären Baum als prinzipielles Primitive für unsicherheitsbewusste Klassifizierung zu etablieren. Ihre Bedeutung liegt in:

Praktischer Nützlichkeit: Bereitstellung eines Mechanismus zur Kennzeichnung grenzunsicherer Vorhersagen ohne Enthaltung, was es nachgelagerten Systemen (z. B. medizinisches Screening, Kreditwürdigkeitsprüfung) ermöglicht, unterschiedliche Behandlungsstrategien anzuwenden.
Rechenmäßiger Handhabbarkeit: Ableitung von Unsicherheitszonen aus vorhandenen Aufteilungsstatistiken ohne Notwendigkeit externer Daten oder komplexer Neutrainierung.
Theoretischer Fundierung: Angebot eines Rahmens, in dem das „Undec"-Urteil ein Qualifikator für das Vorhersagevertrauen ist und nicht eine Ablehnung der Vorhersage selbst.

Die Autoren vermerken bescheiden, dass die Methoden, obwohl sie die entschiedene Genauigkeit verbessern, die Kennzeichnungsrate noch nicht perfekt an den theoretischen Bayes-Fehler kalibrieren, und identifizieren diese Kalibrierung als ein konkretes offenes Problem für zukünftige Arbeiten.