What Should Be Minimized in a Decision Tree?

Abstract

In this paper, we address the issue of evaluating decision trees generated from training examples by a learning algorithm. We give a set of performance measures and show how some of them relate to oth-ers. We derive results suggesting that the number of leaves in a decision tree is the important mea-sure to minimize. Minimizing this measure will, in a probabilistic sense, improve performance along the other measures. Notably it is expected to produce trees whose error rates are less likely to exceed some acceptable limit. The motivation for deriving such results is two-fold: 1. To better understand what constitutes a good mea-sure of performance, and 2. To provide guidance when deciding which aspects of a decision tree generation algorithm should be changed in order to improve the quality of the decision trees it generates. The results presented in this paper can be used as a basis for a methodology for formally proving that one decision tree generation algorithm is better than another. This would provide a more satisfactory al-ternative to the current empirical evaluation method for comparing algorithms. I.