The TREESPLIT Procedure

Algorithms for building a decision tree use the training data to split the predictor space (the set of all possible combinations of values of the predictor variables) into nonoverlapping regions. These regions correspond to the terminal nodes of the tree, which are also known as leaves.

The splitting is done by recursive partitioning, starting with all the observations, which are represented by the node at the top of the tree. The algorithm splits this parent node into two or more child nodes in such a way that the values (or levels) of the response variable within each child region are as similar as possible. The splitting process is then repeated for each of the child nodes, and the recursion continues until a stopping criterion is satisfied. At that point, the tree is considered to be fully built (grown).

At each step, the split is determined by finding the best predictor variable and the best split value (or possibly a set of split values when the value of the MAXBRANCH= option is greater than 2) that optimize a specified criterion in the response variable across the child nodes to which the parent node is split. For more information about the splitting methods available in the TREESPLIT procedure, see the section Splitting Criteria.

The best predictor variable and split value (or set of split values) is called the primary splitting rule. You can also request one or more surrogate splitting rules, which are determined in a fashion similar to the primary splitting rule and are applied when the primary splitting rule’s variable is missing. Each nonterminal node has a primary splitting rule and zero or more surrogate splitting rules. For more information about surrogate splitting rules, see the section Primary and Surrogate Splitting Rules.

Each region, which corresponds to a terminal node, is described by a set of primary and surrogate splitting rules that determine the observations that are assigned to the region. During scoring these rules are applied to determine the predicted values for new observations. For classification trees, the predicted value for a scored observation is the level of the response variable that is most common in the region in which the scored observation exists. For regression trees, the predicted value for a scored observation is the mean of the response variable across training observations values in the region in which the scored observation exists.

Figure 21.8, Figure 21.9, and Figure 21.10 illustrate this process. Figure 21.8 shows a classification tree of depth 2.

Figure 21.8: First Two Splits for the mycas.hmeq Data Table

All 4,172 observations in the data are initially assigned to node 0 at the top of the tree, which represents the entire predictor space. PROC TREESPLIT splits this space into two nonoverlapping regions, represented by node 1 and node 2. PROC TREESPLIT determines that the predictor variable and its split value that optimize the growing criterion across the child nodes are Debtinc and 43.77156, respectively. This split variable and split value constitute the primary splitting rule for node 0. Observations in which Debtinc < 43.77156 are assigned to node 2, and observations in which Debtinc 43.77156 are assigned to node 1.

Figure 21.9 presents a scatter plot of the predictor space for the primary splitting rule for node 0. The split of the variable Debtinc divides the predictor space into node 1 and node 2; these nodes are represented by the two rectangular regions, which have different ratios of events to nonevents for the response variable.

Figure 21.9: Scatter Plot of the Predictor Space for the First Split

Next, the algorithm determines the primary splitting rule for node 2 and splits the region that is represented by node 2 into two nonoverlapping regions, represented by node 3 and node 4. PROC TREESPLIT chooses the variable Delinq and its values to optimize the growing criterion. Observations in which values of the categorical predictor variable Delinq are equal to 0, 1, 2, 3, or 4 are assigned to node 3, and observations in which the values of Delinq are equal to 5, 6, 7, 8, or 10 are assigned to node 4.

Figure 21.10 presents a scatter plot of the predictor space for the primary splitting rule of node 2. The split of the variable Delinq further divides the predictor space of node 2 into two regions: node 3 and node 4, which have different ratios of events to nonevents for the response variable.

Node 3 has a very high proportion of observations for which Bad is equal to 0. In contrast, Bad is equal to 1 for almost all the observations in node 4.

Note that several observations have the same values for Debtinc or Delinq, so the scatter plot gives the perception of fewer observations than there actually are.

Figure 21.10: Scatter Plot of the Predictor Space for the Second Split

This example illustrates recursive binary splitting, in which each parent node is split into two child nodes. By default, the TREESPLIT procedure creates at most two child nodes per split. You can use the MAXBRANCH= option to specify the maximum possible number of child nodes you want per split of a parent node. Based on the splitting criterion you specify, PROC TREESPLIT determines the best number of child nodes up to the value of the MAXBRANCH= option.