Rule-based classification
Rule-based classification builds human-readable if–then rules from labeled data and is used in expert systems, fast interpretable models, and as a post-processing step for other learners.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Rule-based classification produces human-readable models: sets of IF–THEN rules that map attribute tests to a class. Engineers use rule sets for explainable decision logic (fault diagnosis, credit rules, simple classifiers on edge devices) and as a compact form of a learned model that can be audited and edited.
Key ideas
Start from first principles. We have a dataset D of labelled examples. Each example is (x, y) where x is a vector of attribute values and y is a class label.
Classification rule: A statement of the form IF antecedent THEN consequent, where the antecedent is a conjunction of one or more attribute tests (e.g. Age > 30 AND Income = High) and the consequent is a class label (e.g. Class = Good). Formal notation: a rule r is written as A -> y, where A is the set (conjunction) of tests and y is a class.
Antecedent (coverage set): For a rule r: A -> y, the coverage is the set of examples in D whose attributes satisfy A. Denote n(A) the number of examples satisfying A and n(A,y) the number of examples satisfying A and having label y.
Support: The support of rule A -> y is the fraction (or count) of examples that satisfy both A and y. As a proportion: support(A -> y) = n(A,y) / |D|. (Support measures how common the rule is in D.)
Confidence: The confidence of rule A -> y is the conditional probability estimate that y holds given A: confidence(A -> y) = n(A,y) / n(A). (It estimates P(y | A) under the i.i.d. sampling assumption.)
Accuracy: For rules, accuracy often means the same as confidence (proportion of covered examples that are correctly predicted). If a rule predicts class y for its coverage set, accuracy = n(A,y) / n(A).
Coverage (in counts): n(A) — the number of examples covered by antecedent A. Do not confuse with support which is n(A,y)/|D|.
Precision, recall, F1: When viewing the class y as positive, precision = n(A,y) / n(A) (same as confidence), recall = n(A,y) / n(y) where n(y) is the total positives in D, and F1 = 2·precision·recall / (precision + recall).
Default rule: A fallback prediction made when no other rule applies. Typical default: predict the majority class of remaining examples.
Rule set vs ordered rules: An unordered rule set means all rules are considered and conflicts resolved (e.g., by voting). An ordered (sequential) rule list means rules are considered top-to-bottom: the first matching rule fires and later rules are ignored for that example.
Sequential-covering (learn-one-rule-at-a-time): A common approach to build an ordered rule list. Pseudocode (exact statement universities expect):
- Input: dataset D, stopping criteria (min_coverage, max_rules).
- R := empty list.
- While there remain positive examples in D and |R| < max_rules: a. Learn a high-quality rule r that predicts the positive class using a rule-grow + prune procedure (maximize some heuristic like information gain or FOIL-gain, subject to min_coverage). b. Add r to R. c. Remove from D all examples covered by r (or optionally only the positive examples covered).
- Return R plus a default rule for remaining examples.
Assumptions: training examples are i.i.d.; attributes are discrete or discretised; rule quality is measured by a consistent heuristic.
Rule growing and pruning: Growing starts from the empty antecedent and greedily adds tests that improve a heuristic (e.g., information gain or confidence increase). Pre-pruning stops growth early (min support), post-pruning simplifies a fully-grown rule by removing tests that do not reduce performance on a validation set. Explainability and overfitting control depend on pruning.
Evaluation heuristics: Common heuristics are support, confidence, information gain (relative improvement in class purity when adding a test), and Laplace estimate for small counts. The statistical interpretation: confidence estimates P(y|A). For small n(A) a corrected estimate (Laplace) is used to avoid over-optimistic confidence.
How to handle continuous attributes: either discretise in a preprocessing step (see the subject Data reduction and discretisation) or generate threshold tests Age > t during rule growing (choose t by searching candidate splits).
Relation to other topics: Rules can be extracted from decision trees (convert each root-to-leaf path into a rule), from association rules (class association rules), or learned directly (CN2, RIPPER family). See also Decision tree induction and Frequent itemsets and association rules.
Diagram to draw for exams: Draw a rectangle labelled D (whole dataset). Inside draw two overlapping circles: A (examples satisfying antecedent A) and C (examples with class y). Label the intersection n(A,y), the part of A outside intersection n(A)–n(A,y), and the part of C outside intersection n(y)–n(A,y). This Venn-like diagram illustrates support and confidence.
Formulas
support(A -> y) = n(A,y) / |D| — n(A,y): count of examples that satisfy A and have class y; |D|: total examples. Unit: dimensionless fraction. Applies to rule frequency.
confidence(A -> y) = n(A,y) / n(A) — n(A): count of examples satisfying A. Unit: dimensionless probability estimate. Applies as empirical estimate of P(y | A).
coverage(A) = n(A) — count of examples covered by antecedent A. Unit: examples (count). Applies when choosing min_coverage thresholds.
precision = n(A,y) / n(A) — when y considered positive; same as confidence. Unit: dimensionless.
recall = n(A,y) / n(y) — n(y): total examples of class y in D. Unit: dimensionless.
F1 = 2 * precision * recall / (precision + recall) — harmonic mean. Unit: dimensionless.
Laplace(A -> y) = (n(A,y) + 1) / (n(A) + k) — k: number of classes. Unit: dimensionless. Use as a smoothed confidence estimate for small counts.
error_rate(r) = (n(A) - n(A,y)) / n(A) — fraction of covered examples misclassified by rule r. Unit: dimensionless.
Information-gain like heuristic when adding test t to antecedent A (binary split of the covered set A):
gain = H(A) - [ (n(A and t)/n(A)) * H(A and t) + (n(A and not t)/n(A)) * H(A and not t) ] where H(.) is class entropy on the indicated set and H(S) = - sum_c p_c log2 p_c. Apply when evaluating split improvement; note that dropping the (A and not t) term is no longer information gain.
Worked examples
Example 1 — small labelled dataset and sequential covering (manual trace)
Dataset D (8 examples): attributes A (High/Low), B (Yes/No), Class ∈ {Pass, Fail}. 1: A=High, B=Yes => Pass 2: A=High, B=No => Pass 3: A=Low, B=Yes => Pass 4: A=Low, B=No => Fail 5: A=High, B=Yes => Pass 6: A=Low, B=Yes => Pass 7: A=High, B=No => Pass 8: A=Low, B=No => Fail
Step 1: counts: |D| = 8. Total Pass n(Pass) = 6 (examples 1,2,3,5,6,7). Total Fail = 2 (4,8).
Consider candidate rule r1: IF A = High THEN Pass.
- n(A=High) = examples 1,2,5,7 => n(A) = 4.
- n(A=High, Pass) = 4 => confidence = 4/4 = 1.0.
- support = 4/8 = 0.5. This is a strong rule. Add r1.
Remove covered examples (sequential covering): remove 1,2,5,7. Remaining examples: 3 (Low,Yes,Pass), 4 (Low,No,Fail), 6 (Low,Yes,Pass), 8 (Low,No,Fail).
Step 2: learn r2. Candidate: IF B = Yes THEN Pass.
- Among remaining, B=Yes are 3 and 6 => n(A)=2, both Pass => confidence = 1.0, support overall = 2/8 = 0.25. Add r2.
Remove covered 3,6. Remaining 4 and 8: both Fail. Default rule: ELSE predict Fail.
Final ordered rules: (1) IF A=High THEN Pass; (2) IF B=Yes THEN Pass; (3) ELSE Fail.
Check: all 8 examples are correctly classified. This demonstrates sequential covering, coverage removal, and default rule.
Example 2 — Laplace smoothing and numeric check
Consider a rule r that covers n(A) = 4 examples, all predicted as class Pass so raw confidence = 4/4 = 1.0. But classes k = 2. Laplace estimate = (4 + 1) / (4 + 2) = 5/6 ≈ 0.8333. Explain: Laplace reduces over-optimistic confidence for small samples.
Common mistakes
- Forgetting to remove covered examples in sequential covering (or removing both positive and negative examples incorrectly).
- Assuming rule sets are inherently consistent: unordered rules can conflict — you must specify conflict resolution or use ordered rules.
- Interpreting confidence P(y|A) as P(A|y) — conditional probabilities are not symmetric.
- Not validating pruned rules on a separate validation set (post-pruning requires validation data or cross-validation).
For your exam
Question types you will see: definitions (define rule, antecedent, support, confidence), short notes (sequential covering, pruning), derivations (derive formula for confidence as conditional probability), numericals (compute support/confidence/F1, trace a rule learner on small data), pseudocode (write the sequential-covering algorithm or grow-and-prune steps), diagram (draw Venn sets for antecedent and class).
What a full-marks answer includes:
- For definitions: state the term and give the formal formula (e.g., confidence = n(A,y)/n(A)).
- For algorithm questions: give clear pseudocode, stopping criteria, and complexity remarks (e.g., growing each rule is O(#attributes × #candidate tests × |D|) per rule) and assumptions.
- For numericals: show counts, compute support and confidence step by step, show any smoothing used, and state final rule set and default rule.
- For explanations: mention how continuous attributes are handled (discretisation or threshold tests) and how pruning prevents overfitting.
Quick check
- Write the formula for rule confidence in terms of counts.
- In sequential covering, after adding a rule you usually remove which examples from training? (positive only, or all covered?)
- Laplace smoothing for a rule with n(A,y)=2, n(A)=3, k=3 classes: what is the Laplace estimate?
Answers: (1) confidence = n(A,y) / n(A). (2) Usually remove the positive examples covered (so subsequent rules focus on remaining positives); some variants remove all covered examples. (3) (2+1)/(3+3) = 3/6 = 0.5.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?