Building Decision Trees with Entropy and Information Gain

Hello! Welcome to our next lesson.

Introduction

In our last session, we explored Support Vector Machines (SVMs), a powerful algorithm that finds an optimal decision boundary by maximizing the margin between classes. Especially with the kernel trick, SVMs can feel a bit like a "black box," creating complex separations in high-dimensional spaces that are difficult to visualize and interpret.

Today, we shift gears to a completely different family of models: Decision Trees. In stark contrast to SVMs, decision trees are often called "white box" models because their decision-making process is transparent and highly interpretable. This lesson is designed to help you achieve the learning outcome: Build decision trees using entropy and information gain criteria.

We will deconstruct the decision tree algorithm from the ground up, covering:

1. The intuitive structure of a decision tree and how it makes predictions.
2. The core mathematical concepts of entropy and information gain, which are used to measure the quality of a split.
3. The recursive, greedy algorithm used to construct the tree.
4. How to implement the entire process from scratch, leveraging your background in computer science and Python.

Let's begin by understanding the basic anatomy of a decision tree.

1. What is a Decision Tree?

At its heart, a decision tree is a flowchart-like structure that makes predictions by asking a series of simple questions about the features of your data.

• The tree starts at a root node, which contains all your data.
• It branches out into internal nodes (or decision nodes), where a specific feature is tested against a condition (e.g., "Is room size > 5?").
• Each branch represents the outcome of that test.
• This process continues until we reach a leaf node, which represents a final decision or a class label.

To classify a new data point, you start at the root and traverse down the tree, following the path that matches the data point's features until you arrive at a leaf node. The label of that leaf node is your prediction.

This video provides an excellent visual introduction to the structure of a decision tree and how it partitions the feature space.

As you saw, the structure is quite intuitive. The real question is: How does the algorithm decide which feature to split on at each node, and what threshold to use? The answer lies in finding splits that make the resulting child nodes as "pure" as possible.

2. The Art of Splitting: Entropy and Information Gain

The goal of building a decision tree is to create leaf nodes that are as homogeneous or "pure" as possible—ideally, containing samples from only one class. To do this, we need a way to quantify the impurity of a node. This is where entropy comes in.

Entropy: A Measure of Impurity

In information theory, entropy is a measure of uncertainty or disorder. For a set of data $S$, the entropy is calculated as:
$H(S)=-{\sum }_{i=1}^c{p}_i{\log }_2(p_i)$
where $c$ is the number of classes, and $p_i$ is the proportion (probability) of samples belonging to class $i$.

• Maximum Entropy (H=1): Occurs when the classes are perfectly balanced (e.g., 50% Class A, 50% Class B). This is a state of maximum impurity and uncertainty.
• Minimum Entropy (H=0): Occurs when all samples in the node belong to a single class (e.g., 100% Class A). This is a state of perfect purity.

Information Gain: Quantifying the Quality of a Split

Now that we can measure impurity with entropy, we can evaluate a potential split. We want to choose the split that provides the biggest reduction in entropy. This reduction is called Information Gain.

The Information Gain for a split on an attribute $A$ is calculated as the entropy of the parent node minus the weighted average of the entropies of the child nodes.
$IG(S,A)=H(S)-{\sum }_{v\in \text{children}}\frac{|S_v|}{|S|}H(S_v)$
where:

• $H(S)$ is the entropy of the parent node.
• $\text{children}$ is the set of child nodes created by the split.
• $|S_v|$ is the number of samples in a child node $v$.
• $|S|$ is the total number of samples in the parent node.
• $H(S_v)$ is the entropy of a child node $v$.

The algorithm greedily selects the feature and threshold that maximize the information gain at each step.

The following video provides a clear, step-by-step example of how to calculate both entropy and information gain.

3. Building the Tree: A Recursive, Code-Driven Approach

With the concepts of entropy and information gain in hand, we can now outline the algorithm for building a decision tree. It's a recursive process that you'll find quite natural given your CS background.

The Algorithm:

1. Start with a node containing a dataset (initially, the entire training set).
2. Check for stopping criteria:
   • Is the node pure (entropy is 0)?
   • Have we reached the maximum allowed depth?
   • Are there too few samples left to split?
   • If any of these are true, create a leaf node and assign it the majority class of the samples in the node.
3. If no stopping criteria are met, find the best possible split:
   • Iterate through every feature.
   • For each feature, iterate through all its unique values (or potential thresholds for continuous features).
   • Calculate the information gain for each potential split.
4. Select the feature and threshold that yielded the highest information gain.
5. Split the dataset into two subsets (left and right branches) based on this best split.
6. Recursively call the tree-building function on the left subset and the right subset.

This process creates the tree structure by making locally optimal decisions at each node.

The best way to solidify this understanding is to see it implemented in code. The following video provides a complete, from-scratch implementation of a decision tree in Python. It's an excellent resource that connects all the theory directly to practice.

Test your understanding!

Decision tree construction is often described as a "greedy" algorithm.

1. What does this mean in the context of finding the best split at each node?
2. What is a potential downside of this greedy approach? (Hint: Think about local vs. global optimality).

Show answer

1. A "greedy" approach means that at each step of building the tree, the algorithm chooses the split that is locally optimal—that is, the split that provides the maximum information gain at that specific node, without considering the impact this split might have on future splits further down the tree.
2. The potential downside is that a series of locally optimal splits does not guarantee a globally optimal tree. A different, less optimal split at an early stage might have opened up the possibility for much better splits later on, leading to a better overall tree. However, the greedy algorithm will never backtrack to explore this, as it would be computationally infeasible to evaluate all possible tree structures.

Conclusion

In this lesson, we have thoroughly dissected the Decision Tree algorithm. We moved from its intuitive, flowchart-like structure to the core mathematical engine that powers it.

Key Takeaways:

• Decision trees are interpretable, "white box" models that classify data by making a series of decisions.
• The construction of the tree is a recursive process that aims to create pure leaf nodes.
• Entropy is a measure of impurity or uncertainty within a node.
• Information Gain is the reduction in entropy achieved by a split. The algorithm greedily chooses the split that maximizes this value.
• Stopping criteria, such as max_depth or min_samples_split, are crucial hyperparameters used to control the complexity of the tree and prevent overfitting.

Preview of the next lesson:
We have now explored several major paradigms in classification. Next, we will examine another classic algorithm: K-Nearest Neighbors (KNN). KNN takes a completely different, non-parametric approach. Instead of learning an explicit model, it makes predictions based on the labels of the "k" closest training examples in the feature space.