| Home > Publications > Reports > Informatics (CW) |
CW 488
Daan Fierens, Jan Ramon, Hendrik Blockeel and Maurice Bruynooghe
A comparison of pruning criteria for probability trees
Abstract
Probability trees (or Probability Estimation Trees, PET's) are decision trees with probability distributions in the leaves. Usually decision trees are learned in a top-down manner with pre- or postpruning. Which pruning criterion is used strongly influences the size of the resulting tree and the quality of the probability estimates. While the effect of pruning criteria on classification accuracy is well-studied, only recently there is more interest in the effect on probability estimates or probability-based rankings. Hence, there is currently no clear view on the relative performance of all different pruning criteria for probability trees and it is unclear which criteria are preferable under which circumstances. In this paper we survey six of the most important pruning criteria for probability trees. We discuss their theoretical advantages and disadvantages and we perform an extensive experimental study of their relative performance. The main conclusion is that a pruning criterion based on randomization tests usually performs best and learns trees that are relatively small. We identify several scenarios in which other pruning criteria achieve results comparable to those of randomization tests.
report.pdf (350K) / mailto: D. Fierens