What is the C4.5 Algorithm and How Does It Work?

C4.5, developed by Ross Quinlan as a direct successor to his earlier ID3 algorithm, builds a decision tree the same basic way any decision-tree algorithm does: at each node, score every candidate attribute using an attribute selection measure and split on whichever one scores best, repeating recursively until a stopping condition is reached. Entropy and Information Gain — the specific scoring formulas involved — are covered with a full hand-verified worked example in the lesson on attribute selection measures, and pre-pruning versus post-pruning in general are covered in the lesson on tree pruning in data mining. This lesson covers the one thing C4.5 specifically added beyond both of those: Gain Ratio, and exactly what problem with plain Information Gain it was designed to fix.

The Problem Gain Ratio Was Built to Solve

Information Gain, as computed in the lesson on attribute selection measures, has a specific, serious flaw: it's biased toward attributes with many distinct values, regardless of whether those values actually generalize to new data. The clearest illustration is an attribute like Customer ID, where every single record has a different value. Take a 100-record dataset with the same class balance used in the lesson on attribute selection measures (60 records labeled Yes, 40 labeled No, giving a root entropy of 0.9710), split two different ways:

Split on Weather (3 groups: 40/30/30 records, same proportions as the worked example
in the lesson on attribute selection measures):
  Information Gain(Weather) = 0.3710
Split on Customer ID (100 groups of exactly 1 record each):
  Every subset is perfectly pure (a single record has no impurity to measure)
  Weighted entropy after split = 0
  Information Gain(Customer ID) = Entropy(root) - 0 = 0.9710 - 0 = 0.9710

By raw Information Gain alone, Customer ID scores nearly three times higher than Weather (0.9710 versus 0.3710) — and a tree-building algorithm using Information Gain alone would confidently pick Customer ID as the very first split. This is a completely useless choice in practice: a tree that splits on customer ID perfectly "classifies" every record in the training set (each ends up alone in its own leaf), while learning absolutely nothing that would apply to a customer ID it hasn't seen before.

How Gain Ratio Corrects This

Gain Ratio divides Information Gain by Split Information — a penalty term that measures how much the attribute itself fragments the dataset, independent of the target class entirely:

Gain Ratio(D, A) = Information Gain(D, A) / Split Information(D, A)
Split Information(D, A) = - sum over each value v of A of [ (|Dv|/|D|) x log2(|Dv|/|D|) ]

Computing Split Information for both attributes:

Split Information(Weather) = -(0.4 x log2(0.4)) - (0.3 x log2(0.3)) - (0.3 x log2(0.3))
                            = -(0.4 x -1.3219) - (0.3 x -1.7370) - (0.3 x -1.7370)
                            = 0.5288 + 0.5211 + 0.5211 = 1.5710
Split Information(Customer ID) = -100 x [ (1/100) x log2(1/100) ]
                                = -log2(1/100) = log2(100) ≈ 6.6439

An attribute that splits the data into many small groups (like Customer ID, with 100 groups of 1) has much higher Split Information than one that splits it into a few larger groups (like Weather, with 3 groups) — which is exactly the penalty needed:

Gain Ratio(Weather)     = 0.3710 / 1.5710 ≈ 0.236
Gain Ratio(Customer ID) = 0.9710 / 6.6439 ≈ 0.146

Under Gain Ratio, Weather (0.236) now correctly outranks Customer ID (0.146) — the exact reversal of what raw Information Gain concluded, and the reversal that actually matches which attribute produces a generalizable split. This is C4.5's specific, well-documented improvement over ID3, which used raw Information Gain and was consequently vulnerable to exactly this bias.

C4.5's Own Pruning Approach

While the general pre-pruning-versus-post-pruning distinction and CART's cost-complexity pruning are covered in the lesson on tree pruning in data mining, C4.5 specifically uses reduced-error pruning together with rule post-pruning: after building the full tree, it converts each root-to-leaf path into an IF-THEN rule (the same rule format covered in the lesson on rule-based classification in data mining), then simplifies each rule independently by removing conditions that don't reduce its estimated error on held-out data. Pruning at the rule level rather than the tree level lets C4.5 remove a condition from one rule without being forced to remove the entire branch it came from, which can preserve useful structure a strict tree-pruning approach would have discarded wholesale.

Handling Continuous Attributes

One further practical detail worth noting: unlike ID3, which only handles categorical attributes directly, C4.5 handles continuous attributes by testing candidate threshold splits (Age <= 30 vs. Age > 30) and choosing whichever threshold, combined with the resulting Gain Ratio, scores best — evaluating the attribute as if it were being converted into a two-value categorical split at the optimal cut point, rather than requiring the numeric attribute to be discretized into bins beforehand.