Efficient Algorithms for Finding Multi-way Splits for Decision Trees

A number of recent papers have pointed out that binary decision trees are not always the best model for some domains. In particular, for some distributions the best way to partition a set of examples might be to find a set of intervals for a given feature, and split the examples up into several groups based on those intervals. Binary decision tree induction methods pick a single split point, i.e., they consider only bi-partitions at a node in the tree. We have developed an efficient new algorithm that computes an optimal multi-split of an interval into k sub-intervals, for any fixed k less than the number of examples. The algorithm employs a penalty function for increasing values of k to prevent it from splitting the examples into trivial partitions. Our implementation demonstrates both the efficiency of this method and the kinds of distributions for which it can produce better decision trees.