Global Induction of Classification and Regression Trees

Introduction

Decision trees are one of the most widely used prediction techniques in data mining (Fayyad, Piatetsky-Shapiro, Smyth, & Uthurusamy, 1996). Their similarity to a human reasoning process makes them popular not only among data analysts but also business users. Tree-based approaches are easy to understand, visualize, interpret and their output model can be explained in typical business terms. The ease of application, fast operation and what may be the most important, i.e. the effectiveness of the decision trees, makes them powerful and popular tool (Kotsiantis, 2013).

Two main types of decision trees’ approaches can be distinguished by the type of the problem they are applied to. Tree predictors can be used to classify existing data (classification trees) or to approximate real-valued functions (regression trees) (see Figure 1). In each leaf, classification tree assigns a class label (usually the majority class of all instances that reach that particular leaf), while the regression tree holds a constant value (usually an average value for the target attribute). In addition, model tree is an extension of regression tree (see Figure 1). Main difference between regression tree and model tree is that, for the latter, constant value in the terminal node is replaced by the regression function. Each leaf of the model tree holds a linear (or nonlinear) model whose output is the final prediction value.

Figure 1.

An example of univariate decision tree with tests on nominal and continuous-valued features. Depending on the tree type, leaves could contain class (classification tree), constant value (regression tree) or some kind of model (model tree).

Most typical tree-based system applies greedy search in decision tree induction. One major drawback of greedy algorithms is that, they search only for locally best splits at each node which does not guarantee the globally best solution. Hence, applications of Evolutionary Algorithms (EAs) to the problem of decision tree induction become increasingly popular alternative. Instead of local search, EAs perform a global search in the space of candidate solutions.

The purpose of this chapter is to illustrate the application of EAs to the problem of decision tree induction. The objectives are to show that evolutionary optimization, compared to the greedy search, may result in finding globally optimal solutions, whose complexity is significantly smaller and the prediction is highly competitive. We will cover the global induction of classification, regression, and model trees.

Background

Inducing optimal decision tree is known to be NP-complete (Naumov, 1991). Consequently, practical decision-tree learning algorithms are based on heuristics such as greedy algorithms where locally optimal splits are made in each node. The most popular tree-induction is based on the top-down approach (Rokach & Maimon, 2005). Top-down induction starts from the root node, where locally best split (test) is searched, according to the given optimality measure (e.g. Gini, towing or entropy rule for classification tree and least squared or least absolute deviation error criterion for regression tree). Next, the training instances are redirected to the newly created nodes and this process is repeated for each node until some stopping-rule is satisfied. The recursive partitioning of the dataset may lead to the data over-fitting, therefore, the decision tree pruning (Esposito, Malerba, & Semeraro, 1997) is applied to improve the generalization power of the predictor.

Most of tree inducing algorithms partition the feature space with axis-parallel hyper-planes. These types of trees are called univariate decision trees. Split at each non-terminal node usually involves single feature. For a continuous-valued feature usually an inequality test with binary outcomes is applied and for a nominal attribute mutually exclusive groups of attribute values are associated with outcomes. One of the first and most well-known solution that can be applied to classification and regression problem is CART (Breiman, Friedman, Olshen, & Stone, 1984) system. Good representatives of univariate inducers are also systems developed by Quinlan: C4.5 (1993) for classification and M5 (1992) for regression.