Decision Tree Basics

Predictive Analytics

Predictive analytics problems can be largely categorized into either class prediction (classification) or numeric prediction (regression) problems.

In classification, we use the information in the sample data to sort the data into distinct classes — this is what a classification tree does:

• predict whether a customer is a loyal customer or a churn customer
• predict whether a loan is going to default or not
• predict whether a passenger of the Titanic is going to survive or not

In numeric prediction, we predict the numeric value of a target/label attribute — this is what a regression tree does:

• predict the housing price
• predict how much a customer is going to spend in the next quarter

Decision trees can be used for both kinds of prediction, which is why they are often referred to as CART: Classification and Regression Trees.

Classification Trees (Decision Trees)

Decision trees (DTs), or classification trees, are one of the most popular classification techniques:

• easy to set up
• easy to interpret (especially for business users)
• computationally cheap

Almost all data mining packages include DTs.

Here is a small tree that recommends a major based on the grades a student earned in a few courses. The vocabulary you need is root, node, and leaf:

The root is the first question the tree asks, an internal node is any later question, and a leaf is a final answer — there is nothing left to ask.

Homogeneity/Purity of Data

The basic idea of a decision tree is to split the dataset based on the homogeneity (of the same kind) of the data, i.e., to reduce impurity.

Impurity (uncertainty) is at its maximum when all possible classes are equally represented — for example, the same number of "default" and "not default" customers. Suppose we have 30 loan customers, 16 of whom defaulted, and we split them twice, first on balance and then on age:

The top leaf contains 10 customers who all belong to the same class: it is 100% pure, or has 0% impurity. The tree has done its job on that branch. The two middle leaves are still mixed, so they are still impure.

Entropy

Entropy is one of the most common measures for calculating impurity. It was proposed by Claude Shannon, known as "the father of information theory":

where $p(x_i)$ is the probability of class $x_i$ in the data, and $n$ is the total number of classes.

For two classes, entropy is 0 when the data is completely pure (every case belongs to one class) and 1 when the two classes are split 50/50 — the curve peaks in the middle:

import numpy as np
import matplotlib.pyplot as plt

p = np.linspace(0.001, 0.999, 500)
entropy = -p * np.log2(p) - (1 - p) * np.log2(1 - p)

plt.plot(p, entropy)
plt.xlabel('% of one class')
plt.ylabel('entropy')
plt.title('entropy for two classes')
plt.show()

For the loan dataset above, there are two classes — "default" (16 cases) and "not default" (14 cases) — so the entropy of the entire dataset is:

Almost 1 — this dataset is about as impure as a two-class dataset can be.

ID3 Decision Tree Algorithm

ID3 (Iterative Dichotomiser 3) was developed in 1986 by Ross Quinlan. We will walk through it using the classic golf dataset: decide whether to play golf or not based on four attributes — outlook, temperature, humidity, and windy.

Building the tree comes down to answering two questions over and over:

1. Where to split the data?
2. When to stop splitting?

Sources: ID3 algorithm and saedsayad.com/decision_tree.htm.

Entropy Calculation Using Frequency Tables

There are two entropy calculations we need, and both can be done from a frequency table.

Entropy of the target variable

The golf dataset has 9 "yes" and 5 "no":

Entropy of the target given one feature

where $T$ is the target and $X$ is the feature. Cross-tabulate the feature against the target:

Each branch contributes its own entropy, weighted by how much of the data lands in it:

Note that the overcast branch contributes nothing: all four of its cases are "yes", so its entropy is 0.

Information Gain/Entropy Reduction

Information gain is the decrease in entropy after the dataset is split on an attribute — information gain is entropy reduction:

For outlook:

Constructing a decision tree is all about finding the attribute that returns the highest information gain at each split.

Choosing the First Split

Repeat the same frequency-table calculation for all four attributes:

Outlook has the largest gain, so it becomes the decision node. Divide the dataset by its branches and repeat the same process on every branch.

Outlook = sunny — still mixed, needs further splitting:

Outlook = overcast — already pure (entropy is 0), no more splitting:

Outlook = rainy — still mixed, needs further splitting:

Splitting Recursively

The rule for each branch:

• a branch with entropy of 0 is a leaf node
• a branch with entropy greater than 0 needs further splitting
• repeat recursively on the non-leaf branches until all data is classified

Take the sunny branch (5 rows, entropy 0.971) and compute the gain of the three remaining attributes on those rows only:

Windy splits the sunny rows perfectly, so it is chosen as the next decision node — and both of its branches are pure, so both are leaves:

The rainy branch is still impure, so run the same calculation once more on its 5 rows:

Humidity splits it perfectly. Every branch is now pure, so the tree is complete:

Read a prediction off the tree by walking from the root down to a leaf. A cool, humid, windy, overcast day? Outlook is overcast, so play golf — the tree never even looks at the other three attributes.

Split Points for Numeric Variables

The golf dataset above used categorical attributes ("hot", "high"). Real temperature and humidity readings are numbers, and a decision tree needs a split point to turn a number into a yes/no question.

Method 1: use averages of available values. Sort the values, then try the midpoint between each adjacent pair as a candidate split. For temperature: first split at Avg(64, 65) = 64.5, then Avg(65, 68) = 66.5, and so on — computing the information gain of each candidate and keeping the best.

Method 2: discretize the values via "binning". Turn the numbers back into categories once, up front. For temperature: >= 80 is "hot", between 70 and 79 is "mild", and less than 70 is "cool".

When to Stop?

The ID3 algorithm as described keeps splitting until every leaf is pure, which may lead to a very complex tree with hundreds of nodes. Such a tree may work well on the training data but predict poorly on unseen data — this is called overfitting, and we will discuss it more in a later lecture.

The general fix is regularization: limiting how complex a model may become, so it can't fit the training data perfectly. You give up a little training accuracy to gain accuracy on new data.

For a decision tree, regularization means pruning, which comes in two kinds:

• Pre-pruning — stop the tree from growing, such as by setting a maximum depth or a minimum information gain required to make a split: max_depth, min_samples_leaf, min_samples_split, max_leaf_nodes, min_impurity_decrease.
• Post-pruning — fully grow the tree, then cut back the branches that aren't worth keeping, with minimal cost-complexity pruning: ccp_alpha.

Every stopping rule below is an argument to DecisionTreeClassifier, and each one answers "when to stop" differently:

Read the default column again: scikit-learn prunes nothing out of the box. A node splits as long as it is impure and holds at least two rows, so the tree grows until every leaf is pure — the overfitting-prone tree this section opened with. A tree left at its defaults can score a perfect 1.0 on the training data and still lose to a three-condition rule you wrote by hand. Note also that criterion defaults to 'gini' rather than the 'entropy' we computed by hand above.

So pre-pruning is what you reach for first, and two of those options carry most of the weight:

• max_depth limits how many questions the tree may ask before it must decide. Depth 3 means at most 3 questions, so at most 8 leaves. This is the interpretability knob: a depth-3 tree fits on a slide and you can read it aloud to the revenue director.
• min_samples_leaf limits how much evidence each answer must rest on. Set it to 20 and the tree may not create a leaf covering fewer than 20 training rows — so it can't propose a rule backed by two customers. This is the noise knob.

from sklearn.tree import DecisionTreeClassifier

tree_clf = DecisionTreeClassifier(criterion='entropy', max_depth=3, min_samples_leaf=20)

The two are not the same constraint: depth caps the questions, leaf size caps the confidence. A shallow tree can still isolate a single customer, if one split happens to cut that customer off at depth 2.

Post-Pruning with ccp_alpha (optional)

ccp_alpha stands for cost-complexity pruning alpha. It scores a tree like this:

• Impurity of its leaves — how badly the tree fits the training data: the Gini or entropy of each leaf, weighted by its share of the rows. A fully grown tree scores 0 here.
• α × number of leaves — a price per leaf. Every extra leaf makes the tree more complex, and α says how much that complexity costs.

The pruning then works like this:

1. Grow the full tree, with every leaf pure.

2. For each branch, ask how much impurity it removes per extra leaf it adds. That is the branch's effective α:

   $$\text{effective } \alpha = \frac{\text{impurity if the branch became one leaf} - \text{impurity of its leaves}}{\text{its number of leaves} - 1}$$

3. If a branch's effective α is below ccp_alpha, it does not pay for its leaves, so it is cut back to a single leaf. The weakest branch goes first, and this repeats until every remaining branch pays for itself.

So ccp_alpha=0 (the default) prunes nothing, and a larger ccp_alpha makes every leaf more expensive, so the tree gets smaller.

The business framing: every leaf has to earn its keep. A branch stays only if the fit it adds is worth more than the complexity it costs.

Which numbers to use cannot be read off the data. In Model Evaluation we score several candidate values on rows the tree never saw during training, and keep whichever wins — until then, any particular depth is a guess.