Decision Trees

What Is a Decision Tree?

A decision tree is exactly what it sounds like — a tree-shaped model that makes decisions. Each internal node asks a question about a feature, each branch represents a possible answer, and each leaf gives you a final classification.

Here's a classic example: should you play tennis today?

The tree checks the weather outlook first. If it's overcast, just go play — always yes. If it's sunny, check the humidity. If it's rainy, check the wind. Simple and readable.

We can also express this tree as a set of logical rules (called disjunctive normal form):

• Yes
• Yes
• Yes

This is one of the best things about decision trees, you can always convert them into human-readable if-then rules.

Why Decision Trees?

Decision trees have several properties that make them a solid starting point for classification problems:

• They handle both discrete and continuous features. Discrete features like color (red, blue, green) work naturally. For continuous features like temperature, the tree can split on a threshold (e.g., temperature < 30°C vs. ≥ 30°C).
• They naturally represent disjunctive (OR) concepts. Some classification boundaries are complex unions of conditions, but decision trees handle this natively.
• They're robust to noise. Both mislabeled examples and noisy feature values can be tolerated.
• They handle missing values. If a data point doesn't have a value for some feature, the algorithm can still work with it.
• Classification trees produce discrete class labels at the leaves, while regression trees output continuous real-valued predictions.

How Do We Build a Decision Tree?

The core algorithm is a top-down, recursive, divide-and-conquer approach. Here's the pseudocode:

DTree(examples, features):
    If all examples belong to one class:
        return a leaf with that class label
 
    If no features are left:
        return a leaf with the majority class
 
    Pick the "best" feature F
    Create a node for F
    For each value v of F:
        Let examples_v = subset of examples where F = v
        If examples_v is empty:
            attach a leaf with the majority class of examples
        Else:
            attach DTree(examples_v, features - {F})
 
    Return the tree rooted at this node

The key question is: how do we pick the "best" feature?

Entropy and Information Gain

This is where information theory comes in. We want to choose the feature that best separates the data — the one that brings us closest to pure (single-class) subsets.

Entropy

Entropy measures the impurity or disorder of a set. For a binary classification:

where is the fraction of positive examples and is the fraction of negatives.

Some intuition:

• If all examples are the same class → entropy = 0 (perfectly pure, no uncertainty)
• If examples are evenly split (50/50) → entropy = 1 (maximum uncertainty)

For multi-class problems with classes, it generalizes to:

You can think of entropy as the average number of bits needed to encode the class label of a randomly chosen example — more uncertainty means more bits.

Information Gain

Information gain measures how much entropy decreases after we split on a particular feature:

where is the subset of where feature has value .

In plain language: information gain = entropy before the split − weighted average entropy after the split. The feature with the highest information gain wins.

A Worked Example

Consider four examples with features (size, color, shape) and a binary class (+/−):

The overall dataset has 2 positives and 2 negatives, so .

Splitting on Size:

• big → 1+, 1− →
• small → 1+, 1− →
• — useless!

Splitting on Color:

• red → 2+, 1− →
• blue → 0+, 1− →
• — much better.

Splitting on Shape:

• circle → 2+, 1− →
• square → 0+, 1− →
• — tied with color.

So we'd pick either color or shape first (both have gain = 0.311), and definitely not size (gain = 0).

The ID3 Algorithm

The algorithm we've been describing is called ID3, invented by J. Ross Quinlan in 1979. It uses Shannon's information theory (1948) to select features via information gain. Key characteristics:

• Builds the tree top-down with no backtracking (the algorithm is stubbornly committed to its choices, greedy algorithm)
• Selects the feature with the highest information gain at each step
• Runs recursively on non-leaf branches until all data is classified
• Searches the entire dataset to construct the tree Later improvements led to C4.5 (Quinlan, 1993), which handles continuous attributes, missing values, and pruning. Another parallel development was CART (Classification and Regression Trees) by Breiman and Friedman.

A Fun Example: Classifying Simpsons Characters

Let's say we want to classify Simpsons characters as Male or Female using three features: hair length, weight, and age.

The dataset has 4 females and 5 males, with .

We compute the information gain for splitting on each feature:

• Hair Length ≤ 5? → Gain = 0.0911
• Weight ≤ 160? → Gain = 0.5900 ← Winner!
• Age ≤ 40? → Gain = 0.0183 Weight gives us the best split. Everyone over 160 lbs turns out to be male (entropy = 0 on that branch — done!). But the ≤160 group still has a mix (4F, 1M), so we recurse.

On the second split, we find that Hair Length ≤ 2 perfectly separates the remaining group: Bart (short hair, male) vs. the females (longer hair).

The final tree:

            Weight ≤ 160?
            /           \
          yes            no
          /               \
   Hair Length ≤ 2?      Male
      /        \
    yes         no
    /             \
  Male          Female

And as rules:

• If Weight > 160 → Male
• Else if Hair Length ≤ 2 → Male
• Else → Female Now if Comic Book Guy shows up (Hair: 8", Weight: 290, Age: 38), the tree says: Weight 290 > 160 → Male. Correct!

The Overfitting Problem

Here's the catch: a tree that perfectly classifies every training example isn't necessarily a good tree.

Overfitting happens when a model fits the training data too well — including its noise and quirks — and performs poorly on new, unseen data. Formally, hypothesis overfits if there exists another hypothesis that has higher training error but lower test error.

Think of it this way: if you measure 10 data points for Ohm's Law () and fit a 9th-degree polynomial, you'll pass through every point perfectly. But that wiggly curve is way worse at predicting new measurements than a simple straight line that misses a few points.

The same thing happens with decision trees — noise in the data can cause the algorithm to create extra branches that capture randomness rather than real patterns.

How Noise Causes Overfitting

Imagine our color/shape example, and one training instance gets mislabeled. The tree might need to add extra splits on irrelevant features (like size) just to account for that one noisy data point. The result is a bigger, more complex tree that generalizes poorly.

Pruning: The Cure for Overfitting

There are two main strategies:

Prepruning — Stop growing the tree early, before it perfectly fits the training data. For example, stop when a node has too few examples to split reliably.

Postpruning — Grow the full tree first, then cut back branches that don't help generalization. This is generally more effective since it's hard to know when to stop growing.

Reduced Error Pruning

A common postpruning method:

1. Split your data into a "grow" set and a "validation" set
2. Build a complete tree from the grow set
3. For each internal node, try replacing its subtree with a leaf (majority class)
4. If the replacement improves accuracy on the validation set, make it permanent
5. Repeat until no more pruning helps The downside is that you "waste" some training data on validation. An alternative is to run multiple trials with different random splits, average the resulting tree complexity, then grow a final tree from all the data up to that average complexity.

Other Pruning Approaches

• Statistical tests — Check whether the pattern at a node is statistically significant or just random chance
• Minimum Description Length (MDL) — Ask whether the extra tree complexity is worth it compared to just memorizing the exceptions

Computational Complexity

In the worst case (a complete tree testing every feature on every path), building a decision tree takes time, where is the number of examples and is the number of features.

In practice, the tree is rarely complete, and the complexity is roughly linear in both and — which is why decision trees scale well to large datasets.

Strengths and Limitations

Strengths

• Produces interpretable, human-readable rules
• Fast to build and fast to classify new instances
• Handles both categorical and numerical features
• Robust to noise and missing data
• No need for feature scaling or normalization

Limitations

• Prone to overfitting, especially with small datasets
• Tests only one feature at a time (axis-aligned splits) — can't easily capture diagonal decision boundaries
• Information gain has a bias toward features with many values
• Greedy construction doesn't guarantee the globally optimal tree (finding the smallest consistent tree is NP-hard)
• Produces a single deterministic hypothesis with no confidence estimates

What Comes Next?

Decision trees are a foundation for more powerful methods:

• Random Forests — build many decision trees on random subsets of features and data, then vote
• Gradient Boosted Trees (XGBoost, LightGBM) — build trees sequentially, each one correcting the errors of the previous
• C4.5 / C5.0 — Quinlan's improvements to ID3 with better handling of continuous features, missing values, and pruning These ensemble methods are among the most successful algorithms in practice, especially for structured/tabular data — and they all build on the decision tree concepts we've covered here.

These notes are based on Week 4 of WIA1006/WID3006 Machine Learning at Universiti Malaya (Semester 2, 2025/2026). If you found this helpful, stay tuned for more ML concepts explained from scratch!