Ternary Decision Trees with Locally-Adaptive Uncertainty Zones William Smits
arXiv:2605.22740v1 [cs.LG] 21 May 2026
Avathon, Austin, TX, USA [email protected]
Abstract. Decision trees partition the feature space using hard binary thresholds, assigning identical confidence to instances far from a decision boundary and to those directly on it. We introduce ternary decision trees, which augment each split node with an uncertainty zone of half-width δ centered on the optimal threshold. Instances whose feature value falls within this zone receive predictions formed by weighted blending of both child subtrees and are flagged as boundary-uncertain, signaling that downstream applications may wish to treat these predictions differently. Crucially, δ is computed locally at each node from statistics already available during standard CART split finding, requiring no external noise specification and no additional data. We propose and evaluate five δ-estimation methods: quality-plateau (plateau width of the split criterion curve), class-overlap (empirical class-distribution overlap), gain-ratio (split quality relative to split entropy), node-bootstrap (threshold variance under node-level resampling), and margin (SVMinspired distance to the nearest cross-class training example). Evaluated across 72 OpenML-CC18 datasets with 5-fold cross-validation, all five methods with probabilistic routing significantly outperform standard CART on decided accuracy (Wilcoxon signed-rank, p ≤ 0.001). The margin method achieves the best efficiency (0.104 accuracy gain per unit of boundary-uncertain flagging rate), wins on 42 of 72 datasets, and requires zero additional hyperparameters. Analysis on three Breiman synthetic benchmarks with known Bayes errors reveals that the margin method is self-calibrating on geometrically clean data, while nodebootstrap and quality-plateau maintain the best ratio of flagging rate to theoretical irreducible error. Experiments on four medical and financial datasets demonstrate practical value: on mammography, node-bootstrap achieves +0.71% decided accuracy by flagging 10.8% of screening cases as boundary-uncertain.
1
Introduction
Decision trees are among the most widely used classification algorithms due to their interpretability, computational efficiency, and competitive accuracy on tabular data [5,17]. At each internal node, CART selects the feature f and threshold θ that maximize a split criterion (Gini impurity or information gain), routing instances with xf ≤ θ left and xf > θ right. This mechanism is fundamentally
2
William Smits
binary: every instance is routed to exactly one child, and the confidence of that routing is the same regardless of whether the instance sits far from θ or within a single unit of it. This hard commitment creates a known weakness near decision boundaries. An instance with xf = θ + ε is treated identically to one with xf = θ + 10ε, yet the former sits in a region where the optimal threshold may genuinely be uncertain given the training data. Classifying near-boundary instances with the same confidence as clearly-classified instances overstates certainty in precisely the cases where the learned split is least reliable. We address this by introducing a ternary evaluation at each decision node. Around the optimal threshold θ, we define an uncertainty zone of half-width δ: if xf > θ + δ True (1) zone(xf ) = Undec if θ − δ < xf ≤ θ + δ False if xf ≤ θ − δ Instances in the True and False zones are routed deterministically. Instances in the Undec zone receive predictions formed by distance-weighted blending of both child subtrees and are flagged as boundary-uncertain, enabling downstream systems to treat them differently from confident predictions. Figure 1 illustrates the resulting three-region partition on a two-dimensional synthetic dataset. The central technical challenge is computing δ appropriately for each node. Prior work either specifies δ externally from known measurement error [13] or uses global thresholds computed from dataset-level statistics [19,22]. We derive δ locally at each node from quantities already computed during standard CART split finding, requiring no additional data and no external noise model. Contributions. 1. Five methods for computing a node-local uncertainty zone half-width δ from split statistics (Section 3). 2. Two routing architectures for propagating boundary-uncertain instances through the tree (Section 3.4). 3. An extensive empirical evaluation across 72 OpenML-CC18 datasets, three Breiman synthetic benchmarks with known Bayes errors, and four medical/financial datasets (Section 4). 4. A diagnostic framework using the Undecided/Bayes ratio to assess the sensitivity of each δ method relative to the theoretical irreducible error of a dataset (Section 5.2).
2
Related Work
Three-Way Decisions and Rough Sets. Yao’s three-way decisions framework [19,20] partitions instances into positive, boundary, and negative regions corresponding to acceptance, deferral, and rejection. The thresholds defining these regions are derived from global Bayesian risk functions using dataset-level
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
3
Decision Boundaries: Standard CART vs Ternary Decision Tree Background colour = predicted class (every point receives a prediction) (b) Ternary Decision Tree (Quality-Plateau ) Hatching = boundary-uncertain zone (46.4%) | Decided accuracy: 0.948
2
2
1
1
Feature 2
Feature 2
(a) Standard CART Hard binary decision regions
0
0
1
1
2
2
2
1
0
1
Class 0 Class 1
decisive prediction decisive prediction
Feature 1
2
Class 0 Class 1
2
boundary-uncertain (blended prediction) boundary-uncertain (blended prediction)
1
0
Feature 1
1
2
Class 0 training Class 1 training
Fig. 1. Decision boundaries on a two-moons synthetic dataset (quality-plateau δ method, depth 3). Standard CART (left) makes hard binary decisions at every point. The ternary decision tree (right) shows the same two-class color background everywhere — every point receives a class prediction. The hatched overlay marks the boundary-uncertain zone where that prediction is formed by weighted blending of both child subtree outputs rather than deterministic routing. The hatching qualifies the confidence of the prediction, not its presence: the background color reveals what class is predicted even in the uncertain zone. Training instances are shown as scatter points. (Blue + hatch = Class 0 boundary-uncertain; Red + hatch = Class 1 boundaryuncertain.)
loss parameters rather than local node statistics. Pawlak’s rough set theory [15] formalizes a three-region structure identical in form to Equation 1, and the formal connection to three-valued (Kleene) logic has been established by Avron and Konikowska [1]. These frameworks provide the theoretical grounding for our approach; our contribution is a computationally tractable method for deriving the region boundaries locally at each tree node. Indecision Trees. Kent and Ménager [13] modify decision trees to propagate externally specified measurement uncertainty through the tree structure. Their uncertainty zones are derived from known sensor noise rather than from the training data itself. Our work addresses the more common setting where no external uncertainty model is available, deriving δ entirely from the training data at each node. Fuzzy and Soft Decision Trees. Fuzzy decision trees [14] use graded membership functions at each node, providing a continuous analogue of our discrete threezone structure. Zhi et al. [22] combine fuzzy trees with three-way decisions but apply a global post-hoc threshold rather than per-node local adaptation. Soft decision trees [12,10] use learned sigmoid routing functions, optimized by gradient descent, producing probabilistic routing without an explicit uncertainty
4
William Smits
zone. None of these approaches derives a per-node uncertainty zone from the local split quality statistics. Abstaining and Reject-Option Classifiers. A related line of work adds a reject option to binary classifiers [6,2]. The reject option is applied at the classifier output level and does not modify the internal tree structure. Credal classifiers [21] produce set-valued predictions using imprecise probability, providing uncertainty at the output level without structural changes to the model. In our framework, boundary-uncertain instances still receive a class prediction (formed by weighted subtree blending), so the distinction from abstention is fundamental: we never withhold a prediction; we qualify it. Dominance-Based Rough Sets. The Dominance-Based Rough Set Approach (DRSA) [11] uses ordered comparison operators (≥, ≤) to produce certain and possible rules analogous to our True and Undec zones. However, in DRSA the three-zone structure is a property of rule coverage across the training set rather than of individual predicate evaluation. Our framework produces a three-valued evaluation per instance per predicate, which is structurally different.
3
Ternary Decision Trees
3.1
Notation and Preliminaries
d Let D = {(xi , yi )}N i=1 be a training set with xi ∈ R and yi ∈ {0, 1, . . . , K − 1}. ∗ A standard CART node selects f ∈ {1, . . . , d} and θ∗ ∈ R maximizing the split quality criterion Q (Gini gain or information gain) over the n training instances reaching that node. We denote the ternary value set as T = {True, Undec, False} with numeric encoding True = 1, Undec = 0, False = −1. Ternary conjunction follows Kleene’s strong three-valued logic: AND(a, b) = min(a, b), i.e.,
True∧Undec = Undec,
3.2
False∧Undec = False,
True∧True = True. (2)
Uncertainty Zone Semantics
The uncertainty zone of half-width δ around θ∗ represents threshold uncertainty: the observation that the optimal threshold is not perfectly determined by the finite training set, and values close to θ∗ might lie on either side of the true boundary. This interpretation motivates the five estimation methods below. Setting δ = 0 recovers standard binary CART behavior. 3.3
Five Methods for Computing δ
All five methods receive as input the column of feature values c ∈ Rn , the class labels y ∈ {0, . . . , K − 1}n , the sample weights w ∈ Rn , the optimal threshold
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
5
θ∗ , and the quality scores {Q(θj )} evaluated at all candidate thresholds {θj }. These are all quantities already computed during standard CART split finding. Each method returns a non-negative scalar δ, clamped to at most 25% of the feature range to prevent degenerate cases. Quality Plateau (δQP ). The quality curve Q(θ) typically has a plateau of nearoptimal thresholds around θ∗ . The width of this plateau reflects how precisely the data constrains the optimal split location: δQP =
θhi − θlo , 2
where Q(θ) ≥ (1 − ε)Q(θ∗ ) for θ ∈ [θlo , θhi ].
(3)
The tolerance ε ∈ [0, 1] controls the plateau width; we use ε = 0.05. This method adds only O(T ) work per node by scanning the quality curve already evaluated, where T is the number of candidate thresholds. Class Overlap (δCO ). The width of the region where class-conditional feature distributions overlap directly measures where neither class owns the feature space: δCO =
h i+ ′ 1 (c) (c′ ) max′ min P1−q , P1−q − max Pq(c) , Pq(c ) , 2 c̸=c
(4)
(c)
where Pq is the q-th percentile of feature values for class c at this node, and [·]+ = max(0, ·). We use q = 0.10. Gain Ratio (δGR ). The gain ratio GR = IG(θ∗ )/Hsplit (θ∗ ) measures how informative the split is relative to its balance. High gain ratio indicates a clear, confident split; low gain ratio indicates ambiguity: δGR =
α · range(c) , 1 + GR
(5)
where α is a global scale parameter (default α = 0.10) and Hsplit (θ∗ ) is the binary entropy of the split proportions. This method adds zero computation beyond what CART already performs. Node Bootstrap (δNB ). The most statistically principled method directly measures threshold instability by resampling the node’s training examples: ∗ δNB = std(θ1∗ , . . . , θB ),
(6)
where θb∗ is the optimal threshold on the b-th bootstrap resample of the n examples at this node. We scale B with dataset size: B = 20 for n < 2000, B = 15 for n < 10000, and B = 10 otherwise. This method is excluded on datasets with N > 20,000 due to computational cost.
6
William Smits
Margin (δM ). Inspired by support vector machines [7], we define δ as the distance from θ∗ to the nearest cross-class training example (the “support vector” at this node): ∗ ∗ δM = min min (xif − θ ), min (θ − xif ) , (7) ∗ ∗ i:xif >θ ,yi =cL
i:xif ≤θ ,yi =cR
where cL and cR are the dominant classes on the left and right sides of θ∗ respectively. When the split is perfectly clean (no cross-class examples), we fall back to the physical gap between the two adjacent data points straddling θ∗ . This method requires zero hyperparameters and O(n) work per node. 3.4
Routing Architectures
Probabilistic routing (binary tree structure). The tree is trained identically to standard CART, with all examples routed left (≤ θ∗ ) or right (> θ∗ ) during fitting. The value δ is computed and stored at each node for use during prediction only. At prediction time, an instance x arriving at a node with feature f , threshold θ, and uncertainty zone δ is routed as follows: – xf ≤ θ − δ: route left (decisive) – xf > θ + δ: route right (decisive) – otherwise: propagate to both children with weights wL = (θ + δ − xf )/(2δ) and wR = 1 − wL , combining probability outputs as p̂ = wL p̂L + wR p̂R . The instance is flagged as boundary-uncertain if it enters the weighted combination at any node. Hard middle branch (trinary tree structure). A third child is added to each node. During training, examples with θ − δ < xf ≤ θ + δ are routed to this middle child and used to train a separate subtree; left and right subtrees are trained on examples outside the uncertainty zone. During prediction, the instance is routed to whichever of the three branches contains its feature value and is flagged as boundary-uncertain if it enters the middle branch. Equivalence of probabilistic and deferred routing. We also tested deferred routing, in which the weighted combination is resolved using hard binary routing within child subtrees. Across all 72 CC18 datasets and all five δ methods, probabilistic and deferred routing produced numerically identical results (to four decimal places). At depth ≤ 4, the probability of a single instance traversing two or more uncertainty zones on the same path is negligible in practice. We report only probabilistic routing in all experiments. 3.5
Prediction and Boundary-Uncertain Flagging
A standard class prediction is always produced by taking the argmax of the (possibly blended) leaf probability vector. The ternary verdict is not abstention:
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
7
it is a qualifier on the prediction indicating whether the path to the leaf was decisive or passed through a weighted combination. Formally: ( True if no uncertainty zone was traversed (8) verdict(x) = Undec if at least one uncertainty zone was traversed We evaluate performance on decided instances (verdict = True) separately from all instances, using two primary metrics: Decided Accuracy (accuracy restricted to decided instances) and Boundary-Uncertain Rate (fraction of instances receiving verdict Undec).
4
Experiments
4.1
Datasets and Collections
We evaluate across three benchmark collections covering 79 datasets in total. OpenML-CC18. The curated benchmark suite of 72 classification tasks [3] covers diverse dataset sizes (N ∈ [10, 130,000]), dimensionalities (d ∈ [3, 3,072]), and class structures (K ∈ [2, 10]). One dataset (task 167124, raw image pixels, d = 3,072) was excluded as axis-aligned tree splits are not meaningful on flattened pixel arrays, leaving 71 evaluated datasets. Breiman synthetic benchmarks. Three datasets with analytically-known Bayes errors from OpenML: waveform-5000 (N = 5,000, d = 21, K = 3, Bayes error ≈ 14%) [5], twonorm (N = 7,400, d = 20, K = 2, Bayes error ≈ 2.3%) [4], and ringnorm (N = 7,400, d = 20, K = 2, Bayes error ≈ 1.7%) [4]. Medical and financial datasets. Four high-stakes binary classification tasks from OpenML: Pima diabetes (N = 768, d = 8), German credit (N = 1,000, d = 20), Cleveland heart disease (N = 303, d = 13), and Mammography (N = 11,183, d = 6, severely imbalanced at 2.3% positive). 4.2
Experimental Protocol
All experiments use 5-fold stratified cross-validation. Features are standardized within each fold (StandardScaler fitted on training data only). All ternary trees use max_depth = 4. Node-bootstrap is excluded on datasets with N > 20,000 due to computational cost; this affects a subset of the CC18 datasets and is noted in Table 1. We compare against sklearn CART (DecisionTreeClassifier, max_depth = 4) as the baseline. We report Decided Accuracy (primary metric), Boundary-Uncertain Rate (%), Overall Accuracy (all instances), and Decided F1 (macroaveraged F1 on decided instances). Statistical significance of decided accuracy improvements over the baseline is assessed using the one-sided Wilcoxon signed-rank test [9] across per-dataset mean decided accuracies. Win/Tie/Loss (W/T/L) counts use a practical significance threshold of 0.5 percentage points.
8
William Smits
Table 1. Decided accuracy across OpenML-CC18 (72 datasets, 5-fold CV). W/T/L = wins/ties/losses vs CART baseline on decided accuracy. Node-bootstrap excluded where N > 20,000 due to computational cost. All probabilistic-routing methods are significant at p ≤ 0.001 (Wilcoxon, one-sided). Method
Routing Dec.Acc ±std Undec% Acc.All W/T/L
Class-Overlap prob. Gain-Ratio prob. Node-Bootstrap h.m. Node-Bootstrap prob. Margin prob. Quality-Plateau prob. CART (baseline) ref. Margin h.m. Quality-Plateau h.m. Gain-Ratio h.m. Class-Overlap h.m.
0.7620 0.207 0.7583 0.209 0.7425 0.193 0.7421 0.193 0.7397 0.193 0.7337 0.189 0.7217 0.194 0.7203 0.202 0.7128 0.224 0.7015 0.238 0.6785 0.280
5
Results
5.1
OpenML-CC18: Broad Validity
71.3 58.2 17.6 31.9 16.7 17.4 0.0 9.7 11.0 27.1 32.9
0.7177 48/7/17 0.7186 45/14/13 0.7280 38/17/7 0.7336 36/11/15 0.7220 42/21/9 0.7234 37/29/6 0.7217 ref. 0.7136 35/23/14 0.7050 35/27/10 0.6838 33/16/23 0.6350 36/9/27
Table 1 presents results across 72 OpenML-CC18 datasets. Significance. All five δ methods with probabilistic routing significantly outperform the CART baseline on decided accuracy (p ≤ 0.001, Wilcoxon signed-rank, one-sided), confirming that ternary decision trees with locally-adaptive uncertainty zones provide a statistically robust improvement across diverse datasets. Class-Overlap and Gain-Ratio. Although class-overlap and gain-ratio achieve nominally higher decided accuracy (0.762 and 0.758 respectively) than margin (0.740), this is attributable to selective routing: by flagging 71% and 58% of instances as boundary-uncertain respectively, these methods classify only the easiest instances decisively. We quantify this with the efficiency metric η = (Dec-Acc − CART-Acc)/Undec%: class-overlap achieves η = 0.068 and gainratio η = 0.072, compared to η = 0.104 for margin. These methods are therefore not recommended for practical use in their current parameterization. Margin is the recommended method. The margin method achieves the highest efficiency (η = 0.104), flags only 16.7% of instances as boundary-uncertain, wins on 42 of 72 datasets (p < 0.001), and requires zero additional hyperparameters. This combination of performance, parsimony, and theoretical grounding from SVM margin theory makes it the recommended δ method. Hard-middle routing. Probabilistic routing outperforms hard-middle routing for 4 of 5 δ methods. In hard-middle routing, boundary-uncertain examples are
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
9
Accuracy-Coverage Tradeoff All Combinations on OpenML-CC18 =0.10
=0.15
0.78
0.76 Node-Bootstrap (prob.)
Mean Decided Accuracy
Node-Bootstrap
(h.m.) Margin (prob.)
0.74
=0.05
Class-Overlap (prob.)
Gain-Ratio (prob.)
Quality-Plateau (prob.)
Improved decided accuracy
CART (baseline) Margin (h.m.)
0.72
Quality-Plateau (h.m.) Gain-Ratio (h.m.)
0.70
0.68
Class-Overlap (h.m.)
Method | Routing prob. = probabilistic, h.m. = hard-middle Margin (prob.) Gain-Ratio (prob.) Margin (h.m.) Gain-Ratio (h.m.) Node-Bootstrap (prob.) Class-Overlap (prob.) Node-Bootstrap (h.m.) Class-Overlap (h.m.) Quality-Plateau (prob.) CART (baseline) Quality-Plateau (h.m.)
0.66 0.0
0.1
0.2
0.3
0.4
0.5
Mean Boundary-Uncertain Rate
0.6
0.7
0.8
Fig. 2. Accuracy-coverage tradeoff across 71 OpenML-CC18 datasets (5-fold CV means). Each point represents one (delta method, routing) combination at its mean boundary-uncertain rate (x-axis) and mean decided accuracy (y-axis). The dashed horizontal line marks the CART baseline decided accuracy. Efficiency isolines (η = decided accuracy gain per unit of boundary-uncertain rate) show that methods above and to the left of the baseline deliver improvement with lower abstention cost. Circles denote probabilistic routing; diamonds denote hard-middle routing. The margin method (red circle) achieves the best efficiency (η = 0.104), combining competitive decided accuracy with a moderate boundary-uncertain rate of 16.7%. Class-overlap and gain-ratio (far right) achieve high decided accuracy by routing the majority of instances through the uncertainty zone, as reflected by their low efficiency scores.
removed from the left and right training sets, reducing the quality of those branches. The resulting negative efficiency (η < 0 for all hard-middle combinations on CC18) confirms that this structural cost exceeds any benefit on diverse datasets. Node-bootstrap is the exception, performing comparably under both routing strategies.
5.2
Breiman Benchmarks: Theoretical Analysis
Table 2 presents results on the three Breiman synthetic datasets. We introduce the Undecided/Bayes (U/B) ratio as a diagnostic: U/B = Undec%/Bayes error. A ratio close to 1.0 indicates the method flags approximately the fraction of instances that are theoretically ambiguous; ratios much greater than 1 indicate over-flagging.
10
William Smits
Table 2. Breiman synthetic benchmarks with analytically-known Bayes errors. U/B = Boundary-Uncertain Rate / Bayes Error. A ratio closer to 1.0 indicates better alignment with the theoretically ambiguous region. No method achieves calibration, motivating future work on δ scaling. waveform (BE=14%) twonorm (BE=2.3%) ringnorm (BE=1.7%) Method
Dec.Acc
U/B
Dec.Acc
U/B
Dec.Acc
U/B
Node-Bootstrap 0.7845 Margin 0.7377 Quality-Plateau 0.7711 CART (baseline) 0.7350
2.57 0.09 2.54 ref.
0.8245 0.7774 0.8079 0.7759
15.64 0.42 13.49 ref.
0.7688 0.7648 0.7879 0.7647
11.77 0.39 10.68 ref.
Margin is self-calibrating on clean data. The margin method produces U/B ratios of 0.09, 0.42, and 0.39 on the three datasets, all well below 1.0. On geometrically structured synthetic data, the SVM-inspired gap between class support vectors at each node tends to be very small because both classes densely populate the feature space near the boundary. Margin correctly identifies almost no instances as threshold-uncertain, producing predictions nearly identical to CART. This is desirable behavior: a method that aggressively flags uncertainty on geometrically clean data would produce false signals. Node-bootstrap and quality-plateau are proportionally better calibrated. Nodebootstrap and quality-plateau achieve U/B values of 2.4 to 2.6 on waveform (the dataset with the largest Bayes error at 14%) compared to values of 10 to 16 on twonorm and ringnorm (Bayes errors of 2.3% and 1.7%). While all ratios exceed 1.0, the relative ordering is correct: these methods flag proportionally more instances on harder datasets. No method achieves calibration. No δ method achieves U/B ≈ 1.0, confirming that local threshold uncertainty as computed from split statistics does not directly correspond to the Bayes-uncertain fraction of the dataset. This is expected: the Bayes error characterizes the joint distribution in the full feature space, while δ characterizes uncertainty about individual univariate split thresholds. We identify calibration of δ to target the Bayes error boundary as a productive direction for future work, for example via the Cover-Hart k-NN Bayes error bound [8]. 5.3
Medical and Financial Datasets: Domain Value
Table 3 presents results on four high-stakes datasets for the three recommended methods and the baseline. Mammography: strongest practical result. On the severely imbalanced mammography dataset (2.3% positive rate), node-bootstrap flags 10.8% of screening cases as boundary-uncertain while achieving +0.71% decided accuracy over CART. In a clinical screening context, these flagged cases correspond to radiological
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
11
Table 3. Medical and financial datasets. Dec.Acc = accuracy on decisively classified instances. Undec% = fraction of instances classified as boundary-uncertain (these instances still receive a prediction, formed by weighted subtree blending). F1-Dec = macro-averaged F1 on decisive instances. Dataset
Method
Dec.Acc Undec% Acc.All F1-Dec
credit-g
Node-Bootstrap 0.7677 Margin 0.6808 Quality-Plateau 0.7126 CART (baseline) 0.7130
71.0 48.1 7.7 0.0
0.7180 0.614 0.7130 0.584 0.7130 0.607 0.7130 0.605
diabetes
Node-Bootstrap 0.8363 Margin 0.7418 Quality-Plateau 0.7772 CART (baseline) 0.7382
63.4 9.5 29.4 0.0
0.7499 0.814 0.7343 0.715 0.7408 0.751 0.7382 0.714
heart-c
Node-Bootstrap 0.7102 Margin 0.7744 Quality-Plateau 0.7296 CART (baseline) 0.7370
60.7 58.9 0.0 0.0
0.7407 0.640 0.7296 0.508 0.7296 0.723 0.7370 0.730
Node-Bootstrap 0.9915 Margin 0.9867 mammography Quality-Plateau 0.9880 CART (baseline) 0.9844
10.8 0.7 5.5 0.0
0.9848 0.764 0.9845 0.769 0.9847 0.789 0.9844 0.775
findings near the classification boundary, precisely where a second review or additional diagnostic testing is most beneficial. Quality-plateau achieves the best F1-Dec (0.789), indicating better handling of the class imbalance on the decisive subset. Diabetes: large gains at the cost of high boundary-uncertain rates. Nodebootstrap achieves +9.8% decided accuracy over the 0.738 baseline but flags 63.4% of patients as boundary-uncertain. Margin achieves a more practical operating point: +0.4% decided accuracy with only 9.5% boundary-uncertain flagging. For clinical screening where the cost of flagging is high, margin’s conservative operating point is preferable. Heart disease: small dataset limitation. On the Cleveland heart disease dataset (N = 303), node-bootstrap falls below the baseline decided accuracy (0.710 vs. 0.737). With only approximately 240 training examples per fold, bootstrapbased threshold variance estimates are unreliable. We recommend a minimum sample threshold of N ≥ 500 for the node-bootstrap method. Quality-plateau’s decided accuracy closely matches the baseline (0.730 vs. 0.737) without requiring a minimum sample size. Margin achieves the highest decided accuracy (0.774) on this dataset, though at a high boundary-uncertain rate (58.9%) that limits practical utility.
12
William Smits
German credit: margin limitation. Margin is the only method and the only dataset in our experiments where decided accuracy falls below the CART baseline (0.681 vs. 0.713). German credit’s 20 economic features and complex feature interactions appear to produce split margins that do not well-characterize threshold uncertainty. This limitation should be considered in applications involving small-to-medium datasets with intricate economic feature structures.
6
Discussion
Practical recommendations. Based on our empirical analysis, we offer the following recommendations. Margin (prob.) is the default choice, offering the best efficiency, zero hyperparameters, theoretical grounding in SVM margin theory, and self-calibrating behavior on clean data; it is suitable for datasets with N ≥ 200. Node-bootstrap (prob.) is recommended when maximum decided accuracy is required and N ≥ 500 per training fold. Node-bootstrap adds O(B · n log n) work per node where B is the number of bootstrap replicates, making it substantially more expensive than the other four delta methods which add at most O(n) overhead to the standard CART split evaluation. All other methods are computationally lightweight: quality-plateau and gain-ratio reuse the split criterion scores already computed by CART; margin requires a single linear scan over the node’s training examples; class-overlap requires percentile computation over class subsets. We exclude node-bootstrap on datasets with N > 20,000 due to this cost; a compiled implementation would reduce this overhead significantly. Quality-plateau (prob.) is the safest choice: the most consistent improvement across all datasets tested, never catastrophically underperforming, and suitable for any dataset size. Probabilistic routing is preferred in all cases, as hard-middle routing is consistently inferior for 4 of 5 methods on the CC18 benchmark. The boundary-uncertain verdict in practice. It is important to distinguish boundary-uncertain verdicts from abstention. Every instance receives a class prediction. The boundary-uncertain flag is a qualifier indicating that the prediction was formed by weighted blending of subtree outputs rather than deterministic routing to a single leaf. Applications that can act on this signal will benefit most from the ternary architecture: scheduling additional review for flagged medical cases, routing flagged credit applications to manual underwriters, or returning a confidence interval rather than a point prediction are natural use cases. Calibration of the boundary-uncertain rate. The Undecided/Bayes ratio analysis reveals that none of the five δ methods produces a boundary-uncertain rate that aligns with the theoretical Bayes error. Methods that produce high decided accuracy on the Breiman benchmarks do so by flagging substantially more instances than are theoretically ambiguous (U/B between 2 and 16 for node-bootstrap and quality-plateau). Deriving a scaling of δ that targets the Bayes error boundary,
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
13
for example via the Cover-Hart k-NN Bayes error estimate, is a natural extension that we leave for future work.
7
Conclusion
We introduced ternary decision trees with locally-adaptive uncertainty zones, providing a principled framework for augmenting CART with per-node threshold uncertainty. Five methods for computing the uncertainty zone half-width δ were derived from split statistics already computed during standard tree fitting, and two routing architectures were proposed and evaluated. Across 72 OpenML-CC18 datasets, all five δ methods with probabilistic routing significantly outperform CART on decided accuracy (p ≤ 0.001, Wilcoxon signed-rank). The margin method, which requires zero additional hyperparameters, achieves the best efficiency and is recommended as the default. Analysis on Breiman synthetic benchmarks with known Bayes errors reveals that no method precisely calibrates its boundary-uncertain flagging rate to the theoretical ambiguity region, establishing δ calibration as a concrete open problem. This work establishes the ternary tree as a principled primitive for uncertaintyaware classification. Natural extensions include ensemble methods for ternary trees (analogous to random forests), δ calibration targeting the Bayes error, and ternary rule extraction for interpretable classification with boundary-uncertain verdicts.
AI Tools Disclosure Large language model tools were used to assist with manuscript preparation, including grammar refinement and proofreading. All scientific content, experimental design, analysis, and conclusions are the sole work of the authors.
References 1. Avron, A., Konikowska, B.: Rough sets and 3-valued logics. Studia Logica 90(1), 69–92 (2008) 2. Bartlett, P.L., Wegkamp, M.H.: Classification with a reject option using a hinge loss. Journal of Machine Learning Research 9, 1823–1840 (2008) 3. Bischl, B., Casalicchio, G., Feurer, M., Hutter, F., Lang, M., Mantovani, R.G., van Rijn, J.N., Vanschoren, J.: OpenML benchmarking suites. arXiv preprint arXiv:1708.03731 (2021) 4. Breiman, L.: Bagging predictors. Machine Learning 24(2), 123–140 (1996) 5. Breiman, L., Friedman, J., Olshen, R., Stone, C.: Classification and Regression Trees. Wadsworth (1984) 6. Chow, C.K.: On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory 16(1), 41–46 (1970). https://doi.org/10.1109/TIT. 1970.1054406 7. Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20(3), 273–297 (1995)
14
William Smits
8. Cover, T.M., Hart, P.: Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13(1), 21–27 (1967). https://doi.org/10.1109/TIT. 1967.1053964 9. Demšar, J.: Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research 7, 1–30 (2006) 10. Frosst, N., Hinton, G.: Distilling a neural network into a soft decision tree. arXiv preprint arXiv:1711.09784 (2017) 11. Greco, S., Matarazzo, B., Słowiński, R.: Rough sets theory for multicriteria decision analysis. European Journal of Operational Research 129(1), 1–47 (2001) 12. Irsoy, O., Yildiz, O.T., Alpaydin, E.: Soft decision trees. In: Proceedings of the 21st International Conference on Pattern Recognition. pp. 1121–1124 (2012) 13. Kent, J.S., Ménager, D.H.: Indecision trees: Learning argument-based reasoning under quantified uncertainty. In: Synthetic Data for Artificial Intelligence and Machine Learning: Tools, Techniques, and Applications. Proceedings of SPIE, vol. 12529, pp. 296–307. SPIE (2023). https://doi.org/10.1117/12.2663380 14. Olaru, C., Wehenkel, L.: A complete fuzzy decision tree technique. Fuzzy Sets and Systems 138(2), 221–254 (2003) 15. Pawlak, Z.: Rough sets. International Journal of Computer & Information Sciences 11(5), 341–356 (1982) 16. Pedregosa, F., et al.: Scikit-learn: Machine learning in Python, vol. 12 (2011) 17. Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann (1993) 18. Vanschoren, J., van Rijn, J.N., Bischl, B., Torgo, L.: OpenML: Networked science in machine learning. ACM SIGKDD Explorations Newsletter 15(2), 49–60 (2014) 19. Yao, Y.: Three-way decisions with probabilistic rough sets. Information Sciences 180(3), 341–353 (2010) 20. Yao, Y.: An outline of a theory of three-way decisions. In: Rough Sets and Current Trends in Computing (RSCTC 2012). Lecture Notes in Computer Science, vol. 7413, pp. 1–17. Springer (2012). https://doi.org/10.1007/ 978-3-642-32115-3_1 21. Zaffalon, M.: The naive credal classifier. Journal of Statistical Planning and Inference 105(1), 5–21 (2002) 22. Zhi, H., Leung, Y., Liu, J.: Three-way classification: Ambiguity and abstention in machine learning. In: Rough Sets – International Joint Conference, IJCRS 2019. Lecture Notes in Computer Science, vol. 11499, pp. 280–294. Springer (2019). https://doi.org/10.1007/978-3-030-22815-6_22
Appendix A
Per-Dataset Results on OpenML-CC18
Table 4 reports decided accuracy and boundary-uncertain rate for each of the 71 evaluated OpenML-CC18 datasets under probabilistic routing, for the three recommended delta methods and the CART baseline. Full results for all 11 combinations are given in Appendix B.
B
Full Combination Results on OpenML-CC18
Table 5 presents decided accuracy for all 11 combinations averaged across the 71 CC18 datasets, supporting the routing comparison in Section 5.1.
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
C
15
Breiman Synthetic Benchmarks: All Delta Methods
Table 6 extends Table 2 in the main paper to include all five delta methods, providing a complete view of the U/B ratio diagnostic.
D
Medical and Financial Datasets: All Combinations
Table 7 extends Table 3 to include all 11 combinations on the four medical and financial datasets, supporting the domain analysis in Section 5.3.
E
Reproducibility
All experiments were implemented in Python 3.12 using scikit-learn 1.3 [16], numpy 1.24, scipy 1.10, and openml 0.14 [18]. Experiments were run on AMD Ryzen 7 9700X 8-Core Processor, 32GB RAM. Total benchmark runtime for the CC18 collection was approximately CC18: 16933s ( 4h 42m) Breiman: 346s ( 0h 5m) Medical: 29s. All random seeds were fixed at 42. Code is available at https://github.com/smitswil/ternary_tree.
F
Ternary Tree Structure Example
Figure 3 shows an annotated ternary decision tree trained on the breast cancer dataset using the margin δ method at depth 2 (TrinaryTree, hard-middle routing). Each split node carries three outgoing branches corresponding to the three zones of Equation 1: a decisive left branch (≤ θ − δ), a decisive right branch (> θ +δ), and a physical middle branch for boundary-uncertain instances (dashed orange edges). The δ value at each node (shown in red) varies with the local data geometry, demonstrating the per-node adaptivity of the method. Nodes and leaves reached via the middle branch are shaded orange to make the boundary-uncertain path traceable from root to leaf.
16
William Smits Ternary Decision Tree Margin Method (TrinaryTree, depth 2, Breast Cancer dataset)
worst radius = 16.795
= 0.1750 n = 569
UNDECIDED to + )
> +
(
worst concave points
mean texture
mean texture
= 0.136
= 17.720
= 14.990
= 0.0021
= 2.8050
= 0.6500
n = 374
n = 10
n = 185
UNDECIDED to + )
(
UNDECIDED to + )
> +
(
UNDECIDED to + )
> +
(
> +
Class: benign
Class: benign
Class: malignant
Class: benign
Class: benign
Class: malignant
Class: malignant
Class: malignant
Class: malignant
conf = 0.98
conf = 0.57
conf = 0.61
conf = 1.00
conf = 0.75
conf = 0.75
conf = 0.50
conf = 0.50
conf = 0.98
n = 326
n=7
n = 41
n=2
n=4
n=4
n=8
n=6
n = 171
Split node ( = threshold, = uncertainty half-width) Node reached via boundary-uncertain branch
Leaf: benign (decided) Leaf: malignant (decided)
Leaf: boundary-uncertain prediction
Fig. 3. Ternary decision tree structure (hard-middle routing, margin δ method, depth 2, Breast Cancer dataset). Each split node routes instances decisively left (≤ θ − δ), decisively right (> θ + δ), or to a dedicated middle subtree for boundary-uncertain instances (dashed orange edges). The uncertainty zone half-width δ (red) is computed locally at each node from the margin to the nearest cross-class training example. In probabilistic routing (Section 3.4), the same three-zone evaluation occurs at prediction time without a physical middle branch, blending child subtree outputs by distance to θ instead.
G
Probabilistic Routing Tree Structure Example
Figure 4 shows a BinaryTernaryTree trained on the same breast cancer dataset as Figure 3, using the same margin δ method and depth, for direct comparison between the two routing architectures. In probabilistic routing the tree structure is identical to standard CART: every split node has exactly two physical children. The uncertainty zone [θ − δ, θ + δ] is not a separate branch but a routing rule applied at prediction time. Instances whose feature value falls within this range receive a prediction formed by distance-weighted blending of both child subtree outputs: θ + δ − xf , w R = 1 − wL . p̂ = wL p̂L + wR p̂R , wL = 2δ Each node box annotates the blend range [θ−δ, θ+δ] (gray italic) and the routing logic is summarized in the annotation box. Comparing this figure to Figure 3 (Appendix F) illustrates the architectural distinction: hard-middle routing
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
17
creates a physical third subtree trained only on uncertain instances, whereas probabilistic routing reuses both existing subtrees and blends their outputs at inference time. Ternary Decision Tree Probabilistic Routing Margin Method | depth 2 | Breast Cancer dataset
worst radius
Probabilistic routing rules:
= 16.795
xf decisive left subtree
= 0.1750 blend: [16.620, 16.970]
< xf + BOTH subtrees (blended) p = wLpL + wRpR
n = 569
xf > + decisive right subtree
xf (decisive)
xf > + (decisive)
worst concave points
mean texture
= 0.136
= 16.110
= 0.0021
= 0.1700
blend: [0.134, 0.138]
blend: [15.940, 16.280]
n = 379
n = 190
xf (decisive)
xf > + (decisive)
xf (decisive)
xf > + (decisive)
Class: benign
Class: malignant
Class: benign
Class: malignant
conf = 0.98
conf = 0.61
conf = 0.53
conf = 0.99
n = 333
n = 46
n = 17
n = 173
Split node ( = threshold, = uncertainty half-width, blend range = [
, + ])
Leaf: benign
Leaf: malignant
Fig. 4. BinaryTernaryTree structure (probabilistic routing, margin δ method, depth 2, Breast Cancer dataset). Each split node has two physical children, identical in structure to standard CART. The uncertainty zone [θ−δ, θ+δ] (blend range, shown in gray italic) is not a physical branch: instances in this zone receive predictions formed by distance-weighted blending of both child subtree outputs simultaneously, with weights proportional to distance from θ. The routing annotation box (upper right) summarizes the three-zone logic. Compare with Figure 3 (hard-middle routing) where the same zone corresponds to a dedicated physical middle subtree.
18
William Smits
Table 4. Per-dataset decided accuracy (Dec.Acc) and boundary-uncertain rate (Undec%) on OpenML-CC18. Results are 5-fold CV means under probabilistic routing. node-bootstrap excluded where N > 20,000 (shown as –). Datasets sorted alphabetically. Margin
Node-Bootstrap Quality-Plateau
CART
Dataset
Dec.Acc Undec% Dec.Acc Undec% Dec.Acc Undec%
Acc
Bioresponse,OpenML-CC18 Devnagari-Script,OpenML-CC18 Fashion-MNIST,OpenML-CC18 GesturePhaseSegmentationProcessed,OpenML-CC18 Internet-Advertisements,OpenML-CC18 MiceProtein,OpenML-CC18 PhishingWebsites,OpenML-CC18 adult,OpenML-CC18 analcatdata_authorship,OpenML-CC18 analcatdata_dmft,OpenML-CC18 balance-scale bank-marketing,OpenML-CC18 banknote-authentication,OpenML-CC18 blood-transfusion-service-center,OpenML-CC18 breast-w car,OpenML-CC18 churn,OpenML-CC18 climate-model-simulation-crashes,OpenML-CC18 cmc,OpenML-CC18 cnae-9,OpenML-CC18 connect-4,OpenML-CC18 credit-approval,OpenML-CC18 credit-g,OpenML-CC18 cylinder-bands,OpenML-CC18 diabetes,OpenML-CC18 dna,OpenML-CC18 dresses-sales,OpenML-CC18 electricity,OpenML-CC18 eucalyptus,OpenML-CC18 first-order-theorem-proving,OpenML-CC18 har,OpenML-CC18 ilpd,OpenML-CC18 isolet,OpenML-CC18 jm1,OpenML-CC18 jungle_chess_2pcs_raw_endgame_complete,OpenML-CC18 kc1,OpenML-CC18 kc2,OpenML-CC18 kr-vs-kp letter madelon,OpenML-CC18 mfeat-factors mfeat-fourier mfeat-karhunen mfeat-morphological mfeat-pixel,OpenML-CC18 mfeat-zernike mfeat-zernike,OpenML-CC18 mnist_784,OpenML-CC18 nomao,OpenML-CC18 numerai28.6,OpenML-CC18 optdigits,OpenML-CC18 ozone-level-8hr,OpenML-CC18 pc1,OpenML-CC18 pc3,OpenML-CC18 pc4,OpenML-CC18 pendigits,OpenML-CC18 phoneme,OpenML-CC18 qsar-biodeg,OpenML-CC18 satimage,OpenML-CC18 segment,OpenML-CC18 semeion,OpenML-CC18 sick,OpenML-CC18 spambase,OpenML-CC18 splice,OpenML-CC18 steel-plates-fault,OpenML-CC18 texture,OpenML-CC18 tic-tac-toe,OpenML-CC18 vehicle,OpenML-CC18 vowel,OpenML-CC18 wall-robot-navigation,OpenML-CC18 wdbc,OpenML-CC18 wilt,OpenML-CC18
0.7767 0.1462 0.6522 0.4747 0.9643 0.7469 0.9280 0.8624 0.9346 0.2152 0.8273 0.9063 0.9656 0.7788 0.9592 0.9322 0.9284 0.9350 0.6152 0.7093 0.7565 0.8572 0.6808 0.6887 0.7418 0.8945 0.5689 0.7621 0.5539 0.4485 0.8764 0.7015 0.4049 0.8050 0.7125 0.8588 0.8179 0.9409 0.2895 0.7371 0.5111 0.5534 0.6151 0.7805 0.8160 0.5047 0.5503 0.5728 0.9423 0.5167 0.5343 0.9376 0.9407 0.9032 0.9064 0.7059 0.7942 0.8317 0.8044 0.7710 0.5775 0.9908 0.8962 0.9000 0.5910 0.5381 0.9080 0.6838 0.4883 0.9094 0.9452 0.9818
0.7614 0.000 0.1491 0.000 0.6511 0.000 0.4747 0.000 0.9622 0.000 0.7157 0.000 0.9203 0.000 0.8440 0.000 0.9191 0.000 0.2082 0.000 0.7632 0.000 0.8944 0.000 0.9548 0.000 0.7754 0.000 0.9313 0.000 0.8507 0.000 0.9204 0.000 0.9241 0.000 0.5533 0.000 0.4315 0.000 0.6761 0.000 0.8551 0.000 0.7130 0.000 0.6778 0.000 0.7382 0.000 0.8945 0.000 0.5520 0.000 0.7621 0.000 0.5925 0.000 0.4580 0.000 0.8749 0.000 0.6964 0.000 0.3991 0.000 0.8075 0.000 0.7182 0.000 0.8497 0.000 0.8238 0.000 0.9409 0.000 0.2546 0.000 0.7292 0.000 0.5175 0.000 0.5400 0.000 0.5955 0.000 0.6540 0.000 0.7700 0.000 0.4975 0.000 0.5150 0.000 0.5721 0.000 0.9291 0.000 0.5166 0.000 0.5190 0.000 0.9313 0.000 0.9287 0.000 0.8899 0.000 0.8896 0.000 0.7256 0.000 0.7929 0.000 0.8038 0.000 0.7883 0.000 0.7563 0.000 0.5769 0.000 0.9846 0.000 0.8937 0.000 0.9122 0.000 0.5940 0.000 0.5362 0.000 0.7474 0.000 0.6821 0.000 0.4687 0.000 0.9146 0.000 0.9227 0.000 0.9775 0.000
0.076 0.036 0.005 0.006 0.018 0.155 0.586 0.174 0.145 0.657 0.445 0.050 0.047 0.221 0.144 0.275 0.067 0.096 0.546 0.606 0.604 0.046 0.481 0.304 0.095 0.000 0.156 0.005 0.224 0.075 0.006 0.088 0.062 0.165 0.526 0.097 0.211 0.000 0.302 0.026 0.070 0.075 0.105 0.478 0.332 0.052 0.134 0.003 0.076 0.003 0.071 0.076 0.105 0.088 0.125 0.140 0.014 0.218 0.078 0.087 0.000 0.084 0.020 0.253 0.071 0.017 0.777 0.209 0.169 0.089 0.134 0.014
0.7521 – – 0.4575 0.9654 0.7998 0.9203 – 0.9359 0.1807 0.8471 – 0.9834 0.7545 0.9776 0.8507 0.9358 0.9658 0.5737 0.4315 – 0.9185 0.7677 0.6645 0.8363 0.8945 0.4855 – 0.6044 0.4505 0.8885 0.7635 0.3862 0.8123 – 0.8710 0.8181 0.9409 0.2497 0.7643 0.5290 0.5625 0.6721 0.6709 0.8132 0.5172 0.5449 – – – 0.5370 0.9652 0.7163 0.9309 0.7792 0.7175 0.8108 0.8532 0.8247 0.7700 0.5775 0.9887 0.8880 0.9040 0.6054 0.5412 0.7474 0.7332 0.5164 0.9061 0.9517 0.9885
0.474 – – 0.587 0.047 0.344 0.000 – 0.157 0.677 0.485 – 0.324 0.872 0.227 0.000 0.144 0.441 0.442 0.000 – 0.696 0.710 0.467 0.634 0.000 0.810 – 0.353 0.219 0.050 0.844 0.088 0.720 – 0.589 0.724 0.000 0.042 0.427 0.099 0.102 0.243 0.100 0.339 0.087 0.124 – – – 0.088 0.514 0.639 0.519 0.907 0.141 0.246 0.366 0.233 0.038 0.000 0.365 0.399 0.087 0.111 0.057 0.000 0.273 0.478 0.146 0.195 0.299
0.7696 0.3655 0.4100 0.5136 0.9653 0.7837 0.9203 0.8729 0.9242 0.2058 0.7650 0.8099 0.9789 0.7557 0.9514 0.8534 0.9279 0.9315 0.5582 0.4315 0.6761 0.8577 0.7126 0.6764 0.7772 0.8945 0.5524 0.7574 0.5912 0.4379 0.9100 0.6703 0.4147 0.8245 0.7226 0.8531 0.8204 0.9409 0.2522 0.7459 0.5287 0.5666 0.6513 0.7538 0.8258 0.5488 0.5629 0.5132 0.9435 0.5173 0.5426 0.9341 0.9319 0.8964 0.8882 0.7312 0.8047 0.8425 0.8739 0.7892 0.5775 0.9848 0.8899 0.9122 0.6101 0.5734 0.7474 0.6954 0.5572 0.9245 0.9411 0.9831
0.055 0.990 0.696 0.403 0.023 0.218 0.000 0.159 0.118 0.071 0.013 0.715 0.199 0.187 0.051 0.014 0.070 0.122 0.071 0.000 0.000 0.023 0.077 0.065 0.294 0.000 0.012 0.273 0.481 0.168 0.213 0.134 0.215 0.326 0.091 0.158 0.038 0.000 0.012 0.144 0.138 0.160 0.208 0.488 0.405 0.149 0.165 0.907 0.138 0.162 0.168 0.054 0.006 0.025 0.006 0.342 0.188 0.167 0.256 0.103 0.000 0.003 0.407 0.000 0.144 0.166 0.000 0.103 0.327 0.081 0.100 0.083
Ternary Decision Trees with Locally-Adaptive Uncertainty Zones
19
Table 5. All 11 combinations on OpenML-CC18. Mean decided accuracy and boundary-uncertain rate across 71 datasets (5-fold CV). prob. = probabilistic routing, h.m. = hard-middle routing. Method
Routing Dec.Acc Undec%
Class-Overlap prob. Gain-Ratio prob. Node-Bootstrap h.m. Node-Bootstrap prob. Margin prob. Quality-Plateau prob. Baseline ref. Margin h.m. Quality-Plateau h.m. Gain-Ratio h.m. Class-Overlap h.m.
0.7624 0.7562 0.7458 0.7455 0.7426 0.7361 0.7247 0.7229 0.7148 0.7032 0.6788
0.712 0.584 0.177 0.323 0.168 0.174 0.000 0.097 0.109 0.269 0.323
Table 6. All delta methods on Breiman synthetic benchmarks under probabilistic routing. U/B = boundary-uncertain rate divided by known Bayes error. waveform (BE=14%) twonorm (BE=2.3%) ringnorm (BE=1.7%) Method
Dec.Acc
U/B
Dec.Acc
U/B
Dec.Acc
U/B
Baseline Class-Overlap Gain-Ratio Margin Node-Bootstrap Quality-Plateau
0.7350 0.8578 0.8492 0.7377 0.7845 0.7711
0.00 6.87 5.95 0.09 2.57 2.54
0.7759 0.9483 0.9233 0.7774 0.8245 0.8079
0.00 39.05 37.46 0.42 15.64 13.49
0.7647 0.8431 0.8261 0.7648 0.7688 0.7879
0.00 42.71 46.22 0.39 11.76 10.68
20
William Smits
Table 7. All combinations on medical and financial datasets (5-fold CV means). Dec.Acc = decided accuracy. Undec% = boundary-uncertain rate. Dataset credit-g
Method
Node-Bootstrap Margin Gain-Ratio Node-Bootstrap Baseline Quality-Plateau Quality-Plateau Gain-Ratio Class-Overlap Class-Overlap Margin diabetes Gain-Ratio Node-Bootstrap Class-Overlap Class-Overlap Gain-Ratio Node-Bootstrap Quality-Plateau Quality-Plateau Margin Margin Baseline heart-c Class-Overlap Margin Gain-Ratio Baseline Gain-Ratio Quality-Plateau Quality-Plateau Node-Bootstrap Node-Bootstrap Class-Overlap Margin mammography Gain-Ratio Class-Overlap Gain-Ratio Node-Bootstrap Node-Bootstrap Class-Overlap Quality-Plateau Quality-Plateau Margin Margin Baseline
Routing Dec.Acc Undec% Acc.All prob. h.m. prob. h.m. ref. prob. h.m. h.m. prob. h.m. prob. prob. prob. h.m. prob. h.m. h.m. prob. h.m. prob. h.m. ref. prob. prob. prob. ref. h.m. prob. h.m. prob. h.m. h.m. h.m. prob. prob. h.m. prob. h.m. h.m. prob. h.m. h.m. prob. ref.
0.7677 0.7631 0.7287 0.7161 0.7130 0.7126 0.7089 0.7035 0.6993 0.6983 0.6808 0.8909 0.8363 0.8356 0.8200 0.8170 0.8059 0.7772 0.7766 0.7418 0.7410 0.7382 0.7963 0.7744 0.7408 0.7370 0.7341 0.7296 0.7222 0.7102 0.6471 0.5886 0.5869 0.9950 0.9948 0.9944 0.9915 0.9911 0.9881 0.9880 0.9879 0.9867 0.9867 0.9844
0.710 0.271 0.271 0.323 0.000 0.077 0.049 0.162 0.901 0.481 0.481 0.797 0.634 0.542 0.948 0.617 0.491 0.294 0.285 0.095 0.083 0.000 0.744 0.589 0.311 0.000 0.211 0.000 0.000 0.607 0.093 0.104 0.004 0.196 0.359 0.226 0.108 0.091 0.033 0.055 0.025 0.005 0.007 0.000
0.7180 0.7150 0.7190 0.6940 0.7130 0.7130 0.7080 0.7030 0.7210 0.6960 0.7130 0.7473 0.7499 0.7239 0.7500 0.7513 0.7369 0.7408 0.7291 0.7343 0.7317 0.7382 0.7407 0.7296 0.7407 0.7370 0.7370 0.7296 0.7222 0.7407 0.6556 0.6037 0.5889 0.9838 0.9846 0.9835 0.9848 0.9847 0.9838 0.9847 0.9854 0.9852 0.9845 0.9844