CN2 and RIPPER algorithms

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.