Scalable classification and regression tree construction
Johannes E. Gehrke, Alin Dobra · 2003
Automating the learning process is one of the long standing goals of Artificial Intelligence and its more recent specialization, Machine Learning. Supervised learning is a particular learning task in which the goal is to establish the connection between some of the attributes of the data made available for learning, called attribute variables, and the remaining attributes called predicted attributes. This thesis is concerned exclusively with supervised learning using tree structured models: classification trees for predicting discrete outputs and regression trees for predicting continuous outputs. In the case of classification and regression trees most methods for selecting the split variable have a strong preference for variables with large domains. Our first contribution is a theoretical characterization of this preference and a general corrective method that can be applied to any split selection method. We further show how the general corrective method can be applied to the Gini gain for discrete variables when building k-ary splits. In the presence of large amounts of data, efficiency of the learning algorithms with respect to the computational effort and memory requirements becomes very important. Our second contribution is a scalable construction algorithm for regression trees with linear models in the leaves. The key to scalability is to use the EM Algorithm for Gaussian Mixtures to locally reduce the regression problem to a much easier, classification problem. The use of strict split predicates in classification and regression trees has undesirable properties like data fragmentation and sharp decision boundaries, properties that result in decreased accuracy. Our third contribution is the generalization of the classic classification and regression trees by allowing probabilistic splits in a manner that significantly improves the accuracy but, at the same time, does not increase significantly the computational effort to build this types of models.