Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

    1. Input: dataset D, stopping criteria (min_coverage, max_rules).
    2. R := empty list.
    3. 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).
    4. 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

  1. Write the formula for rule confidence in terms of counts.
  2. In sequential covering, after adding a rule you usually remove which examples from training? (positive only, or all covered?)
  3. 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?