Decision Tree Classification

The central difficulty is not merely assigning labels. It is selecting the complete decision structure. Because exact search is computationally hard, the practical method replaces one difficult global choice with a sequence of local choices.

Programming

Interactive lab

Try it: Decision Tree (ID3)

How ID3 grows a decision tree greedily: label the node by majority vote, compute the gain of every remaining attribute, split on the best one, and recurse until the node is pure or no attributes are left — then classify a new row by walking the tree.

How it works

Start with one root leaf holding every row and give it the majority label.
If all rows agree, or no attributes are left, the node stays a leaf.
Otherwise compute for each remaining attribute (C = entropy, training error or Gini).
Split on the attribute with the largest gain and repeat on every child with that attribute removed.
Classify a query by following its attribute values from the root to a leaf.

Default run (15 steps): ID3 starts with one root leaf holding all 14 rows (9 Yes / 5 No); its majority label is Yes. Impurity measure: entropy. … The query reaches the leaf Humidity = Normal: prediction Play = Yes.

Simplified: A fixed 4-attribute categorical table (at most 14 rows) with a Yes/No label. A value with no rows becomes a leaf with the parent's majority label, and a tied majority keeps the parent's label; real trees also prune.

Educational simulation

Loading the simulation…

Why Tree Learning Needs a Search Strategy

Decision tree classification can be viewed as a search problem. The learner wants a tree that minimizes the relevant bound on the tree's learning performance. In principle, it could try to compare complete trees and choose the best one. In practice, finding that tree exactly is computationally hard, so practical algorithms construct a tree step by step instead.

What does the learner face when it searches for a tree with the best overall performance?

Key point

The Initial Root Leaf

A practical tree-growing algorithm begins with a single root leaf. That leaf represents all labeled training examples currently reaching the tree. Before any split is selected, the leaf receives the majority label among those examples. This gives the tree a prediction even before it has any internal decision structure.

How does one root leaf containing all labeled examples become multiple child leaves after a selected split?

Worked example

A Majority Label Before Splitting

Imagine a training set reaching one root leaf. The examples have two possible class labels, and one label occurs more often than the other.

1
Represent the examples
The single root leaf stands for every labeled example in the training set.
2
Assign the initial prediction
The algorithm gives the root leaf the majority label.
3
Prepare for comparison
The learner can now evaluate whether a feature-based split would improve the tree.

Result

The tree begins with one labeled root leaf, even though no feature test has been selected yet.

Comparing Candidate Splits

After the current leaf has a majority-label prediction, the learner considers possible feature-based splits. A gain measure compares the improvement offered by those candidates. The gain procedure receives a training set and a feature index, evaluates the gain associated with splitting according to that feature, and turns several possible decisions into comparable candidates.

How do candidate feature splits change the current leaf, and how does gain identify the preferred next action?

Worked example

Choosing Between Two Current Candidates

A growing tree has one leaf to consider. The learner evaluates two available feature-based splits.

1
Keep the current leaf as the baseline
The leaf already has a prediction from the majority vote.
2
Evaluate each feature
The gain procedure compares the improvement offered by splitting according to each candidate feature.
3
Select the better current action
The candidate with the better gain is preferred for this stage, unless the algorithm chooses not to split.

Result

Gain guides the next local decision. It does not by itself prove that the completed tree will be globally optimal.

Recursive Partitioning

When the learner replaces a leaf with a selected feature-based decision structure, the branches represent the outcomes of that split. The examples reaching the original leaf are consequently represented in the resulting child leaves according to those branch outcomes. The procedure can then continue evaluating leaves in the growing tree.

How do examples move through successive feature tests, and which subset reaches each leaf?

1
Start with one root leaf containing the labeled training examples.
2
Give that leaf the majority label.
3
Evaluate candidate feature-based splits with a gain measure.
4
Choose the locally best next action, or choose not to split.
5
Replace the selected leaf with a decision structure whose branches represent the split outcomes.
6
Continue evaluating leaves in the growing tree.

Greedy Choices and Global Quality

This construction is greedy because it chooses a locally best action at each stage. At a current leaf, the algorithm compares available splits using the gain measure and may choose the best one according to that criterion. It may also choose not to split. The decision is made using the information available at the current stage rather than by examining every possible completed tree.

How does choosing the best current split differ from searching for the globally optimal complete tree?

Locally best split	Globally optimal tree
A next action selected at the current stage	A complete tree selected for its overall performance
Uses a gain measure to compare current candidates	Requires considering the full tree-search problem
Supports practical step-by-step construction	Is difficult to find exactly
Does not guarantee the best completed tree	Is the target of the idealized global search

The local decision used by practical construction is not the same as the global optimization goal.

A locally best split can lead to a tree that is not globally optimal because the gain measure evaluates the current comparison, whereas global quality depends on the complete decision structure. The practical algorithm accepts this distinction: it uses local decisions to make tree learning tractable rather than claiming that each local choice solves the entire search problem.

Common Misunderstandings

Common mistake
Assuming the tree is built by checking every possible complete tree.
What it looks like
The practical procedure chooses actions one stage at a time instead of examining every completed tree.
Why it fails
The exact search for the best tree is computationally hard.
Do this instead
Separate the global search goal from the practical greedy construction.
Common mistake
Thinking the root leaf has no prediction until after the first split.
What it looks like
A learner describes the initial root as unlabeled.
Why it fails
The root leaf is assigned the majority label before a split is selected.
Do this instead
Remember that labeling happens before splitting.
Common mistake
Treating gain as proof that a final tree will be optimal.
What it looks like
A candidate with the best current gain is called the globally best tree.
Why it fails
Gain compares the improvement offered by current candidate splits; it does not guarantee global optimality.
Do this instead
Call it the locally preferred next action.
Common mistake
Confusing a split with a complete tree.
What it looks like
The selected feature split is treated as the entire learned model.
Why it fails
A split replaces a leaf with a decision structure, after which the procedure can continue evaluating leaves.
Do this instead
View the split as one step in recursive tree growth.

Check Your Understanding

What do you think happens?

A decision tree learner has just started. Before evaluating any feature split, what does the initial root leaf represent and what label does it receive?

A randomly selected example and a randomly selected label
All labeled examples and their majority label
Only the examples that already passed a feature test
A complete globally optimal tree

Reveal answer

Answer:

All labeled examples and their majority label

The practical construction begins with one root leaf representing the labeled examples. That leaf receives the majority label before a split is selected.

MEDIUM

Explain, in your own words, why a split with the best current gain is not necessarily part of the globally optimal tree. Then describe the sequence from root leaf to candidate comparison to child leaves.

Hints

Mention the difference between a current comparison and the complete tree.
Include the majority label assigned to the initial root leaf.
Explain that a selected split replaces a leaf with a decision structure.

Your attempt (not saved)

Key Takeaways

1
Finding the complete decision tree with the best relevant bound is computationally hard.
2
Practical construction begins with one root leaf labeled by the majority class.
3
A gain measure compares the improvement offered by candidate feature-based splits.
4
Greedy growth selects a locally best action at the current stage or chooses not to split.
5
A locally best split is not a guarantee of a globally optimal completed tree.

At a glance

Decision tree learning is a computationally hard global search problem.
A practical learner starts with a majority-labeled root leaf.
Gain compares candidate splits at the current stage.
Greedy tree growth repeatedly makes local decisions and can continue after a leaf is split.
Local gain does not guarantee global optimality.

Related concepts

More concepts starting with D