Components of a Decision Tree

All the components of a decision tree are shown in Figure 4-2.

Classification Decision Tree When There Are Multiple Discrete Independent Variables

The criterion for splitting at a root node varies by the type of variable we are predicting, depending on whether the dependent variable is continuous or categorical. In this section, we’ll look at how splitting happens from the root node to decision nodes by way of an example. In the example, we are trying to predict employee salary (emp_sal) based on a few independent variables (education, marital status, race, and sex).

Here is the dataset (available as “categorical dependent and independent variables.xlsx” in github):

Here, Emp_sal is the dependent variable, and the rest of the variables are independent variables.

When splitting the root node (the original dataset), you first need to determine the variable based on which the first split has to be made—for example, whether you will split based on education, marital status, race, or sex. To come up with a way of shortlisting one independent variable over the rest, we use the information gain criterion.

Calculating Uncertainty: Entropy

Uncertainty, also called entropy , is measured by the formula

where p is the probability of event 1 happening, and q is the probability of event 2 happening.

Let’s consider the win scenarios for the two parties:

Scenario	Party A uncertainty	Party B uncertainty	Overall uncertainty
Equal chances of win	−0.5log2(0.5) = 0.5	−0.5log2(0.5) = 0.5	0.5 + 0.5 =1
90% chances of win for party A	−0.9log2(0.9) = 0.1368	−0.1log2(0.1) = 0.3321	0.1368 + 0.3321 = 0.47

We see that based on the previous equation, the second scenario has less overall uncertainty than the first, because the second scenario has a 90% chance of party A’s win.

Uncertainty in the Original Dataset

In the original dataset, nine observations have a salary <= 50K, while five have a salary > 50K:

Let’s calculate the values of p and q so that we calculate the overall uncertainty:

The formulas for p and q are as follows:

Thus, the overall uncertainty in the root node is as follows:

Uncertainty in <=50K	Uncertainty in >50K	Overall uncertainty
–0.64 × log2(0.64) = 0.41	−0.36 × log2(0.36) = 0.53	0.41 + 0.53 = 0.94

The overall uncertainty in the root node is 0.94.

To see the process of shortlisting variables in order to complete the first step, we’ll figure out the amount by which overall uncertainty decreases if we consider all four independent variables for the first split. We’ll consider education for the first split (we’ll figure out the improvement in uncertainty), next we’ll consider marital status the same way, then race, and finally the sex of the employee. The variable that reduces uncertainty the most will be the variable we should use for the first split.

Measuring the Improvement in Uncertainty

To see how the improvement in uncertainty is calculated, consider the following example. Let’s consider whether we want to split our variable by sex of employee:

We calculate the uncertainty –(plog₂p+qlog₂q) of each distinct value of each variable. The table for the uncertainty calculation for one of the variables (Sex) is as follows:

Sex	P	Q	–(plog2p)	–(qlog2q)	–(plog2p+qlog2q)	Weighted uncertainty
Female	4/5	1/5	0.257	0.46	0.72	0.72 × 5/14 = 0.257
Male	5/9	4/9	0.471	0.52	0.99	0.99 × 9/14 = 0.637
Overall						0.894

A similar calculation to measure the overall uncertainty of all the variables would be done. The information gain if we split the root node by the variable Sex is as follows:

(Original entropy – Entropy if we split by the variable Sex) = 0.94 – 0.894 = 0.046

Based on the overall uncertainty, the variable that maximizes the information gain (the reduction in uncertainty) would be chosen for splitting the tree.

In our example, variable-wise, overall uncertainty is as follows:

Variable	Overall uncertainty	Reduction in uncertainty from root node
Education	0.679	0.94 – 0.679 = 0.261
Marital status	0.803	0.94 – 0.803 = 0.137
Race	0.803	0.94 – 0.803 = 0.137
Sex	0.894	0.94 – 0.894 = 0.046

From that we can observe that the splitting decision should be based on Education and not any other variable, because it is the variable that reduces the overall uncertainty by the most (from 0.94 to 0.679).

Once a decision about the split has been made, the next step (in the case of variables that have more than two distinct values—education in our example) would be to determine which unique value should go to the right decision node and which unique value should go to the left decision node after the root node.

Let’s look at all the distinct values of education, because it’s the variable that reduces uncertainty the most:

Distinct value	% of obs. <=50K
11th	100%
9th	100%
Assoc-acdm	100%
Bachelors	67%
HS-grad	50%
Masters	50%
Some-college	0%
Overall	64%

Which Distinct Values Go to the Left and Right Nodes

In the preceding section, we concluded that education is the variable on which the first split in the tree would be made. The next decision to be made is which distinct values of education go to the left node and which distinct values go to the right node.

The Gini impurity metric comes in handy in such scenario.

Gini Impurity

Gini impurity refers to the extent of inequality within a node. If a node has all values that belong to one class over the other, it is the purest possible node. If a node has 50% observations of one class and the rest of another class, it is the most impure form of a node.

Gini impurity is defined as where p and q are the probabilities associated with each class.

Consider the following scenario:

P	Q	Gini index value
0	1	1 – 02 – 12 = 0
1	0	1 – 12 – 02 =0
0.5	0.5	1 – 0.52 – 0.52 = 0.5

Let’s use Gini impurity for the employee salary prediction problem: From the information gain calculation in the previous section, we observed that Education is the variable used as the first split.

To figure out which distinct values go to the left node and which go to the right node, let’s go through the following calculation:

	# of observations			Left node		Right node		Impurity		# of obs
	<=50K	>50K	Grand Total	p	q	p	q	Left node	Right node	Left node	Right node	Weighted impurity
11th	1		1	100%	0%	62%	38%	-	0.47	1	13	0.44
9th	1		1	100%	0%	58%	42%	-	0.49	2	12	0.42
Assoc-acdm	1		1	100%	0%	55%	45%	-	0.50	3	11	0.39
Bachelors	4	2	6	78%	22%	40%	60%	0.35	0.48	9	5	0.39
HS-grad	1	1	2	73%	27%	33%	67%	0.40	0.44	11	3	0.41
Masters	1	1	2	69%	31%	0%	100%	0.43	-	13	1	0.40
Some-college		1	1

We can understand the preceding table through the following steps:

1. 1.

   Rank order the distinct values by the percentage of observations that belong to a certain class.

   This would result in the distinct values being reordered as follows:

   Distinct value	% of obs <= 50K
   11th	100%
   9th	100%
   Assoc-acdm	100%
   Bachelors	67%
   HS-grad	50%
   Masters	50%
   Some-college	0%

    
2. 2.

   In the first step, let’s assume that only the distinct values that correspond to 11th go to the left node, and the rest of the distinct observations correspond to the right node.

   Impurity in the left node is 0 because it has only one observation, and there will be some impurity in the right node because eight observations belong to one class and five belong to another class.

    
3. 3.

   Overall impurity is calculated as follows:

   ((Impurity in left node × # of obs. in left node) + (Impurity in right node × # of obs. in right node)) / (total no. of obs.)

    
4. 4.

   We repeat steps 2 and 3 but this time we include both 11th and 9th in the left node and the rest of the distinct values in the right node.

    
5. 5.

   The process is repeated until all the distinct values are considered in the left node.

    
6. 6.

   The combination that has the least overall weighted impurity is the combination that will be chosen in the left node and right node.

    

In our example, the combination of {11th,9th,Assoc-acdm} goes to the left node and the rest go to the right node as this combination has the least weighted impurity.

Splitting Sub-nodes Further

From the analysis so far, we have split our original data into the following:

Now there is an opportunity to split the right node further. Let us look into how the next split decision is. The data that is left to split is all the data points that belong to the right node, which are as follows:

From the preceding data, we’ll perform the following steps:

1. 1.

   Use the information gain metric to identify the variable that should be used to split the data.

    
2. 2.

   Use the Gini index to figure out the distinct values within that variable that should belong to the left node and the ones that should belong to the right node.

   The overall impurity in the parent node for the preceding dataset is as follows:

   

   

    

Now that the overall impurity is ~0.99, let’s look at the variable that reduces the overall impurity by the most. The steps we would go through would be the same as in the previous iteration on the overall dataset. Note that the only difference between the current version and the previous one is that in the root node the total dataset is considered, whereas in the sub-node only a subset of the data is considered.

Let’s calculate the information gain obtained by each variable separately (similar to the way we calculated in the previous section). The overall impurity calculation with marital status as the variable would be as follows:

In a similar manner, impurity with respect to employee race would be as follows:

Impurity with respect to sex would be calculated as follows:

Impurity with respect to employee education would be calculated as follows:

From the above, we notice that employee education as a variable is the one that reduces impurity the most from the parent node—that is, the highest information gain is obtained from the employee education variable.

Notice that, coincidentally, the same variable happened to split the dataset twice, both in the parent node and in the sub-node. This pattern might not be repeated on a different dataset.

Classification Decision Tree for Continuous Independent Variables

So far, we have considered that both the independent and dependent variables are categorical. But in practice we might be working on continuous variables too, as independent variables. This section talks about how to build a decision tree for a continuous variable.

We will look at the ways in which we can build a decision tree for a categorical dependent variable and continuous independent variables in the next sections using the following dataset (“categorical dependent continuous independent variable.xlsx” in github):

In this dataset, we’ll try to predict whether someone would survive or not based on the Age variable.

Classification Decision Tree When There Are Multiple Independent Variables

In this case, we’ll reverse the scenario—that is, we’ll first find out the rule of splitting to the left node and right node, if we were to split on any of the variables. Once the left and right nodes are figured, we’ll calculate the information gain obtained by the split and thus shortlist the variable that should be slitting the overall dataset.

From the data, we can see that the rule derived should be Age <= 20 or Age >= 26. So again, we’ll go with the middle value: Age <= 23.

Now that we’ve derived the rule, let’s calculate the information gain corresponding to the split. Before calculating the information gain, we’ll calculate the entropy in the original dataset:

Given that both 0 and 1 are 6 in number (50% probability for each), the overall entropy comes out to be 1.

Thus, all values less than or equal to 22 belong to one group (left node), and the rest belong to another group (right node). Note that, practically we would go with a mid value between 22 and 32.

From the data, we see that information gain, due to splitting by the Unknown variable, is only 0.09. Hence, the split would be based on Age, not Unknown.

Classification Decision Tree When There Are Continuous and Discrete Independent Variables

We’ve seen ways of building classification decision tree when all independent variables are continuous and when all independent variables are discrete.

What If the Response Variable Is Continuous?

If the response variable is continuous , the steps we went through in building a decision tree in the previous section remain the same, except that instead of calculating Gini impurity or information gain, we calculate the squared error (similar to the way we minimized sum of squared error in regression techniques). The variable that reduces the overall mean squared error of the dataset will be the variable that splits the dataset.

Here, the independent variable is named variable, and the dependent variable is named response. The first step would be to sort the dataset by the independent variable, as we did in the classification decision tree example.

Once the dataset is sorted by the independent variable of interest, our next step is to identify the rule that splits the dataset into left and right node. We might come up with multiple possible rules. The exercise we’ll perform would be useful in shortlisting the one rule that splits the dataset most optimally.

From the preceding, we see that the minimal overall error occurs when variable < -0.37249. So, the points that belong to the left node will have an average response of 1,556, and the points that belong to the right node will have an average response of 2,146. Note that 1,556 is the average response of all the variable values that are less than the threshold that we derived earlier. Similarly, 2,146 is the average response of all the variable values that are greater than or equal to the threshold that we derived (0.37249).

Continuous Dependent Variable and Multiple Continuous Independent Variables

In classification, we considered information gain as a metric to decide the variable that should first split the original dataset. Similarly, in the case of multiple competing independent variables for a continuous variable prediction, we’ll shortlist the variable that results in least overall error.

We’ll add one additional variable to the dataset we previously considered:

We already calculated the overall error for various possible rules of variable in the previous section. Let’s calculate the overall error for the various possible rules of var2.

The first step is to sort the dataset by increasing value of var2. So, the dataset we will work on now transforms to the following:

var2	response
0.1	1996
0.3	839
0.44	2229
0.51	2309
0.75	815
0.78	2295
0.84	1590

The overall error calculations for various possible rules that can be developed using var2 are as follows:

Note that overall error is the least when var2 < 0.44. However, when we compare the least overall error produced by variable and the least overall error produced by var2, variable produces the least overall error and so should be the variable that splits the dataset.

Continuous Dependent Variable and Discrete Independent Variable

To find out how it works to predict a continuous dependent variable using a discrete independent variable, we’ll use the following dataset as an example, where “var” is the independent variable and “response” is the dependent variable:

var	response
a	1590
b	2309
c	815
a	2229
b	839
c	2295
a	1996

Let’s pivot the dataset as follows:

We’ll order the dataset by increasing average response value:

Now we’ll calculate the optimal left node and right node combination. In the first scenario, only c would be in the left node and a,b will be in the right node. The average response in left node will be 1555, and the average response in right node will be the average of {1574,1938} = {1756}.

Overall error calculation in this scenario will look as follows:

In the second scenario, we’ll consider both {c,b} to belong to the left node and {a} to belong to the right node. In this case, the average response in left node will be the average of {1555,1574} = {1564.5}

The overall error in such case will be calculated as follows:

We can see that the latter combination of left and right nodes yields the lesser overall error when compared to the previous combination. So, the ideal split in this case would be {b,c} belonging to one node and {a} belonging to another node.

Implementing a Decision Tree in R

The implementation of classification is different from the implementation of regression (continuous variable prediction). Thus, a specification of the type of model is required as an input.

The decision tree is implemented using the functions available in a package named rpart. The function that helps in building a decision tree is also named rpart. Note that in rpart we specify the method parameter.

A method anova is used when the dependent variable is continuous, and a method class is used when the dependent variable is discrete.

You can also specify the additional parameters: minsplit, minbucket, and maxdepth (more on these in the next section).

Implementing a Decision Tree in Python

The Python implementation of a classification problem would make use of the DecisionTreeClassifier function in the sklearn package (The code is available as “Decision tree.ipynb” in github):

For a regression problem, the Python implementation would make use of the DecisionTreeRegressor function in the sklearn package:

Common Techniques in Tree Building

Visualizing a Tree Build

In R, one can plot the tree structure using the plot function available in the rpart package. The plot function plots the skeleton of the tree, and the text function writes the rules that are derived at various parts of the tree. Here’s a sample implementation of visualizing a decision tree:

The output of the preceding code looks like this:

From this plot, we can deduce that when var is either of b or c, then the output is 1564. If not, the output is 1938.

In Python, one way to visualize a decision tree is by using a set of packages that have functions that help in display: Ipython.display, sklearn.externals.six, sklearn.tree, pydot, os.

In the preceding code, you would have to change the data frame name in place of (data.columns[1:]) that we used in the first code snippet. Essentially, we are providing the independent variable names as features.

In the second code snippet, you would have to specify the folder location at which graphviz was installed and change the decision tree name to the name that the user has given in the fourth line (replace dtree with the variable name that you have created for DecisionTreeRegressor or DecisionTreeClassifier).

The output of the preceding code snippet looks like Figure 4-3.

Impact of Outliers on Decision Trees

In previous chapters, we’ve seen that outliers have a big impact in the case of linear regression. However, in a decision tree outliers have little impact for classification, because we look at the multiple possible rules and shortlist the one that maximizes the information gain after sorting the variable of interest. Given that we are sorting the dataset by independent variable, there is no impact of outliers in the independent variable.

However, an outlier in the dependent variable in the case of a continuous variable prediction would be challenging if there is an outlier in the dataset. That’s because we are using overall squared error as a metric to minimize. If the dependent variable contains an outlier, it causes similar issues like what we saw in linear regression.

Summary

Decision trees are simple to build and intuitive to understand. The prominent approaches used to build a decision tree are the combination of information gain and Gini impurity when the dependent variable is categorical and overall squared error when the dependent variable is continuous.