Decision Tree Learning for Uncertain Clinical Measurements

Cecília Nunes, Hélène Langet, Mathieu De Craene, Oscar Camara, Bart H. Bijnens, Anders JonssonIEEE TKDE 2021 · DOI · OpenReview

Abstract

Clinical decision-making requires reasoning in the presence of imperfect data. Decision Trees (DTs) are a well-known decision support tool, owing to their interpretability, which is fundamental in safety-critical contexts such as medical diagnosis. However, learning DTs from uncertain data often leads to poor generalization, and generating predictions for uncertain data can hinder accuracy. Several methods have suggested the potential of probabilistic decisions at internal nodes to make DTs robust to uncertainty. Some approaches only employ probabilistic thresholds during evaluation, while others consider uncertainty during the learning phase at the expense of increased computational complexity or reduced interpretability. This paper presents a probabilistic DT approach that models measurement uncertainty as a noise distribution, independently realized during three phases: (1) searching for split thresholds, (2) splitting training instances, and (3) generating predictions for unseen data. Our findings indicate that soft training approaches (1, 2) achieve a regularizing effect, leading to significant reductions in DT size while maintaining accuracy. Conversely, soft evaluation (3) showed no significant benefit in handling noise.

Introduction

In clinical practice, measurements such as Ejection Fraction (EF) are rarely absolute; they are estimates subject to inter-observer variability, equipment discrepancies, and patient-specific factors. Traditional Decision Trees (DTs), despite being the "gold standard" for interpretable clinical support, treat these values as absolute. This reliance on "hard" thresholds creates a brittle model: a guideline-based split at an EF of $35\%$ will treat a $34.9\%$ measurement and a $35.1\%$ measurement as fundamentally different, despite the difference likely being within the margin of error.

This brittleness manifests in two primary ways. First, during training, the algorithm may overfit by creating complex branches to account for noisy outliers. Second, at prediction time, minor measurement errors can misdirect a patient's classification path. While fuzzy or soft decision trees have been proposed, they often introduce high computational overhead or fail to distinguish between noise encountered during training versus testing.

Methodology: A Probabilistic Framework

We propose a framework that models measurement noise as a Gaussian distribution $\mathcal{N}(0, \sigma^2)$. The approach decouples "softness" into three independent components to isolate their respective benefits:

Soft Search (SS)

During the training phase, instead of evaluating discrete split points, the algorithm employs a Gaussian kernel to smooth the information gain calculation. This acts as a "Gaussian filter," allowing the algorithm to identify thresholds robust to local data fluctuations rather than being misled by noisy clusters.

Comparison of Information Gain $I(X;Y)$ between standard C4.5 search (discrete points) and Soft Search (SS) (smooth curves) for different data distributions.

Soft Training Propagation (STP)

In standard DTs, an instance belongs entirely to one branch. In STP, instances are fractionally divided between child nodes based on their distance from the threshold, calculated using a Cumulative Distribution Function (CDF). This ensures that instances near the threshold contribute to both potential outcomes during the learning process.

Soft Evaluation (SE)

This component applies probabilistic logic at prediction time. By weighting the outputs of multiple branches, the model produces a final class probability rather than a hard classification, theoretically accounting for uncertainty in the test data.

Experimental Setup and Datasets

The methodology was validated using a diverse set of data sources:

  • 15 Real-World Clinical Datasets: Sourced from UCI and KEEL repositories, including Pima Indians Diabetes, Heart Disease, and Hepatitis datasets.
  • 5 Synthetic Datasets: Generated to test specific properties like varying feature importance and class separation.
  • Cardiology Case Study: A focused analysis of Ejection Fraction data from the Data Science Bowl Cardiac Challenge to demonstrate real-world clinical impact.

Key Insights and Results

Uncertainty as a Regularizer

The most significant finding is that incorporating uncertainty during the training phase (SS and STP) acts as a natural pruning mechanism. Because the model is "less confident" in splits derived from noisy data, it naturally favors simpler, smaller trees. On average, STP produced trees with 5 to 9 fewer leaves than standard C4.5 models. This reduction in complexity significantly enhances interpretability for clinicians without sacrificing predictive power.

Training vs. Test Noise

Our experiments revealed that "softening" the evaluation phase (SE) provided negligible benefits for handling noise present in the training data. Robustness must be integrated during the learning phase to be effective. As shown in the figure below, the probability of a correct classification changes significantly depending on whether the noise is accounted for in the underlying model logic.

Prediction probabilities $P(\hat{y}=0)$ under certain vs. noisy data assumptions as a function of noise level $\sigma$.

Efficiency and Interpretability

Unlike previous Uncertain Decision Tree (UDT) methods that rely on computationally expensive oversampling, our Soft Search (SS) limits the number of necessary computations. This makes it faster and more scalable. Furthermore, by maintaining univariate splits, the resulting models remain "white boxes" that align with clinical guidelines and satisfy regulatory requirements for algorithmic transparency, such as those mandated by the GDPR.

Conclusion and Future Work

Soft training approaches provide a powerful regularizing effect for clinical decision trees, producing models that are both robust to noise and highly interpretable. While this study utilized Gaussian assumptions for noise, future work should explore skewed or non-parametric distributions that may better reflect specific medical device errors. Additionally, automating the estimation of uncertainty factors ($u_s, u_t$) from manufacturer specifications or data-driven heuristics remains a promising avenue for further research.

Summary updated

Abstract

Clinical decision requires reasoning in the presence of imperfect data. DTs are a well-known decision support tool, owing to their interpretability, fundamental in safety-critical contexts such as medical diagnosis. However, learning DTs from uncertain data leads to poor generalization, and generating predictions for uncertain data hinders prediction accuracy. Several methods have suggested the potential of probabilistic decisions at the internal nodes in making DTs robust to uncertainty. Some approaches only employ probabilistic thresholds during evaluation. Others also consider the uncertainty in the learning phase, at the expense of increased computational complexity or reduced interpretability. The existing methods have not clarified the merit of a probabilistic approach in the distinct phases of DT learning, nor when the uncertainty is present in the training or the test data. We present a probabilistic DT approach that models measurement uncertainty as a noise distribution, independently realized: (1) when searching for the split thresholds, (2) when splitting the training instances, and (3) when generating predictions for unseen data. The soft training approaches (1, 2) achieved a regularizing effect, leading to significant reductions in DT size, while maintaining accuracy, for increased noise. Soft evaluation (3) showed no benefit in handling noise.
BibTeX
@article{nunes2021decision,
  author = {Cecília Nunes and Hélène Langet and Mathieu De Craene and Oscar Camara and Bart H. Bijnens and Anders Jonsson},
  title = {{Decision Tree Learning for Uncertain Clinical Measurements}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2021},
  doi = {10.1109/tkde.2020.2967378},
}
Figure