Rule-Based Classification

Rule-Based Classification

Rule-based classifiers use a set of IF-THEN rules to classify tuples; they are the most human-interpretable model family (used in expert systems, fraud detection, credit scoring and clinical decision support).

1. Rule Form and Terminology

where the consequent $y$ is a class label. Conditions are of the form $A , {=,
e, <, >, \le, \ge} , v$ (categorical equality or numeric range).

Term	Meaning
Coverage / support of a rule	Fraction of tuples in $D$ that satisfy the rule's antecedent: $|X|/|D|$
Accuracy / confidence of a rule	Fraction of covered tuples that have the rule's class: $|X \cap y|/|X|$
Rule set coverage	Fraction of tuples covered by at least one rule
Mutual exclusivity	No tuple is covered by more than one rule (ideal but rare)

Conflict resolution when rules overlap

1. Voting — count rules predicting each class; the majority wins (ties broken arbitrarily or by rule accuracy).
2. Rule ordering / decision list — rules are ranked; the class of the highest-priority matching rule is chosen.
3. Class-based ordering — rules are grouped by class; the class whose rules come first wins (used in RIPPER and C4.5rules).

2. From a Decision Tree to Rules

Each root-to-leaf path becomes a rule (see decision tree notes); trees → rules gives an equivalent but more flexible representation, because conditions can be pruned independently.

 Decision tree path:  age=youth -> student=yes -> [buys=yes]
 Rule:                IF age=youth AND student=yes THEN buys_computer=yes

Rule pruning (C4.5rules): remove a precondition if removing it does not reduce estimated accuracy; then eliminate duplicate/dominated rules (keep the simpler rule with lower error; ties → prefer the more general rule).

3. Sequential Covering Algorithm (the classic rule-learning framework)

SequentialCovering(Target_class, Attributes, Data):
  1. RuleSet = {}                        (empty)
  2. repeat
       Rule = LearnOneRule(Data, Attributes, Target_class)
       remove tuples covered by Rule from Data
       RuleSet = RuleSet + Rule
     until the termination condition (e.g. accuracy of RuleSet >= threshold,
           or no more positive tuples)
  3. return RuleSet

LearnOneRule performs a greedy, beam search: start with the empty antecedent IF {} (covers everything, accuracy = class prior) and add conditions one at a time, keeping the best k candidates (beam width $k$) using a measure such as:

where $P_1, N_1$ = positive/negative tuples covered after adding the condition, and $P_0, N_0$ = before. FOIL is a pure FOIL-gain learner, RIPPER (FOIL + IREP) adds incremental reduced-error pruning.

Rule growth may also use accuracy: $\text{acc} = \frac{|P_1|}{|P_1|+|N_1|}$ — but accuracy alone is weak when positives are rare, hence FoilGain (which also rewards coverage of positive tuples).

4. RIPPER (Repeated Incremental Pruning to Produce Error Reduction)

1. Order the classes by increasing frequency (rare classes first → one-vs-rest).
2. Grow a rule by adding conditions that maximise FoilGain until it covers no negative tuple (or hits a length limit).
3. Prune using the incremental reduced error pruning (IREP) rule: delete the last condition added, computing

4. Repeat to obtain a rule set covering the class; then optimise each rule — for every rule, grow two alternatives (replacing the rule, or revising by adding more conditions), prune, and keep the one with the lowest error.
5. Stop when the description length of the rule set exceeds a bound.

Advantage: scales to large noisy datasets; produces compact, ordered rule sets.

5. Associative Classification (RIPPER's cousin)

Mine class association rules (CARs) with Apriori/FP-growth, then use the subset of frequent rules with the highest confidence as a classifier (detailed under Associative Classification).

6. Rule Quality Measures

Measure	Formula	Note
Support / coverage	$\frac{|X|}{|D|}$ or $\frac{|X\cap y|}{|D|}$	Frequency
Confidence / accuracy	$\frac{|X\cap y|}{|X|}$	Reliability
Laplace accuracy	$\frac{|X\cap y|+1}{|X|+k}$ ($k$ = #classes)	Corrected for small counts
Foil gain	as above	Favours coverage
$m$-estimate	$\frac{|X\cap y|+m\,p}{|X|+m}$ ($p$ = prior of $y$)	Smoothed
Lift	$\frac{conf}{P(y)}$	Interest

Example rule: IF income=high AND student=yes THEN buys_computer=yes

• Coverage = 2/14 = 14.3%, accuracy = 2/2 = 100%, Laplace = (2+1)/(2+2) = 75%.

7. Advantages and Limitations

Advantages

• Rule sets are easy to interpret, verify and modify by domain experts; a single rule can be read as an independent piece of knowledge.
• Can express disjunctions of conjunctions; order-independent (unlike a tree's fixed splits).
• Handles missing values (a condition on a missing attribute simply fails) and mixed attribute types.
• Easy to weight/prioritise rules and integrate domain knowledge and cost information; can use only a subset of rules (partial matching) for explanation.

Limitations

• Greedy separate-and-conquer → overlapping, redundant or conflicting rules; may cause overfitting if not pruned.
• Efficiency: rule induction can be slow (many candidate rules); prone to class imbalance (rare classes are learned first or ignored).
• Rule conflicts must be resolved (unordered rule sets need voting/priority rules).
• Performance is usually slightly lower than ensembles/SVM, and strongly dependent on the pruning and stopping criteria.

8. Exam Points

• Explain the sequential covering algorithm with pseudo-code and a worked rule — 10 marks (frequent).
• Define coverage, accuracy and FoilGain; compute them for a given rule — 5-7 marks.
• Explain RIPPER's grow-and-prune cycle (with IRED's $v=(p-n)/(p+n)$) — 5-7 marks.
• Compare rule-based classification with decision tree induction — 5 marks.