Entropy evaluation based on confidence intervals of frequency estimates: Application to the learning of decision trees

Entropy gain is widely used for learning decision trees. However, as we go deeper downward the tree, the examples become rarer and the faith-fulness of entropy decreases. Thus, misleading choices and over-fitting may occur and the tree has to be adjusted by using an early-stop crite-rion or post pruning algorithms. However, these methods still depends on the choices previously made, which may be unsatisfactory. We propose a new cumulative entropy function based on con-fidence intervals on frequency estimates that to-gether considers the entropy of the probability distribution and the uncertainty around the es-timation of its parameters. This function takes advantage of the ability of a possibility distri-bution to upper bound a family of probabilities previously estimated from a limited set of exam-ples and of the link between possibilistic speci-ficity order and entropy. The proposed measure has several advantages over the classical one. It performs significant choices of split and provides a statistically relevant stopping criterion that al-lows the learning of trees whose size is well-suited w.r.t. the available data. On the top of that, it also provides a reasonable estimator of the per-formances of a decision tree. Finally, we show that it can be used for designing a simple and ef-ficient online learning algorithm. 1