---
title: "CN2 and RIPPER algorithms"
subject: "Data Mining"
chapter: 3
key: "semester_7/data_mining:cn2-ripper"
source: https://www.bctengineer.com/q/semester_7/data_mining/cn2-ripper
site: BCT Engineering
---

# CN2 and RIPPER algorithms

Data Mining · Chapter 3: Classification

- Asked in: year not given
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/cn2-ripper
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-3

## Question

Describe CN2 and RIPPER algorithm for rule growing. What are the measures for Rule Evaluation?

## Short answer

CN2 grows rules by beam search, evaluating specializations with entropy and significance, producing an ordered list. RIPPER greedily adds conditions maximizing FOIL's information gain, prunes on a validation set, and optimizes the rule set. Evaluation measures include accuracy, Laplace estimate, m-estimate, FOIL's gain, and likelihood ratio statistic.

## Answer

Both algorithms learn rules by sequential covering: grow a rule for one class, remove the covered records, and repeat.

#### CN2
CN2 (Clark and Niblett) produces an ordered rule list (or unordered rules).
1. Start with the most general rule `IF true THEN class`.
2. Grow the rule by **beam search**: keep the best k (beam width) candidate rules; refine each by adding one attribute test (a "complex").
3. Evaluate candidates by **entropy** (or Laplace accuracy); choose the one with the lowest entropy that is statistically significant (likelihood ratio test).
4. Output the rule with the majority class of covered records, delete those records, repeat until no good rule is found; add a default rule.

#### RIPPER
RIPPER (Repeated Incremental Pruning to Produce Error Reduction, Cohen) works for two-class and multi-class data, ordering classes by frequency and learning from the least frequent.
1. **Grow** a rule greedily from an empty rule, adding conditions with the best **FOIL's information gain**, until it covers no negative records.
2. **Prune** the rule on a validation part of the data (delete trailing conditions to improve v = (p − n)/(p + n)).
3. Add the rule; remove covered records; stop when the **description length** (MDL) of the rule set grows by more than a limit, or the error exceeds 50%.
4. **Optimise** the rule set by revising or replacing each rule and keeping the better version.

#### Measures for rule evaluation
- **Accuracy** = n_correct/n_covers and **coverage** = n_covers/|D|.
- **Laplace** = (n_correct + 1)/(n_covers + k) for k classes.
- **m-estimate** = (n_correct + k·p)/(n_covers + k) with prior p.
- **FOIL's information gain** = p₁ (log₂ p₁/(p₁ + n₁) − log₂ p₀/(p₀ + n₀)), where p₀, n₀ are positive and negative records covered before, and p₁, n₁ after, adding the condition.
- **Likelihood ratio** statistic R = 2 Σ fᵢ log(fᵢ/eᵢ), used by CN2 for significance.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does CN2 grow rules?
   A. Greedy search keeping only one rule using FOIL gain
   B. Beam search keeping the best k candidate rules, refining each by one test
   C. Exhaustive search over all rules
   D. Bottom-up generalisation of one record
   Answer: B. CN2 uses beam search with width k. (Key point: CN2 search)

2. Which measure does RIPPER use to choose conditions when growing a rule?
   A. FOIL's information gain
   B. Gini index
   C. Laplace accuracy only
   D. Likelihood ratio
   Answer: A. RIPPER adds the condition with best FOIL's information gain. (Key point: RIPPER gain)

3. What does RIPPER do after growing a rule?
   A. Adds more conditions until coverage is 100%
   B. Discards it and restarts
   C. Prunes it on a validation set by deleting trailing conditions
   D. Converts it into a tree
   Answer: C. Pruning improves v = (p-n)/(p+n). (Key point: RIPPER pruning)

4. For k classes, the Laplace measure of a rule is:
   A. n_correct/n_covers
   B. (n_correct + k)/(n_covers + 1)
   C. n_covers/|D|
   D. (n_correct + 1)/(n_covers + k)
   Answer: D. Laplace adds 1 to the correct count and k to the covered count. (Key point: Laplace measure)

## Related in Data Mining

- [Rule based classifier; coverage and accuracy](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Arule-based-classifier-measures) — Data Mining, chapter 3
- [Sequential covering for rule induction](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Asequential-covering) — Data Mining, chapter 3

## Related in other subjects

- [Data types and classification of algorithms](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-types-classify-algorithms) — Data Structure and Algorithm, chapter 1
- [Measures of efficiency with standard curves](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aefficiency-measures-curve) — Data Structure and Algorithm, chapter 9
- [DDA versus Bresenham line algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Adda-vs-bresenham-line) — Computer Graphics, chapter 2, asked 6×
- [Associative mapping and replacement algorithms](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassociative-mapping) — Computer Organization and Architecture, chapter 6, asked 2×