Finding Multivariate Splits in Decision Trees Using Function Optimization

Abstract

We present a new method for top-down induction of decision trees (TDIDT) with multivariate binary splits at the nodes. The primary contribution of this work is a new splitting criterion called soft entropy, which is continuous and differentiable with respect to the parameters of the splitting function. Using simple gradient descent to find multivariate splits and a novel pruning technique, our TDIDT-SEH (Soft Entropy Hyperplanes) algorithm is able to learn very small trees with better accuracy than competing learning algorithms on most datasets examined. The process of finding a splitting function at a node of a decision tree is a search problem, and we choose to view it as unconstrained parametric function optimization over the space of hyperplane weight vectors w E Rn. Our objective function is soft entropy, a new continuous approximation to the entropy measure (Quinlan 1986). Soft entropy was chosen for two reasons. First, it is well-established that entropy is a good splitting criterion (Buntine & Niblett 1992). Second, softness is important to get good generalization in continuous spaces, as shown in Figure 1. Related work is similar overall, but the OCl algorithm of Murthy et al. (1993) uses entropy as a criterion, and Brodley and Utgoff (1992) d escribe algorithms using error, also a hard splitting criterion.