Core ML1986foundational9 min read

Induction of Decision Trees

استقراء أشجار القرار

Quinlan, J. R. — Machine Learning

The problem

In the 1980s, building expert systems required months of interviews with human experts to extract rules by hand. Datasets had many attributes and thousands of objects, but no automatic way to turn raw examples into an interpretable, structured decision procedure. Exhaustive search over all possible decision trees was computationally impossible — a dataset with 10 binary attributes already has billions of possible trees.

The contribution

ID3 (Iterative Dichotomiser 3): a greedy, top-down that builds a by repeatedly choosing the attribute that maximizes — the reduction in Shannon after splitting. A windowing technique samples a subset, builds a tree, tests it on the rest, and iterates until the tree classifies everything correctly. Extensions handle noisy data (by accepting impure leaves) and incomplete data (by distributing uncertain cases probabilistically across branches).

The impact

ID3 established decision tree induction as a practical tool for knowledge acquisition and launched a family of algorithms — C4.5, C5.0, CART — that remain central to machine learning. Its information-gain criterion became the standard splitting heuristic, and the interpretable tree structure influenced decades of work on explainable AI. Modern ensemble methods like Random Forests and Gradient Boosting are built on top of individual decision trees.

A doctor diagnosing a patient doesn't run every possible test at once. She asks the single question whose answer splits the possibilities most — "Does it hurt when you breathe?" — then follows up depending on the response. Each answer eliminates diseases, narrowing the field until one diagnosis remains.

ID3 builds the same kind of flowchart automatically: given a table of patients and their diagnoses, it discovers which question to ask first, second, third — producing a decision tree that any human can follow, branch by branch, to classify a new case.

What is a decision tree?

A decision tree is a classifier shaped like an upside-down tree. Every internal tests one attribute ("Is outlook = sunny?"), every branch corresponds to a possible value of that attribute, and every leaf node assigns a class label.

To classify a new object, you start at the root, answer the question at each node, follow the matching branch, and repeat until you reach a leaf. The leaf tells you the predicted class. The beauty of this structure is transparency: unlike a , you can trace exactly why a was made, node by node.

But how do you build a good tree from data? There are exponentially many possible trees. An exhaustive search is out of the question. ID3's answer: build greedily, one node at a time, always picking the attribute that is most informative right now.

Open in Lab

Click "Build Step" to watch ID3 grow a tree one node at a time, always picking the highest-gain attribute.

The demo wakes as you arrive…

Entropy: measuring uncertainty

Before we can pick the "best" attribute, we need a way to measure how mixed up — how impure — a set of examples is. ID3 borrows Shannon's entropy from .

Imagine a bag of colored balls. If every ball is red, there is zero surprise when you draw one — entropy is 0 (pure). If half are red and half are blue, you're maximally uncertain about what you'll draw — entropy is 1 bit. The more evenly spread the classes, the higher the entropy.

H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i

Shannon entropy of a set S — p_i = fraction of examples in class i · c = number of classes · H = 0 when all examples share one class (pure) · H = 1 bit for two equally sized classes (maximum uncertainty)

Think of entropy as a surprise meter. When you already know the outcome (pure set), there's no surprise — entropy is zero. When anything could happen with equal probability, surprise is maximal. ID3's goal at each node is to ask the question that drives this surprise as close to zero as possible.

Open in Lab

Drag the slider to change the class ratio and watch entropy rise and fall.

The demo wakes as you arrive…

Information gain: choosing the best split

Now we can measure . The next step is: which attribute reduces it the most? Information gain answers this. It measures how much entropy drops when we split the data on a particular attribute.

Imagine you have 14 tennis-match examples — 9 "play" and 5 "don't play". The entropy is about 0.94 bits. Now split on "Outlook" (sunny / overcast / rainy). The weighted average entropy of the three subsets is lower — say 0.69 bits. The difference, 0.94 − 0.69 = 0.25 bits, is the information gain of "Outlook". ID3 computes this for every attribute and picks the one with the highest gain.

Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)

Information gain for attribute A on set S — H(S) = entropy before splitting · S_v = subset of S where attribute A has value v · The weighted sum accounts for subset sizes · Higher gain = more useful attribute

The intuition is a weighing scale: on one side is the current mess (entropy before), on the other side is the mess left after asking this question (weighted entropy after). The bigger the gap, the more useful the question. ID3 always asks the question that tilts the scale the most.

Open in Lab

Pick different attributes to split on and compare their information gain. The attribute with the tallest green bar wins.

The demo wakes as you arrive…

The ID3 algorithm step by step

ID3 is a recursive procedure with an elegant simplicity:

If all examples in the current set belong to the same class, create a leaf with that class label. Done.
If no attributes remain, create a leaf with the majority class (a forced decision when attributes are exhausted).
Otherwise, compute information gain for every remaining attribute, select the one with the highest gain, create a node for it, partition the examples by its values, and recurse on each subset.

The recursion builds the tree from the root downward, branching at each level, until every path ends in a pure leaf or runs out of attributes. This is what we call — each split carves the data space into smaller, purer regions.

Open in Lab

Step through the full ID3 algorithm: compute gains, pick the best attribute, partition, and recurse.

The demo wakes as you arrive…

Windowing: scaling to large datasets

The basic ID3 algorithm processes all examples at once. When datasets are very large, Quinlan introduced a windowing technique: start with a random subset (the "window"), build a tree from it, test the tree on the remaining examples, add any misclassified examples to the window, and repeat.

This is like studying for an exam: you practice on a sample of questions, check your mistakes, focus on the ones you got wrong, and repeat until you get everything right. Windowing often converges to correct trees much faster than processing the entire dataset from the start, especially in -free domains.

Dealing with the real world: noise and missing values

Real-world data is messy. Two kinds of mess threaten decision trees:

Noise: some examples have wrong class labels or incorrect attribute values. A single mislabeled example can create an entire extra branch — a branch that exists only to accommodate one error.
: some attributes are unknown for certain examples. If a patient's blood test result is missing, which branch should they follow at the "blood test" node?

Quinlan proposed two extensions. For noise, the tree can accept impure leaves — instead of splitting until every leaf is perfectly pure, it stops early and assigns the majority class. This is an early form of what we now call . For missing values, an example with an unknown attribute value is sent down all branches simultaneously, weighted by the proportion of known examples in each branch.

Open in Lab

Toggle noise on/off to see how a mislabeled example creates spurious branches, and how pruning simplifies the tree.

The demo wakes as you arrive…

A shortcoming: bias toward many-valued attributes

Information gain has a hidden bias: it prefers attributes with many possible values. Consider an attribute like "PatientID" — it uniquely identifies each example, so splitting on it produces one pure leaf per example. Information gain is maximal, but the tree is useless — it has memorized the rather than learning a pattern.

Quinlan recognized this problem and later introduced gain ratio in C4.5, which normalizes information gain by the attribute's own entropy (its "split information"). This penalizes attributes that create many small branches without truly reducing class uncertainty.

GainRatio(S, A) = \frac{Gain(S, A)}{SplitInfo(S, A)}

Gain ratio — C4.5's correction to information gain — SplitInfo measures the entropy of the attribute itself (how evenly it divides examples among its values). Dividing by it penalizes many-branched splits.

The same idea in code

ID3 core — entropy, information gain, and recursive tree buildingpython

Simplified to show the idea — not the real implementation.

import math
from collections import Counter

def entropy(labels):
    """H(S): Shannon entropy of a list of class labels."""
    n = len(labels)
    counts = Counter(labels)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

def info_gain(data, attr_index, label_index):
    """Gain(S, A): how much entropy drops when we split on attribute A."""
    total = len(data)
    h_before = entropy([row[label_index] for row in data])

    # Group rows by attribute value
    splits = {}
    for row in data:
        splits.setdefault(row[attr_index], []).append(row)

    # Weighted entropy after split
    h_after = sum(
        (len(subset) / total) * entropy([r[label_index] for r in subset])
        for subset in splits.values()
    )
    return h_before - h_after

def id3(data, attrs, label_index):
    """Build a decision tree recursively."""
    labels = [row[label_index] for row in data]

    # All same class? → leaf
    if len(set(labels)) == 1:
        return labels[0]

    # No attributes left? → majority class
    if not attrs:
        return Counter(labels).most_common(1)[0][0]

    # Pick the attribute with the highest information gain
    gains = {a: info_gain(data, a, label_index) for a in attrs}
    best = max(gains, key=gains.get)

    tree = {best: {}}
    remaining = [a for a in attrs if a != best]

    for val in set(row[best] for row in data):
        subset = [row for row in data if row[best] == val]
        tree[best][val] = id3(subset, remaining, label_index)

    return tree

# That's all of ID3. The rest is choosing good data.

Why it mattered

1966
CLS (Concept Learning System)
Hunt's CLS introduced top-down tree construction from examples, using cost-based attribute selection. ID3's direct ancestor.
1979
Early ID3
Quinlan applied the first version of ID3 to chess endgame classification, demonstrating that information-theoretic splitting could discover complex rules automatically.
1986
The paper — Induction of Decision Trees
Quinlan published the definitive description of ID3 with extensions for noise and missing data. Published in Machine Learning journal, volume 1.
1984
CART (Classification and Regression Trees)
Breiman et al. independently developed CART, using Gini impurity instead of entropy and introducing cost-complexity pruning. A parallel lineage.
1993
C4.5
Quinlan's successor to ID3 — handles continuous attributes, uses gain ratio, and adds post-pruning. Became one of the most cited algorithms in machine learning.
2001
Random Forests
Breiman combined many decision trees into an ensemble, each trained on a random subset of features and data. Trees as building blocks of powerful models.
2016
XGBoost dominates Kaggle
Gradient-boosted trees, descendants of ID3's lineage, became the winning algorithm in the majority of tabular data competitions, confirming trees' enduring power.

ID3 proved that you don't need to search every possible tree. A guided by information theory can build interpretable classifiers that are surprisingly accurate. Every random forest, every gradient-boosted , every decision tree in scikit-learn traces its lineage back to this 1986 paper.

CitationQuinlan, J. R.. Induction of Decision Trees. Machine Learning, 1986.

Terms in this paper

Decision Treeشجرة القرار الإحصائية
Entropyالعشوائية الدلالية
Information Gainالكسب المعلوماتي
Greedy Algorithmالخوارزمية الجشعة
Recursive Partitioningالتقسيم التكراري
Classificationالتصنيف
Information Theoryنظرية المعلومات
Impurityالشائبة
Overfittingفرط التخصيص
Pruningتشذيب الشبكات العصبية