A comparison of pruning criteria for probability trees

Daan Fierens, Jan Ramon, Hendrik Blockeel, Maurice Bruynooghe

Abstract

Probability Estimation Trees (PETs) are a variant of decision trees designed to predict class probabilities rather than discrete labels. A critical challenge in PET construction is pruning, which must balance the refinement of probability estimates with their statistical calibration. This paper presents the first comprehensive evaluation of six major pruning criteria—Chi-square (CHI), Randomization tests (RAND), Minimum Description Length (MDL), Bayesian Information Criterion (BIC), Error-Based Pruning (EBP), and No Pruning (NOPRUNING)—across 26 diverse datasets. The results demonstrate that the randomization-based approach (RAND) is the most robust and high-performing criterion, effectively navigating the trade-off between model complexity and predictive accuracy.

Introduction

While standard decision trees are optimized for classification accuracy, Probability Estimation Trees (PETs) aim to provide accurate class probability estimates. This shift in objective complicates the pruning phase. Pruning involves a fundamental trade-off between two factors:

  1. Refinement: Excessive pruning results in small trees that group distinct instances into the same leaf, leading to coarse, unrefined probability estimates.
  2. Calibration: Insufficient pruning results in large trees with very few training examples per leaf, leading to "noisy" estimates that do not reflect true population frequencies.

While pruning for classification is well-documented, the optimal criteria for generating accurate probability estimates—especially in the presence of skewed classes or high-cardinality categories—has remained unclear.

Pruning Criteria and Methodology

The study evaluates six distinct pruning strategies:

  • Chi-square test (CHI): A statistical test for correlation utilizing Bonferroni correction.
  • Randomization tests (RAND): An empirical approach that permutes class labels to determine if a split is significantly better than random chance.
  • Minimum Description Length (MDL): An information-theoretic approach that penalizes model complexity based on encoding length.
  • Bayesian Information Criterion (BIC): A criterion similar to MDL but with a lighter penalty for complexity.
  • Error-Based Pruning (EBP): The standard approach used in C4.5, which seeks to minimize predicted classification error.
  • No Pruning (NOPRUNING): Often referred to as the C4.4 approach, which maintains the largest possible tree.

All models utilized Laplace smoothing at the leaves to prevent the prediction of 0% or 100% probabilities, which is essential for maintaining valid probability estimates in small samples.

Experimental Design

The criteria were tested against 26 datasets, including 20 standard attribute-value benchmarks from the UCI repository and 6 complex relational datasets from domains such as bioinformatics and citation analysis. These datasets were selected to provide a rigorous test environment with varying class counts (ranging from 2 to 23) and significant class skews.

Key Insights

The Failure of Information-Theoretic Penalties

A significant finding was the poor performance of MDL and BIC in scenarios with many classes. Because their complexity penalties scale linearly with the number of classes, the penalty becomes disproportionately large as categories increase. This causes the algorithms to over-prune, often reducing the tree to a single node and destroying its predictive utility.

The Calibration Crisis

While some researchers advocate for NOPRUNING to maximize refinement, this study shows that unpruned trees suffer from poor calibration. The lack of sufficient data in the leaves of large trees leads to probability estimates that are statistically unreliable.

Skew Sensitivity in EBP

Error-Based Pruning (EBP), while effective for classification, proved suboptimal for PETs. In highly skewed datasets, EBP often prunes branches that provide nuanced probability information simply because those branches do not alter the majority class label at the node.

The Robustness of Randomization

Randomization tests (RAND) emerged as the superior choice. Unlike CHI, which relies on fixed parametric assumptions, or MDL/BIC, which use rigid penalties, RAND empirically adapts to the specific characteristics of the dataset. By testing splits against randomized data, it identifies truly informative structures without the biases of traditional heuristics.

Results and Performance

RAND significantly outperformed the other criteria in 88 separate test cases across two primary metrics: Root Mean Squared Error (RMSE), which measures the quality of the probabilities, and Area Under the ROC Curve (AUC), which measures the quality of the instance ranking. RAND was so consistently effective that it served as the baseline for the study, being significantly outperformed in only 6 out of 260 total test cases.

From a computational standpoint, while randomization is often perceived as intensive, the authors demonstrated that by randomizing only labels rather than attributes, the overhead is minimal. RAND was found to be only 3.6x slower than not pruning at all—a negligible cost given the substantial gains in model performance.

Conclusion

For the development of Probability Estimation Trees, the choice of pruning criterion is paramount. This research establishes randomization tests (RAND) as the most robust and reliable method for balancing refinement and calibration. While future work may explore the interaction of these criteria with post-hoc recalibration techniques or n-ary tree structures, RAND currently represents the state-of-the-art for generating high-quality probability estimates in decision tree models.

Summary updated

Abstract

Probability trees are decision trees that predict class probabilities rather than the most likely class. The pruning criterion used to learn a probability tree strongly influences the size of the tree and thereby also the quality of its probability estimates. While the effect of pruning criteria on classification accuracy is well-studied, only recently has there been more interest in the effect on probability estimates. Hence, it is currently unclear which pruning criteria for probability trees are preferable under which circumstances.In this paper we survey six of the most important pruning criteria for probability trees, and discuss their theoretical advantages and disadvantages. We also perform an extensive experimental study of the relative performance of these pruning criteria. The main conclusion is that overall a pruning criterion based on randomization tests performs best because it is most robust to extreme data characteristics (such as class skew or a high number of classes). We also identify and explain several shortcomings of the other pruning criteria.
BibTeX
@article{fierens2010comparison,
  author = {Daan Fierens and Jan Ramon and Hendrik Blockeel and Maurice Bruynooghe},
  title = {{A comparison of pruning criteria for probability trees}},
  journal = {Machine Learning},
  year = {2010},
  doi = {10.1007/s10994-009-5147-1},
}
Figure