What does ID3 optimize at each split?

It selects an attribute using information gain, which measures the reduction in training-label entropy.

Does ID3 find the best possible tree?

No. Its greedy choices do not search all possible complete trees.

Why can an identifier be misleading?

Many unique values can separate training examples perfectly while providing little or no predictive information for new cases.

AI Glossary / AI and machine learning / Intermediate

ID3 algorithm

Definition

ID3 is a decision-tree learning algorithm that recursively chooses attributes using information gain. It builds a classifier by selecting tests that reduce uncertainty about the training examples' class labels, then repeating the process within the resulting branches.

What it means

ID3 stands for Iterative Dichotomiser 3 and is associated with J. Ross Quinlan's work on decision-tree induction. Despite the name, a categorical attribute can produce more than two branches when it has several values.

The algorithm starts with labeled examples. At each node, it asks which available attribute most reduces class uncertainty. That uncertainty is commonly measured using entropy, a quantity based on the proportions of the classes.

Information gain compares uncertainty before a split with the weighted uncertainty afterward. The weights reflect how many examples enter each branch, so a tiny pure branch does not count as if it represented the whole dataset.

ID3 is greedy: it chooses a locally attractive split without searching every possible complete tree. This makes the procedure understandable, but it does not guarantee the globally smallest tree or the best future predictions.

How it works

Collect labeled training examples and identify the candidate attributes. The basic ID3 presentation is particularly straightforward for categorical features with known values.

Calculate the current class entropy. For each attribute, divide the examples by its values, calculate each subset's entropy and form their size-weighted average. Subtract that average from the original entropy to obtain information gain.

Select an attribute with the highest gain and create its branches. Repeat within each branch using the remaining relevant attributes, stopping when examples are pure or another stopping condition applies. A practical implementation must define behavior for exhausted attributes and empty subsets.

Evaluate the resulting tree on independent data. Raw information gain can favor attributes with many distinct values, and basic tree growth can overfit. Later algorithms and practical systems introduce additional mechanisms, so their features should not all be attributed to basic ID3.

Three practical examples

1. A teaching dataset uses categorical features to predict whether a fictional service request needs specialist handling. ID3 illustrates how labeled examples can produce an interpretable sequence of questions.

2. An analyst inspects why a unique record identifier receives high information gain. The exercise reveals that perfect training separation may have no useful meaning for new records.

3. A machine-learning course compares ID3 with a later tree method. Students examine the split criterion and handling of numeric or missing values instead of treating every decision-tree implementation as identical.

Think of it this way

Think of choosing the most informative next question in a guessing game. A good question divides possibilities so that uncertainty falls. The analogy is limited because ID3 uses measured label proportions in training data, and the best immediate question does not necessarily produce the best complete strategy for unseen cases.

Worked example

Suppose a node contains eight examples, four labeled yes and four no. Its binary entropy is 1 bit. Attribute A divides them into two equally sized groups: one has three yes and one no, and the other has one yes and three no.

Each group has entropy approximately 0.811 bits, so the weighted post-split entropy is also 0.811. Information gain is therefore 1 minus 0.811, or about 0.189 bits.

Attribute B separates the examples into two pure groups, giving post-split entropy zero and gain 1 bit. Basic ID3 prefers B at this node. Whether that split generalizes depends on what B represents and how the examples relate to future data; the training calculation alone cannot settle that question.

Illustrative case study

Fictional case: Maple Training uses ID3 to teach staff about classification. Its dataset includes a unique request number alongside meaningful service attributes.

The first tree splits on the request number and perfectly separates the training labels. Instructors then present new requests, exposing that the identifier-based split provides no useful general rule for them.

The team removes the identifier from the candidate predictors and discusses independent evaluation. This invented case demonstrates a common modeling pitfall rather than claiming that excluding identifiers automatically produces a strong classifier.

Common misconceptions and mistakes

Mistake: Assuming every ID3 split has exactly two branches. Categorical attributes can create a branch for each value.

Mistake: Treating high information gain as causal importance. The criterion measures label uncertainty reduction in the observed data, not causal influence.

Mistake: Attributing every modern decision-tree feature to ID3. Numeric thresholds, missing-value handling and pruning procedures depend on the particular algorithm and implementation.

Business use

ID3 remains useful for understanding how decision trees learn and why feature choices matter. Its transparent calculations make it a good foundation for discussions of interpretable classification.

For a business deployment, choose and evaluate an actual supported implementation rather than relying on the historical algorithm name. Consider missing data, changing categories, error costs and overfitting. An easy-to-read tree is valuable only if its decisions remain useful on the cases it will encounter.

Check your understanding

An attribute gives every training example its own branch. Does its high information gain prove it is a good predictor?

Answer: No. It may simply memorize the training examples, so usefulness must be evaluated on independent data.

Related terms

Learn next

Learn binary entropy and weighted averages. Compute information gain for two candidate attributes on a small labeled table, then invent a new example to test whether the chosen split provides a meaningful rule.

Sources

J. Ross Quinlan, Induction of Decision Trees: https://doi.org/10.1007/BF00116251. Original publication record consulted; author paper copy: https://storm.cis.fordham.edu/~gweiss/selected-papers/quinlan86.pdf. Entropy example and fictional teaching case are original.

Previous: I.i.d Next: Idempotent matrix