Magic Behind Constructing a Decision Tree

Before we get started I need to clarify something. Theoretical decision trees can have two or more branches protruding from a single node.
dt1

However, this can be computationally expensive so most implementations of decision trees only allow binary splits.

dt2

Recall our example problem – Bill is a user on our online dating site and we want to build a decision tree that predicts whether he would message a certain girl. (If so, we say that she’s “date-worthy”). Suppose we have the following ten samples of girls who Bill has viewed and messaged.

ID Distance Hair Income Height BillMessagedHer?
1 5 Blonde 100 5’6 TRUE
2 20 Blonde 50 5’11 FALSE
3 100 Red 20 5’2 FALSE
4 40 Brown 45 6’0 FALSE
5 250 Brown 200 5’5 TRUE
6 5 Blonde 20 6’1 FALSE
7 15 Brown 0 4’11 FALSE
8 20 Black 80 5’3 TRUE
9 70 Brown 15 5’3 FALSE
10 30 Brown 85 5’8 FALSE

Given these 10 training samples, what’s the best split point we can choose to separate our data? Let’s analyze a couple of arbitrary splits.

dt3

Here, green Xs signify women who Bill messaged and red Xs signify women who Bill didn’t message. Out of 3 women with blonde hair, Bill messaged 1 of them and out of 7 women without blonde hair, Bill messaged 2 of them.

dt4

Out of 6 girls 5’6 and shorter Bill messaged 3 of them, and out of 4 girls taller than 5’6 Bill messaged 0 of them.

It appears Bill cares about girls’ height more than their hair color. Maybe Bill is 5’7 and only dates girls shorter than him. Whatever the case, we think that split #2 is a better predictor of women who Bill would message.

The above comparison was pretty intuitive but that isn’t always the case. Suppose we compare these two splits:

dt5

dt6

Which is the better split? This is a subjective question. In practice, people use different metrics for evaluating splits. The most commonly used metric is Information Gain. Another commonly used metric is Gini Impurity, and since it’s easier to explain, let’s use it.

Gini Impurity measures the disorder of a set of elements. It is calculated as the probability of mislabeling an element assuming that the element is randomly labeled according the the distribution of all the classes in the set.

Example: Suppose we have a set with 6 elements: {red, red, blue, blue, blue, blue}. (The classes of this set are red and blue). We select an element at random. Then we randomly label it according to the distribution of classes in the set. This would be equivalent to labeling the selected element by rolling a 6 sided die with 4 blue sides and 2 red sides. The probability that we misclassify the element is equal to the probability that we select a red element times the probability that we label it blue plus the probability that we select a blue element times the probability that we label it red. This is

2/6 * 4/6 + 4/6 * 2/6 = 16/36.

A few points before we move on. If all the elements in a set are identical, the Gini Impurity is 0. If we have two classes of elements, our max Gini Impurity occurs when there is an equal number of elements from each class in the set. In this case the Gini Impurity is 1/2. Gini Impurity generalizes for more than 2 classes, and the max Gini Impurity approaches 1 as the number of classes approaches infinity.

Now suppose we have a set {red, red, blue, blue, blue, blue}. We consider a split {red blue blue blue} {red blue}. We can measure the goodness of this split by averaging the Gini Impurity of the leaves, weighted by the number of elements in each leaf and compare that number to the Gini Impurity in the root.

The Gini Impurity in the root was 16/36 = 0.444. The weighted average of the Gini Impurity in the leaves is roughly 0.417 So this split reduced our Impurity by about 0.027.

Now we have a method to quantify the goodness of a split, but how do we know what splits to test? Implementations differ here. Ideally, we’d like to test all possible splits but this isn’t always practical. There are typically 4 types of feature vectors:

Boolean – True or False

Numerical – In our example Distance and Income are numerical features.

Factors – Loosely speaking, factors are variables that have a limited number of possible values. Factors can be subdivided into two categories

  • Unordered Factors – This would be like hair color. In our example we had Blonde, Red, Brown, and Black and for our purposes it doesn’t do us any good to try to order these.
  • Ordered Factors – Height. Okay, this one’s borderline numerical but let’s just assume that our website only allows users to select heights between 4’ and 7’ with 1 inch intervals. The important thing to recognize is that we have a finite set of possible values where order matters.

First let’s look at our vector of Incomes.

Income BillMessagedHer?
100 TRUE
50 FALSE
20 FALSE
45 FALSE
200 TRUE
20 FALSE
0 FALSE
80 TRUE
15 FALSE
85 FALSE

How might we write a program to test various splits? It’s easy to get creative here but a simple program would just order the incomes and try the midpoint of each interval. The Gini Impurity reduction for each split would be calculated and the split with the best reduction would be kept.

Next up, unordered factors. What splits would we test on the possible hair colors? In this case all of them,

{Blonde} vs {Red or Brown or Black}
{Blonde or Red} vs {Brown or Black}
{Blonde or Brown} vs {Red or Black}
{Blonde or Black} vs {Red or Brown}
{Blonde or Red or Brown} vs {Black}
{Blonde or Red or Black} vs {Brown}
{Blonde or Black or Brown} vs {Red}

That’s seven unique splits. Here’s the catch – as the number of classes grows, the number of unique splits blows up. Implementations for handling this differ, but one common method is to simply throw an error if there are too many unordered factor classes in the dataset.

Lastly, ordered factors. This is handled in the obvious way. Test all the possible splits without mixing up the order of the factors. If your factors are {Strongly Disagree, Disagree, Agree, Strongly Agree} your splits would be

{Strongly Disagree} vs {Disagree, Agree, Strongly Agree}
{Strongly Disagree, Disagree} vs {Agree, Strongly Agree}
{Strongly Disagree, Disagree, Agree} vs {Strongly Agree}

Now we know what splits to test and how to compare them. We can grow our tree one level out from the root node!

dt7

In what direction should we grow our tree?

Depth First…
dt8

or Breadth First?
dt9

Frankly, it doesn’t matter. Let’s suppose we grow our tree depth first.

The algorithm for growing a decision tree is an example of recursive partitioning. Each node in the tree is grown using the same set of rules as its parent node and the data in the parent node gets partitioned into its child nodes. How do we know when to stop? Ahh, good question!

Clearly, if all of the elements in a node are of the same class it doesn’t do us much good to add another split. Doing so would usually decrease the predictive power of our model. This is known as overfitting. Naturally, this brings up the question, “What if we have a node with 50 elements of the same class and 1 element of a different class?” Hopefully you see where this is going. You, as the omniscient data scientist get to be creative with the rules for termination. Most implementations of decision trees provide a number of parameters for this.

(Special Thanks to Jesse Furmanek for correcting a calculation error in this post.)

ShareTweet about this on TwitterShare on Google+Share on LinkedInShare on Reddit