6.4 Decision Trees

Information

Consider an event that has a certain probability $p$. The higher $p$ is, the more likely the event is, and hence there is not much information (or uncertainty) contained in the occurrence of the event. For example, the event that my car starts when I get into it in the morning has a fairly low amount of information because my car is reliable, and I expect it to start. If, on the other hand, it does not start one morning, then that low-probability event would be surprising and would contain much more information.

Information is typically measured in bits, where one bit represents the amount of information needed to distinguish between two equally likely events or messages. For example, when you flip a fair coin, you gain one bit of information because you go from being uncertain about the outcome (heads or tails) to knowing the outcome (heads, for instance). To measure the number of bits of a whole number, you would use the base-2 logarithm (${\text{log}}_{2}x$), so it may not come as a surprise to learn that the base-2 logarithm plays a huge role in measuring information.

The information of an event with probability $p$ is $-{\text{log}}_{2}p$. Recall that probabilities $p$ are always between 0 and 1, and if $0<p<1$, then by properties of logarithms, we would have ${\text{log}}_{2}p<0$. This explains the negative sign that appears in the formula, as it makes sense to measure information with a positive number.

Note that the information contained in an event that is certain to occur $(p=1)$ is $-{\text{log}}_{2}1=0$, while the information contained in knowing that a coin was flipped and heads came up $(p=1/2)$, would be $-{\text{log}}_2\left(\frac{1}{2}\right)=-(-1)=1$, or one bit of information.

Let’s say the probability that my car will start on any given day is $p=255/256$, and so the probability that it will not start is $1-p=1/256$. The information of the event that it starts is $-{\text{log}}_2\left(\frac{255}{256}\right)=0.0056$, whereas the information of the event that it does not start is $-{\text{log}}_2\left(\frac{1}{256}\right)=8$. Essentially, there are 8 bits of information contained in the knowledge that my car does not start because this would only have happened about once in every $2^8=256$ days.

Entropy

Entropy is a measure that quantifies the average amount of information, or uncertainty, in a random variable or a probability distribution. It is closely related to information. Think of entropy as a measure of the disorder, randomness, or unpredictability in a system.

For a discrete random variable $X$, with $n$ values $x_i$ and associated probabilities $p_i$ the entropy of $X$ is:

The idea of entropy is crucial in creating decision trees, as we shall see in the next section.

Training and Testing

The decision tree model M we constructed in the previous section classifies the original dataset S with 100% accuracy. The reason is quite simple; we forced it to! Starting from the root node containing all the points, the data was split into subsets and smaller subsets until every leaf node contained a pure subset (all one label). However, there is no guarantee that M accurately represents the underlying structure of the data. Think of our dataset S as a random sample of points taken from a larger population of points. There could have been noise, outliers, and other factors present in our sample that cause M to give spurious predictions. In order to evaluate the predictive power of a decision tree, we should try it out on a testing set of additional labeled data. We measure the accuracy of the model using:

Pruning, Depth-Limiting, and Other Methods for Reducing Variance

Decision trees often suffer from overfitting (high variance), which adversely affects their accuracy. Fortunately, there are a number of methods that can be used to reduce overfitting.

A decision tree that has a lot of internal nodes is prone to overfitting because it may be making decisions based on only a very small amount of data or very small difference in the data’s features. “Splitting hairs” is a common term for emphasizing small differences that may not actually matter much. We generally do not want our models to split hairs. Pruning is the process of reducing the size of a decision tree by removing branches that split the data too finely.

For example, in creating the model M, the subset of S defined by the sequence, left, left, right—that is: $Y\le 13.75$, $X\le 14.55$, and $Y>8.45$—consists of the points (7.6, 10.2, Red), (7.9, 10.6, Red), (3.2, 11, Blue), (5.2, 12.2, Red), (9.4, 12.8, Blue), and (1.9, 13, Red). As you can see in Figure 6.20, it takes three additional inequalities to separate the four red and two blue points into regions of the same color. At the end of the process, each of the two blue points and one of the red points became the sole members of their subsets.

Splitting a set into singletons (one-element subsets) is generally not a great idea in machine learning, as this puts too much predictive weight on a single observation. One method of pruning is to remove branches that split the data into sets L and R in which one of L or R is a singleton (or below a predefined proportion of the original set). Then the node becomes a leaf consisting of data having multiple labels. The label of this new leaf is determined by majority vote. That is, the label that occurs most often becomes the predicted label of any data that finds itself to this node. This method is commonly called error-based (reduced-error) pruning, as it seeks to remove branches that do not significantly increase the classification error rate.

Example 6.10

Problem

Use pruning to reduce the complexity of the decision tree model M described in this section. Then reclassify the data points given in Example 6.8.

Solution

From the node whose pathway is $Y\le 13.75$, $X\le 14.55$, $Y>8.45$, the model M branched on the inequality $X\le 8.65$. This splits the set into $L$ = {(7.6, 10.2, Red), (7.9, 10.6, Red), (3.2, 11, Blue), (5.2, 12.2, Red), (1.9, 13, Red)} and $R$ = {(9.4, 12.8, Blue)}. Because the split would produce a singleton, we simply make this node a leaf and prune away all branches and nodes underneath it. Now the node is a leaf with four red and two blue data points, and so this leaf is labeled Red. The flowchart and corresponding regions of the plane are shown in Figure 6.22 and Figure 6.23. Note that the pruned tree has a depth of 4, which is quite a bit smaller than the original tree’s depth of 7.

Figure 6.22 Flowchart for Pruned Decision Tree from Example 6.10

Figure 6.23 Regions of the Plane Corresponding to Pure Nodes for the Pruned Tree. The pruned model divides the plane into fewer regions than the original model did, which likely captures the true underlying pattern better without overfitting.

Now let’s reclassify the points (9.9, 2.5), (15.1, 12.6), and (3.5, 10.2) as in Table 6.9.

$(X,Y)=(9.9,2.5)$. Starting at the root node, branch left $(Y=2.5\le 13.75)$. Branch left again $(X=9.9\le 14.55)$. Branch left once again $(Y=2.5\le 8.45)$, which is a blue leaf.

$(X,Y)=(15.1,12.6)$. Starting at the root node, branch left $(Y=12.6\le 13.75)$. Then branch right $(X=15.1>14.55)$, which is a red leaf.

$(X,Y)=(3.5,10.2)$. Starting at the root node, branch left $(Y=10.2\le 13.75)$. Branch left again $(X=3.5\le 14.55)$. Then branch right $(Y=10.2>8.45)$, which is now a red leaf.

X	Y	Label	Predicted Label
9.9	2.5	Blue	Blue
15.1	12.6	Red	Red
3.5	10.2	Red	Red

Table 6.9 Reclassified Test Points

Now we find the model to be 100% accurate on the testing data. (Of course, a model trained on real-world data with many more data points cannot possibly attain 100% accuracy, but this is possible on very small datasets.) Note that the model’s accuracy on the original training set S is no longer 100%. On S, the pruned tree misclassifies two points, (3.2, 11), and (9.4, 12.8) as red when they are in fact blue, and so the accuracy on the training set is now $17/19=89.5\%$. That’s still pretty good!

Other methods exist for pruning a decision tree. There are two main types: pre-pruning and post-pruning. Pre-pruning refers to setting parameters or criteria for the complexity of the decision tree at the outset. New branches would be added only if the criteria are met. Post-pruning happens after the entire tree is created without restriction. In post-pruning, branches and nodes are removed according to user-defined rules, turning the previously internal nodes into leaf nodes. Error-based pruning may be implemented as either a pre- or post-pruning algorithm.

• Depth-limiting pruning, as the name suggests, means that a decision tree cannot grow beyond a predefined depth (or number of levels). This pre-pruning technique helps to reduce the number of small splits, but care must be taken so as not to set the depth so low that the model fails to distinguish important details.
• Leaf-limiting pruning puts a maximum cap on the total number of leaves. Like depth-limiting, leaf-limiting is used to restrict the overall complexity of the decision tree model but could lead to underfitting and reduce the predictive power of the model when the data itself possesses a great deal of complexity that needs to be captured.
• Minimum description length (MDL) pruning is a post-pruning method that seeks to find the least complex form of a decision tree that meets an acceptable measure of accuracy. In general, there is always a trade-off between simplicity and accuracy in any machine learning algorithm. What MDL does is to err on the side of simplicity. A full description of the MDL algorithm falls outside the scope of this text.

Decision Trees in Python

The Python package sklearn includes powerful algorithms for creating and working with decision trees. Note that the decision tree classifier is limited to a maximum depth of 3 and the Gini index is used rather than information gain. The data is contained in the dataset RedBlue.csv.

Python Code

      # Import libraries
      import pandas as pd  ## for dataset management
      from sklearn.tree import DecisionTreeClassifier 
      from sklearn import tree
      import matplotlib.pyplot as plt
      
      # Read data file
      data = pd.read_csv('RedBlue.csv')
      
      inputs = data[['X', 'Y']]
      output = data['Label']
      
      # Train Decision Tree Classifier
      clf = DecisionTreeClassifier(max_depth=3)
      clf = clf.fit(inputs,output)
      
      # Plot tree with customization
      plt.figure(figsize=(12, 8))  # Set the size of the plot
      tree.plot_tree(clf,
                     rounded=True,       # Round the edges of the box
                     fontsize=10)        # Adjust font size for clarity
      plt.show()  # Display the plot
    

The resulting output will look like this: