Core ML1993foundational9 min read
C4.5: Programs for Machine Learning
C4.5: برامج للتعلّم الآلي
Quinlan, J. R. — Morgan Kaufmann
The problem
ID3 could only handle categorical attributes, ignored missing data, and produced decision trees that memorized noise because it had no . Every real-world dataset has continuous measurements, incomplete records, and noise — so ID3's trees were fragile, overgrown, and unreliable on new data.
The contribution
C4.5 extended ID3 with four major innovations: (1) replaces to correct the bias toward attributes with many values; (2) continuous attributes are handled by finding optimal split thresholds; (3) are managed by fractional instance weighting; (4) error-based pruning trims overfitted branches after the tree is fully grown. Additionally, C4.5 converts decision trees into if-then sets that are often more compact and interpretable, using the minimum description length principle to select the best subset of rules.
The impact
C4.5 became the most widely used algorithm in for over a decade. It was voted the #1 algorithm in a 2008 survey of top data mining methods. Its design choices — gain ratio, error-based pruning, rule extraction — became standard components in later tree-based methods. Random Forests, gradient boosting (XGBoost, LightGBM), and ensemble methods all descend from the decision tree lineage that C4.5 refined and popularized.
Imagine a doctor diagnosing patients. With ID3, the doctor only asks yes/no questions ("Do you have a fever?"), panics when a test result is missing, and memorizes every quirk of past patients — even the ones that were flukes.
C4.5 is the experienced version of that doctor: she handles blood-pressure readings (continuous numbers), carries on when a lab report hasn't arrived yet (missing values), knows which follow-up questions actually matter (gain ratio), and — crucially — crosses out the parts of her decision flowchart that only fit the training patients but would mislead her on new ones (pruning).
From ID3 to C4.5: fixing four weaknesses
ID3 introduced a powerful idea: build a decision tree by recursively choosing the attribute that gives the most information gain — i.e., the question whose answer reduces the most uncertainty about the class. But ID3 had four critical limitations that C4.5 addressed one by one.
The foundation: entropy and information gain
Before we see C4.5's improvements, let's revisit the engine underneath. measures how "mixed" a set of examples is. A bag where every ball is red has zero entropy — no surprise at all. A bag with half red and half blue has maximum entropy — you're maximally uncertain about what you'll draw.
Information gain tells us how much a question reduces that surprise. If splitting on "Is it sunny?" separates the examples into pure groups, the gain is high. C4.5 inherits this from ID3 but then corrects a subtle flaw in how gain picks its questions.
Problem #1: gain ratio fixes the many-values bias
Information gain has a hidden bias: it favors attributes with many distinct values. Consider a "Patient ID" attribute — it has a unique value for every example, so splitting on it produces perfectly pure leaves (one example per leaf). Information gain would rank it first, even though it teaches nothing about the actual patterns.
C4.5 solves this by introducing gain ratio: divide the information gain by the split information of the attribute, which measures how evenly the attribute divides the data. An attribute that creates many tiny groups has high split information, which penalizes its score. Think of it as normalizing the grade: a test that spreads students across 100 buckets is not as informative per-bucket as a test that cleanly separates them into 2 meaningful groups.
Problem #2: splitting on continuous attributes
ID3 could only handle categorical attributes — "color = red / blue / green". But most real-world data includes measurements like temperature, blood pressure, or age. C4.5 handles this by converting a continuous attribute into a binary test: "Is temperature ≤ 28.5?"
The algorithm sorts the training examples by the continuous attribute, then evaluates every possible threshold between adjacent values with different class labels. The threshold with the highest gain ratio becomes the split point. This is like finding the best line to draw through a ruler to separate two groups — you try every position and keep the one that divides them most cleanly.
Problem #3: dealing with missing values
Real data is messy. A patient's blood test might not be back yet; a survey respondent might skip a question. ID3 had no strategy for this — it simply could not handle incomplete records.
C4.5 takes an elegant approach: when a value is missing, it sends a fraction of the example down every branch, weighted by how many known examples go each way. If 60% of known examples for attribute A go left and 40% go right, a missing-A example splits into a 0.6-weight copy going left and a 0.4-weight copy going right. This way, the example contributes proportionally to both sides rather than being discarded or guessed. It's like a weighted vote: the missing example votes in proportion to what the known data suggests.
Problem #4: pruning overfitted trees
A fully grown decision tree fits the training data perfectly — every path leads to a pure leaf. But perfection on training data is usually a sign of : the tree has memorized noise and quirks that won't repeat in new data. Think of a student who memorizes every practice exam answer-for-answer but can't solve a new problem.
C4.5 uses error-based pruning: after growing the full tree, it walks bottom-up and asks at every internal node, "Would replacing this entire subtree with a single leaf increase the estimated error on unseen data?" If yes, keep the subtree. If no, replace it with the majority-class leaf.
The estimated error uses the upper bound of a confidence interval on the training error rate. Even a node with zero training errors gets a nonzero estimated error, which prevents the algorithm from keeping branches that only happen to fit the training data. The default confidence level is 25%, and lowering it causes heavier pruning — smaller, more general trees.
From trees to rules: more compact, more interpretable
A decision tree path from root to leaf is essentially an if-then rule: "IF outlook = sunny AND humidity ≤ 75 THEN Play = yes." C4.5 converts the entire tree into such rules, then improves them through three steps:
Step 1 — Generalize each rule. Try removing conditions one at a time. If dropping a condition doesn't increase the estimated error, remove it. The rule becomes shorter and more general.
Step 2 — Group by class. Collect all rules that predict the same class. Use the minimum description length (MDL) principle to find the smallest subset that covers the training data accurately — discard redundant rules.
Step 3 — Order and default. Rank the class rule-sets by their estimated accuracy and assign a default class for anything not covered.
The resulting rule set is often significantly smaller than the original tree and can make different — sometimes better — predictions because rules from different branches can be individually pruned without affecting siblings.
The C4.5 algorithm step by step
The full C4.5 tree-building algorithm is a recursive divide-and-conquer procedure. At each node, it evaluates every attribute's gain ratio, picks the best one, splits the data, and recurses on each subset. After the full tree is built, it prunes bottom-up.
Simplified to show the idea — not the real implementation.
import numpy as np
from collections import Counter
def entropy(y, weights=None):
"""Weighted entropy of class labels."""
if weights is None:
weights = np.ones(len(y))
total = weights.sum()
if total == 0:
return 0.0
ent = 0.0
for c in set(y):
mask = (y == c)
p = weights[mask].sum() / total
if p > 0:
ent -= p * np.log2(p)
return ent
def gain_ratio(X, y, attr, weights):
"""C4.5's gain ratio = information gain / split info."""
total = weights.sum()
base_ent = entropy(y, weights)
gain = base_ent
split_info = 0.0
for val in set(X[:, attr]):
mask = (X[:, attr] == val)
w_sub = weights[mask]
frac = w_sub.sum() / total
gain -= frac * entropy(y[mask], w_sub)
if frac > 0:
split_info -= frac * np.log2(frac)
if split_info == 0:
return 0.0
return gain / split_info # the key C4.5 formula
def build_tree(X, y, weights, attrs):
"""Recursively build C4.5 tree (simplified)."""
# Base cases
if len(set(y)) == 1:
return {'leaf': y[0]}
if len(attrs) == 0:
return {'leaf': Counter(y).most_common(1)[0][0]}
# Pick best attribute by gain ratio
best = max(attrs, key=lambda a: gain_ratio(X, y, a, weights))
tree = {'attr': best, 'children': {}}
for val in set(X[:, best]):
mask = (X[:, best] == val)
remaining = [a for a in attrs if a != best]
tree['children'][val] = build_tree(
X[mask], y[mask], weights[mask], remaining
)
return tree
# After building, C4.5 prunes bottom-up using
# pessimistic error estimates (upper confidence bound).The complete C4.5 pipeline
Why C4.5 changed machine learning
1986
ID3
Quinlan's original algorithm. Categorical attributes only, no pruning, no missing value handling. Introduced the information gain criterion.
1993
C4.5
Gain ratio, continuous attributes, missing values, error-based pruning, and rule extraction. Became the gold standard for decision tree induction.
1998
C5.0 / See5
Commercial successor. Faster, uses less memory, supports boosting. The algorithm details remain proprietary.
2001
Random Forests
Breiman combined many decision trees with bagging and feature randomization. Each tree is a descendant of the C4.5 lineage, but the ensemble eliminates overfitting far more effectively than pruning alone.
2016
XGBoost / LightGBM
Gradient boosting frameworks that build trees sequentially, each correcting the previous one's errors. Dominated Kaggle competitions and industry applications.
C4.5 did not just build better trees — it established the entire methodology of training, pruning, and evaluating interpretable classifiers. The Random Forests you use today are ensembles of trees, each of which traces its lineage back through C4.5 to ID3.
CitationQuinlan, J. R.. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
Terms in this paper
- Decision Treeشجرة القرار الإحصائية
- Information Gainالكسب المعلوماتي
- Entropyالعشوائية الدلالية
- Gain Ratioنسبة الكسب
- Pruningتشذيب الشبكات العصبية
- Overfittingفرط التخصيص
- Missing Valuesالقيم المفقودة
- Classificationالتصنيف
- Ruleقاعدة