Implementations: Real Machine Learning Schemes (part 1: 6.1–6.2)
Open in the Padhaiko app6.1 Advanced Decision Trees: C4.5, numeric attributes, and pruning
While ID3 illustrates divide-and-conquer induction cleanly on toy nominal tables, real datasets contain continuous measurements, missing values, noise, and many-valued attributes. C4.5 (Quinlan, ) upgrades ID3 into a production-grade decision tree learner through four key mechanisms.
1. Gain Ratio (Correcting Multi-Valued Bias)
ID3's Information Gain favors attributes with many distinct outcomes (e.g., Transaction_ID), even when those outcomes hold zero predictive power. C4.5 normalizes Information Gain by the intrinsic entropy of the split itself:
SplitInfo and Gain Ratio (C4.5)
When attribute partitions dataset into subsets :
Because becomes large for high-cardinality attributes (like an ID with values, where ), penalizes excessive branching. To prevent tiny unbalanced splits (where artificially inflates the ratio), C4.5 restricts candidate selection to attributes whose is at least the average Information Gain across all tested attributes.
2. Numeric Attributes and Boundary Points
For a continuous numeric attribute , C4.5 considers binary threshold splits vs. :
- Sort the training instances by in ascending order: .
- Candidate split thresholds lie halfway between adjacent distinct values: .
- Boundary-Point Optimization (Fayyad & Irani): Information Gain can only achieve its maximum at a class boundary where consecutive sorted instances have different class labels. Thus, thresholds inside a run of identically labeled values can be skipped completely, cutting search cost dramatically.
3. Handling Missing Values in C4.5
- During splitting: Compute only on instances where is known, then scale down by the fraction of instances with known ().
- During partitioning & prediction: An instance with missing is not discarded; it is sent down all branches with fractional weight . At test time, predicted class probabilities from multiple leaves are combined using those fractional weights.
4. Tree Pruning: Pre-Pruning vs. Post-Pruning
Unpruned trees grow until every leaf is pure, memorizing training noise and overfitting.
| Aspect | Pre-Pruning (Online Stopping) | Post-Pruning (Grow-Then-Prune) |
|---|---|---|
| Mechanism | Stop splitting early using minimum leaf size, depth cap, or statistical significance test | Grow a full tree first, then prune unreliable branches bottom-up |
| Main Risk | Horizon effect: misses valuable two-attribute interactions when neither attribute looks strong alone | Higher initial training time to grow the full tree |
| Practical Preference | Rarely used alone except for speed on huge datasets | Preferred in C4.5 / CART because full interaction structure is explored first |
C4.5 Post-Pruning Operations and Error Estimation
- Subtree Replacement: Replace an internal node and its entire subtree by a single leaf predicting the majority class whenever estimated generalization error decreases or stays equal (bottom-up).
- Subtree Raising: Replace an internal node by its most heavily populated child subtree (reclassifying instances from the discarded sibling branches); more expensive and used selectively in C4.5.
- Reduced-Error Pruning (REP): Evaluates each prune candidate directly on a held-out validation (pruning) set. Simple and accurate, but reduces the data available for tree growing.
- Pessimistic Error Pruning (C4.5 Default): Uses training data alone by treating training errors out of instances at a node as a binomial sample and taking a pessimistic upper confidence bound (default confidence , corresponding to upper ). Using the normal approximation with continuity correction:
A subtree is replaced by a leaf whenever the leaf's pessimistic error the weighted sum of its children's pessimistic errors.
6.2 Classification Rules: RIPPER algorithm and partial decision trees
Covering algorithms like PRISM generate -pure rules on the training set, which severely overfits noisy datasets. Real-world rule learners fix this through incremental pruning (RIPPER) and partial trees (PART).
1. RIPPER (Repeated Incremental Pruning to Produce Error Reduction)
Developed by William Cohen () as an improvement over IREP (Incremental Reduced-Error Pruning), RIPPER learns rules one class at a time (typically ordered from least frequent class to most frequent, leaving the majority class as the final DEFAULT rule).
Core Loop: Grow-Then-Prune One Rule at a Time
For the current target class :
- Split: Partition remaining uncovered data randomly into a Growing set () and a Pruning set ().
- Grow: Starting from an empty rule
IF true THEN class = C, greedily add attribute-value tests (or / ) maximizing FOIL's information gain:
where are positive/negative counts covered before adding the test and are counts covered after adding it. Stop growing when (pure on growing set) or no positive gain remains.
- Prune Immediately: Evaluate candidate suffixes of the rule (deleting conditions from the end backward) on the Pruning set, maximizing the pruning metric:
Prune immediately before learning the next rule so subsequent rules adapt to the actual covered examples!
- Stopping Criterion (MDL): Stop adding rules for class when the rule set achieves positive errors, the new rule's error rate on the pruning set exceeds , or its Minimum Description Length (MDL) exceeds the smallest MDL seen so far for this class by more than .
- Global Optimization ( Passes): For each rule in the learned rule set, construct two alternatives—a replacement rule (grown & pruned from scratch) and a revised rule (further grown & pruned starting from )—and keep whichever of minimizes total MDL over the entire dataset.
2. Partial Decision Trees (PART)
PART (Frank & Witten, ) avoids RIPPER's complex global optimization passes by combining divide-and-conquer (C4.5) with separate-and-conquer (covering):
while uncovered training instances remain:
build a PARTIAL C4.5 decision tree on the current uncovered instances:
expand nodes using C4.5 Gain Ratio, but prune subtrees bottom-up
as soon as all children of an internal node are unexpanded or pruned leaves
(subtree replacement using C4.5 pessimistic error test)
select the leaf in the partial tree that covers the LARGEST number of instances
convert the root-to-leaf path into one classification rule
discard the entire partial tree!
remove all instances covered by this rule and repeat| Aspect | RIPPER | PART |
|---|---|---|
| Rule Construction | Grows single rule via FOIL gain + IREP pruning on split | Builds a partial C4.5 tree and extracts its best-covering leaf |
| Global Post-Optimization | Requires passes of MDL replacement/revision optimization | None needed—tree pruning already prevents hasty over-specialization |
| Rule Quality / Speed | Very compact rule sets; fast on huge noisy datasets | Slightly larger rule sets, very clean implementation, high accuracy |
Worked Examples
Computing Gain Ratio and Boundary Thresholds in C4.5
- A dataset of instances has
YesandNolabels (). AttributeRegionpartitions into three branches:North( instances:Yes,No)South( instances:Yes,No)East( instances:Yes,No) Compute , , and .
- A numeric attribute
Scorehas sorted training values and labels: . List only the valid boundary thresholds that C4.5 needs to evaluate.
Computing branch entropies and Information Gain for Region:
North( instances:Yes,No): .South( instances:Yes,No): .East( instances:Yes,No): .
Computing and :
Identifying C4.5 boundary thresholds for Score: Sorted pairs: . Class changes occur between:
- and
- and
- and
Only thresholds () need testing instead of all midpoints.
- , , .
- Candidate boundary thresholds for
Score: and .
Pessimistic Error Pruning Decision and RIPPER Pruning Metric
- Using C4.5's pessimistic upper error bound () at a leaf covering instances with errors (), compute the pessimistic error rate and the pessimistic expected number of errors .
- During RIPPER rule pruning on a pruning set, a grown rule
IF A=1 AND B=2 AND C=3 THEN Yescovers instances. DroppingC=3changes pruning coverage to . Using the pruning score , should RIPPER prune conditionC=3?
Part 1 — Computing C4.5 pessimistic error bound (): With :
Notice C4.5 adds a pessimistic penalty ( estimated errors vs. observed).
Part 2 — Evaluating RIPPER pruning score :
- Before pruning (
A=1 AND B=2 AND C=3): . - After dropping
C=3(A=1 AND B=2): .
Because , dropping C=3 lowers the pruning score, so RIPPER retains C=3.
- Pessimistic error rate ( pessimistic errors out of ).
- RIPPER keeps
C=3because dropping it lowers from to .
Exercises
Practice Exercises — C4.5, Pruning, RIPPER, and PART
Explain why C4.5 replaces ID3's Information Gain with Gain Ratio, and describe the safeguard C4.5 uses when is very small. If an attribute achieves while splitting instances evenly into branches of size , compute and .
Motivation and Safeguard for Gain Ratio: Information Gain prefers attributes with many distinct outcomes (e.g., unique IDs) because many small branches appear purer. Gain Ratio divides by to penalize excessive branching. Because an extremely skewed split (say instance vs. ) makes tiny and artificially inflates , C4.5 only considers attributes whose raw meets or exceeds the average Gain of all candidate attributes.
Computing and ( branches of ):
Gain Ratio corrects Information Gain's bias toward many-valued attributes, safeguarded by filtering out below-average-Gain attributes. For equal branches of , and .
Distinguish between subtree replacement and subtree raising in C4.5 post-pruning, and compare Reduced-Error Pruning (REP) with Pessimistic Error Pruning.
Subtree Replacement vs. Subtree Raising:
- Subtree Replacement: Replaces an entire internal node and all its descendants with a single leaf predicting the majority class if estimated error improves or does not increase.
- Subtree Raising: Deletes an internal node and promotes its most heavily populated child subtree up into its position, re-routing instances from the other siblings through the raised subtree.
Reduced-Error Pruning vs. Pessimistic Error Pruning:
- Reduced-Error Pruning (REP) tests prune candidates directly on an independent held-out validation set (simple, unbiased, but shrinks the training sample).
- Pessimistic Error Pruning requires no separate validation set; it adds a continuity-corrected binomial upper-confidence penalty to the training error at each node and prunes whenever the leaf's pessimistic error is no worse than its subtree's weighted pessimistic error.
Subtree replacement collapses a subtree into a leaf, whereas subtree raising promotes the largest child subtree up one level. REP uses a held-out validation set; pessimistic pruning uses an upper confidence bound on training error without splitting off validation data.
Explain how C4.5 handles a missing attribute value during both tree construction and test-time prediction. Suppose a test instance reaches a node testing Income with a missing value, where training counts on the two branches are (Low) and (High). If the Low subtree predicts P(Approve) = 0.60 and the High subtree predicts P(Approve) = 0.20, compute the final predicted probability P(Approve).
C4.5 Missing-Value Handling: During training, Gain is computed on known rows and scaled down by the fraction of known rows; rows with missing values pass down all branches with fractional weights proportional to branch frequencies. During testing, the same fractional routing splits the query down every branch and takes a weighted average of leaf class probabilities.
Computing Weighted Prediction: Branch weights are and :
C4.5 routes missing-value instances fractionally down every branch proportional to training branch counts. Here (predicting Reject).
Describe the four stages of the RIPPER algorithm (grow, prune, MDL stopping, and global optimization) and explain why immediate incremental pruning outperforms pruning a complete rule set only at the end.
Four Stages of RIPPER:
- Grow: On of remaining data, greedily add tests maximizing FOIL information gain until pure.
- Prune: Immediately prune trailing conditions on the pruning set maximizing .
- Stop (MDL): Stop adding rules for the class when MDL length jumps by or error .
- Global Optimization: Run post-passes building a replacement rule and revised rule for each rule and keeping whichever minimizes full-dataset MDL.
Why Immediate Pruning Matters: If an unpruned overfitted rule stays unpruned while subsequent rules are learned, it covers too few instances and leaves noisy gaps that force later rules to compensate awkwardly. Pruning immediately lets subsequent rules focus cleanly on the truly uncovered examples.
RIPPER grows rules via FOIL gain, prunes immediately on a split, stops using an MDL -bit criterion, and refines via global MDL replacement/revision passes. Immediate pruning prevents over-specific early rules from distorting the remaining training set for later rules.
How does the PART algorithm extract rules without performing RIPPER's global post-optimization? Trace its core loop in four clear steps.
Core Idea of PART: PART observes that a pruned C4.5 decision tree does not suffer from the greedy over-specialization of unpruned covering rules—yet building a whole tree just to extract one rule seems wasteful. PART resolves this by building only a partial decision tree per rule.
Four-Step PART Loop:
- Build a partial C4.5 tree on remaining instances, expanding nodes using Gain Ratio and pruning subtrees via subtree replacement as soon as their subtrees are complete—stopping expansion once the best-covering pruned leaf is isolated.
- Extract the root-to-leaf path of the leaf covering the largest number of instances as a single
IF-THENrule. - Discard the rest of the partial tree.
- Remove all training instances covered by the extracted rule and repeat until no uncovered instances remain.
PART extracts rules by repeatedly building a pruned partial C4.5 tree on uncovered instances, converting the path to the largest-coverage leaf into one rule, discarding the rest of the tree, removing covered rows, and repeating—achieving RIPPER-level accuracy without global optimization.