—

Data Mining

Rule-Based Classification

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Decision trees: structure, splits, and rule extraction — covered in Lecture 7 (Decision Trees)
Entropy and information gain — covered in Lecture 7 (Decision Trees)
Classification accuracy and performance measures — covered in Lecture 6 (Classification, Performance Measures, and Overfitting)
Rule-based classification overview — covered in Lecture 5 (Data Reduction, Discretization, and Classification)
Forward selection and backward elimination — covered in Lecture 5 (Data Reduction, Discretization, and Classification)

Rule-based classification is a classification scheme built from simple if-then rules: we write a set of rules and use those rules to predict the class label of a record. This lecture walks the whole story in order: what a rule is and when it fires, the two measures of rule quality (coverage and accuracy), the two ways to build a rule set (directly from data, or extracted from a decision tree), the two properties tree rules get for free, what rule simplification breaks, how conflicts are resolved, the default-rule fallback, and the direct-method algorithms (sequential covering, CN2, RIPPER) that grow rules one condition at a time. Everything covered here is part of the exam syllabus. The exam will contain good theoretical questions and numerical questions — expect logical questions and some numericals that let you visualize the ideas and solve them properly, not generic "what is data mining" questions.

Exam note: The whole lecture is examinable. Expect two flavors of question: theoretical questions (explain mutual exclusion, exhaustiveness, the conflict resolution strategies, the default rule) and numerical questions (compute coverage $n_{co v er} /∣ D ∣$ and accuracy $n_{cor r ec t} / n_{co v er}$ for a rule on a given dataset). Before the exam, redo the buys-computer numbers in Section 8.2 by hand.

8.1 What Is Rule-Based Classification

8.1.1 The Core Idea: Rules That Predict

In simple words, rule-based classification means we write rules so that we can do some prediction. We classify records by putting some if-then rules over them: if the condition is true, then there is a conclusion, and the conclusion is typically the class level. So the whole scheme reduces to a very simple shape: for a given set of attribute values, the rule tells you the class level.

Hook. How can a machine give a prediction that a human can read, check, and challenge in one line? Because each prediction is an if-then statement: "if the applicant is young and a student, then they will buy a computer." No black box, no hidden weights — just conditions and a conclusion.

Intuition. Think of a security guard's entry checklist at a gate: each line on the checklist is a condition ("badge shown?", "name on the list?"), and only when every line checks out does the guard wave someone through to the inside — the class. A rule works the same way: its conditions are the checklist, and the conclusion is the gate the tuple passes through. The analogy breaks in one place: a guard can improvise when a visitor fails the checklist, but a rule cannot — if the conditions fail, the rule simply stays silent, and some other rule (or a default rule, Section 8.8) must handle that tuple.

8.1.2 The Anatomy of a Rule

A rule is essentially an if-then statement. When we write a rule, the condition implies the class label $y$ : the condition on the left-hand side (LHS) is the antecedent — also called the precondition — and the class label on the right-hand side (RHS) is the consequent. If the condition that makes up the LHS holds true, whatever sits on the RHS is the final prediction. So the LHS is a conjunction of attributes, and $y$ is the class level:

$(A_{1} = v_{1}) \land (A_{2} = v_{2}) \land \dots \land (A_{k} = v_{k}) \to y$

Formalize. Read the formula piece by piece. $A_{j}$ is an attribute (a column of the dataset) and $v_{j}$ is a value that attribute can take; $k$ is the number of conditions, and each single test such as $A_{1} = v_{1}$ is called a conjunct. The $\land$ symbol is the logical AND — every conjunct must hold true at once. The arrow $\to$ means "then", and $y$ is the predicted class label. The operator does not have to be equality: comparisons from the set ${=, \neq =, <, >, \leq, \geq}$ are allowed, so numeric attributes fit too — "if income $\geq$ 50,000" is a legal conjunct.

A classifier does not use one rule but a whole rule set:

$R = r_{1} \lor r_{2} \lor \dots \lor r_{k}$

where each $r_{i}$ is one rule and the $\lor$ (OR) says "any of these rules may fire". The reference book calls this the disjunctive normal form of the rule set — the standard shape in which rule-based classifiers are written.

Notation note. Some texts write $∣ A ∣$ for the number of tuples whose LHS holds and $∣ A \cap y ∣$ for the number of covered tuples the rule predicts correctly; we use $n_{co v er}$ and $n_{cor r ec t}$ to match the lecture. Same quantities, different names.

A single condition is fine on its own, and if we want more than one attribute we join them with a logical AND. In the buys-computer setting, where the class label column is buys_computer, one rule could be:

Worked example: two rules on the buys-computer data.

Rule 1: if age = youth then buys_computer = yes — the attribute age takes the value youth, and the rule predicts the class label yes. The antecedent has $k = 1$ conjunct.
Rule 2: if age = youth and student = yes then buys_computer = yes — here age = youth and student = yes are two attribute conditions joined with an AND ( $k = 2$ ), and the rule says the class label for this sort of tuple is again yes.

Sense-check: Rule 2 fires on a strict subset of the tuples Rule 1 fires on — every tuple that satisfies two conditions also satisfies the first. Adding a conjunct always narrows the set of tuples a rule can trigger.

8.1.3 When Is a Rule Triggered?

The terminology matters for everything that follows. If the condition of the antecedent holds true for a tuple, we say the rule antecedent is satisfied, or the rule is satisfied, or the rule covers the tuple, or the rule is triggered. All four phrases describe the same event: the LHS held true, so the rule is enabled and makes its prediction.

Visual intuition. Picture the attribute space as a rectangular room, with each axis one attribute (age along one axis, student status along the other). A rule is a box drawn inside the room: the box contains exactly the tuples that satisfy the LHS. "The rule is triggered" means the tuple landed inside the box; "the rule covers the tuple" is the same event seen from the rule's side. A tuple outside the box — even one the rule would have classified correctly — never gets the rule's prediction. In Section 8.2 the size of that box becomes the coverage, and how clean the box is inside becomes the accuracy.

Scope. This definition of a rule assumes categorical attributes work naturally (equality tests like age = youth) and numeric attributes are handled with comparison operators such as $\geq$ or $\leq$ . A rule with a non-empty antecedent is only a partial classifier: it speaks about the tuples it covers and stays silent on the rest. A complete classifier needs either a rule set that together covers everything, or a default rule for the leftovers (Sections 8.5 and 8.8).

With that boundary drawn, here are the traps beginners hit when reading rules:

Pitfalls.

Mixing up the two sides: the antecedent is the condition (LHS), the consequent is the class (RHS). The class never sits on the left.
Reading the $\land$ as OR: with AND, all conditions must hold; with OR, one would be enough. Rule 2 above does NOT fire for a 35-year-old who is a student.
Treating one rule as the classifier: the classifier is the whole rule set. A single rule is one decision, one piece of the picture.
Thinking "covers" means "predicts correctly": covering a tuple only means the rule fires for it — the prediction can still be wrong, which is exactly what accuracy (Section 8.2) measures.

Recap + bridge. A rule is an if-then statement: conditions (the antecedent) imply a class (the consequent), and we say the rule is triggered when its conditions hold. But any rule can be written — which rules are good? Next we measure a rule's quality with coverage and accuracy, the two numbers used everywhere in this lecture.

Rule-based classifiers are the workhorse of explainable prediction systems: banks state the exact conditions that flag a suspicious transaction, insurers publish the criteria that reject a claim, and loan or hiring decisions under audit rules must be justifiable line by line. The turtle-versus-amphibian example in Section 8.7 shows the human-readable style these systems are built around — every prediction can be read back as a sentence and checked by a person.

8.2 Rule Quality: Coverage and Accuracy

8.2.1 The Two Measures

Once we write a rule we want to check its quality. There are several rule-quality measures in the literature; the two listed in this class are coverage and accuracy. The professor's plain-language descriptions: "Coverage of the rule is equal to n cover divided by D" and "the accuracy of the rule would be n correct divided by n cover."

Coverage measures how much of the dataset the rule touches:

$coverage (R) = \frac{n _{co v er}}{∣ D ∣}$

where $R$ is the rule, $n_{co v er}$ is the number of tuples for which the rule is actually triggered (the number of tuples whose LHS holds true), and $∣ D ∣$ is the total number of tuples in the dataset $D$ .

Accuracy measures how often the rule is right among the tuples it covers:

$accuracy (R) = \frac{n _{cor r ec t}}{n _{co v er}}$

where $n_{cor r ec t}$ is the number of samples for which the prediction was correct, and $n_{co v er}$ is again the number of samples for which the rule is getting triggered. In words: accuracy asks, of the predictions I make, how many are correct? Coverage asks, of the whole dataset, how much does the rule even speak about?

Formalize + verify. Both formulas reconcile exactly with the reference text, which writes

$Coverage (r) = \frac{∣ A ∣}{∣ D ∣}, Accuracy (r) = \frac{∣ A \cap y ∣}{∣ A ∣}$

where $∣ A ∣$ counts the records that satisfy the antecedent — our $n_{co v er}$ — and $∣ A \cap y ∣$ counts those covered records whose true class is $y$ — our $n_{cor r ec t}$ . The professor's $n_{co v er} /∣ D ∣$ and $n_{cor r ec t} / n_{co v er}$ are the same ratios in the lecture's notation. Check the shapes: both formulas output a fraction between 0 and 1 — a coverage of 0.35 means the rule fires on 35% of the data; an accuracy of 0.4 means 40% of its own predictions are right. Boundary sanity checks: a rule that never fires has $n_{co v er} = 0$ and coverage 0 (its accuracy is undefined there), and a rule that fires on every tuple has coverage 1.

Notation note. Some texts call accuracy the confidence factor — same number, different name.

8.2.2 Worked Example: Rule R1 on the Buys-Computer Data

Take the classic buys-computer dataset shown on the screen: 14 tuples, with attributes age, income, student, and credit rating, and the class label buys_computer saying whether a person buys a computer or not. Suppose we write Rule R1:

R1: if age = youth then buys_computer = yes

Coverage. The rule is triggered exactly when the LHS holds true, i.e. when age = youth. Counting through the dataset, age = youth holds for five tuples (one, two, three, four, five). So $n_{co v er} = 5$ . The dataset has 14 samples, so:

$coverage (R_{1}) = \frac{n _{co v er}}{∣ D ∣} = \frac{5}{14} \approx 0.357 \approx 35%$

Another way to say it: if we write this rule, it gets triggered by about 35 percent of the samples.

Accuracy. Since the LHS holds for only those five tuples, we make exactly five predictions, and every prediction the rule makes is yes. Now compare each prediction with the actual class label: the first covered tuple is actually no (the rule predicts yes — wrong), the second is no (wrong), the third is no (wrong), the fourth is yes (correct), and the fifth is yes (correct). So the prediction is correct for only two of the five tuples:

$accuracy (R_{1}) = \frac{n _{cor r ec t}}{n _{co v er}} = \frac{2}{5} = 40%$

Final answer: Rule R1 has coverage $5/14 \approx 35%$ and accuracy $2/5 = 40%$ .

Sense-check: 5 of the 14 tuples are young, so roughly a third of the dataset is covered — 35% fits. Of those five young people only two actually bought a computer, so the rule is right less than half the time — 40% fits.

The takeaway: coverage and accuracy are computed from the same rule, but they answer different questions — how much of the data the rule covers, and how often the rule is right within what it covers.

8.2.3 What Coverage and Accuracy Count

To rephrase: coverage is the percentage of tuples for which the rule's antecedent (the LHS) is holding true, out of the total tuples in the dataset. Accuracy is the percentage of the covered tuples for which we do a correct prediction — the number of correct predictions out of the number of tuples the rule is triggered for. The class also notes that more ways to measure rule quality exist in the literature — for example the Laplace estimate and the m-estimate, which fold the rule's coverage into the accuracy-like score so that a rule built on two lucky tuples scores lower than one built on forty solid ones — and these two (coverage, accuracy) are the ones listed in this session.

Pitfalls.

Using the wrong denominator: coverage divides by $∣ D ∣$ (all tuples), accuracy divides by $n_{co v er}$ (only the triggered ones). Swapping them is the classic error.
Reporting accuracy when the rule fires zero times: with $n_{co v er} = 0$ the ratio is undefined; a rule that never fires is not "accurate", it is absent.
Forgetting that accuracy is measured on the covered tuples only: a rule that covers one tuple and gets it right shows 100% accuracy — impressive-looking and nearly useless (Section 8.9).

Visual intuition. Go back to the box picture from Section 8.1: coverage is the fraction of the room's floor area inside the box; accuracy is the fraction of the box's interior that is painted in the target class's color. A huge pale box (high coverage, low accuracy) and a tiny perfect box (100% accuracy, near-zero coverage) are the two extreme shapes this lecture keeps coming back to.

Exam note: Numerical questions on this concept are the safest marks on the paper — count $n_{co v er}$ , $n_{cor r ec t}$ , and $∣ D ∣$ from the dataset, then write both ratios, exactly as in the buys-computer example ( $5/14 \approx 35%$ , $2/5 = 40%$ ). Show the counts before the division; examiners reward the working.

Coverage and accuracy answer different questions about the same rule: coverage asks "how much of the dataset does the rule speak about?", accuracy asks "of what it says, how often is it right?" Next: where do rules come from — written by hand straight from the data, or extracted from a model?

8.3 Two Ways to Build Rules: Direct and Indirect

8.3.1 Direct Method

There are two essential ways to write rules. In the direct method, you look into the dataset and write the rules directly — by analyzing the data, you decide the rules yourself. If you are handed a dataset, you study it carefully and produce rules straight from what you see. RIPPER, CN2, and similar algorithms are called direct methods.

The direct method is the lecture's main storyline for the rest of the session: Section 8.10 presents the sequential covering algorithm, Section 8.11 the CN2 rule-growing loop, and Section 8.12 RIPPER with FOIL information gain. The recurring idea: no model is built in advance — the learner reads the data and grows rules one condition at a time.

8.3.2 Indirect Method

In the indirect method, you first build a classification model — a decision tree or maybe a neural network — and then write the rules based on that model. For example, given a dataset you first build a tree, and then by looking at the tree you write the rules. The algorithm name for this is C4.5 rules: C4.5 is how you build the classification model using a decision tree, and when you extract the rules by looking at the tree, it is called C4.5 rules.

The indirect route is developed in Section 8.4 (one rule per root-to-leaf path) and Section 8.5 (the two properties that come free with tree rules).

Comparison — the two methods side by side:

Dimension	Direct method	Indirect method
What you start from	the raw dataset	an existing model (decision tree, neural network)
Where the rules come from	the learner inspects the data and grows rules itself	the learner translates the model's structure into rules
Example algorithms	RIPPER, CN2, sequential covering (Sections 8.10–8.12)	C4.5 rules (Section 8.4)
Rule-quality control during learning	evaluation measures during growth (accuracy, coverage, entropy, FOIL gain)	the tree's own split decisions carry the logic
Properties of the rule set	not guaranteed; ordered list + default rule needed	mutually exclusive and exhaustive for free (Section 8.5)
Typical use	no model exists yet; compact, readable rules wanted	a tree already exists or is easier to build

When to pick which: if a decision tree is already built (or is the natural first step), the indirect route is one extra read — transcribe the paths; if you start from raw data and want human-readable rules without building a model first, the direct route is the natural choice. Both produce explainable if-then rules; they differ only in where the rule structure comes from — data (direct) or model (indirect).

8.4 Indirect Method: Rules from a Decision Tree

8.4.1 The Procedure

Given a training dataset, the indirect method works in two stages. First, build a decision tree on the dataset — the same tree-building we saw in the previous class. Once the tree is built, write the rules: there will be one rule covering each path from root to leaf. Start from the root node and walk toward the leaf node, collecting the conditions along the way; if there are multiple levels, combine the levels by putting an AND between the conditions. The leaf node is typically the class consequent — the class level, or the class prediction — and that becomes the consequent of the rule. Iterate this process for each leaf node: one leaf, one rule.

Purpose. The tree already contains a complete decision procedure; the rules rewrite it into if-then form so that each decision can be read as a sentence. This is the indirect method: rules come from a model, not from staring at the data.

Inputs & Outputs. In: a trained decision tree whose internal nodes are test conditions and whose leaves carry class labels. Out: one rule per leaf — the conjunction of the test conditions along that root-to-leaf path forms the antecedent, and the leaf's class label forms the consequent.

Steps.

Build the decision tree on the training data (the procedure from the previous class).
Pick a leaf node; walk from the root down to that leaf, writing down each test condition passed on the way (for example age = youth, then student = yes).
Join the collected conditions with logical AND to form the antecedent.
Read the leaf's class label; that becomes the rule's consequent — the predicted class.
Repeat for every leaf. The number of rules equals the number of leaves; the rule set is complete when every leaf has produced exactly one rule.

8.4.2 Example: Five Leaf Nodes, Five Rules

Consider a tree with five leaf nodes (one, two, three, four, five). The number of rules we write equals the number of leaf nodes in the tree, so this tree yields exactly five rules. The first rule walks the leftmost root-to-leaf path, the second walks the next path, and so on. For instance, rule 3 could be: if age = middle age then class label = yes. This is the whole indirect recipe: given a training dataset, build a decision tree; once the tree is built, start at the root, go toward each leaf, combine the attributes along each path with AND, and write one rule per leaf.

Worked example: a five-leaf tree gives five rules. The classic buys-computer tree splits on age at the root (youth / middle age / senior); the youth branch splits on student, and the senior branch splits on credit rating. That structure has five leaves, so the procedure produces exactly five rules — one per leaf:

Rule	Path walked	Rule written
r1	youth → student = yes	`if age = youth and student = yes then class label = yes`
r2	youth → student = no	`if age = youth and student = no then class label = no`
r3	middle age (leaf)	`if age = middle age then class label = yes`
r4	senior → credit rating = fair	`if age = senior and credit rating = fair then class label = yes`
r5	senior → credit rating = excellent	`if age = senior and credit rating = excellent then class label = no`

Rule 3 is the single-condition example from the lecture: the middle-age branch has no further test, so its rule's antecedent is exactly age = middle age. Sense-check: each path appears once, so no rule is duplicated, and every tuple the tree can route reaches one leaf — so one rule per tuple, a fact that becomes the property of mutual exclusion in Section 8.5.

8.4.3 The Rule Set Carries All Tree Information

Because every rule is a direct translation of a root-to-leaf path, the rule set contains as much information as there is in the tree. Whatever information is in the tree, we have translated it into rules — nothing is added and nothing is lost in the conversion.

Complexity & cost. The conversion is a single pass over the tree: the work is proportional to the total number of root-to-leaf paths, and each rule costs as many comparisons as its path has test conditions. A wide tree yields many short rules; a deep tree yields fewer, longer rules. At prediction time the system executes every comparison in the rule's LHS — precisely the cost that motivates rule simplification in Section 8.6.

When to use / alternatives. Use the indirect route when a decision tree already exists (or is easy to build) and you want the interpretability of rules plus the two free properties of Section 8.5 — mutually exclusive, exhaustive rules. The alternative is the direct method (Sections 8.10–8.12), which skips the tree entirely and grows rules straight from the data; that route produces compact rules but does not hand you those two properties for free.

Recap + bridge. Indirect extraction = one rule per root-to-leaf path: antecedent is the AND of the path's tests, consequent is the leaf's class; the rule set carries exactly the tree's information. Because the paths are disjoint and cover all leaves, tree rules have two special properties — mutual exclusion and exhaustiveness — which we examine next.

8.5 Two Free Properties: Mutual Exclusion and Exhaustiveness

8.5.1 Mutual Exclusion

If we write rules using a decision tree, there are two properties that come to us for free — they are implicit in the tree structure. These properties are very important because they help us decide, for any tuple, what to do. The first property is mutual exclusion: no two rules are triggered on the same tuple. Since each rule corresponds to a different root-to-leaf path, every tuple falls down exactly one path, so exactly one rule fires for it. For no tuple will two rules be triggered.

Why does this matter? Suppose you have written multiple rules and a test tuple arrives whose LHS holds true for several of them. If all those rules are triggered, which rule do you take to do the final prediction? Mutual exclusion removes that question entirely: with tree-built rules, the conflict never arises.

Formalize. A decision tree routes every tuple by exactly one sequence of test outcomes — at each internal node exactly one branch matches the tuple's attribute values. The tuple ends in exactly one leaf, and that leaf belongs to exactly one rule (the path that leads to it). Two different root-to-leaf paths differ in at least one test outcome, so no single tuple can satisfy two different antecedents at once. So at most one rule can ever be triggered for any tuple — that is mutual exclusion.

Why it is "free". Nothing about the rule-growing or rule-joining had to be checked: the disjointness of root-to-leaf paths is a structural fact of the tree itself, and the rules merely inherit it.

8.5.2 Exhaustiveness

The second property is exhaustiveness: you will have at least one rule for each record. For every tuple in the data, at least one rule gets triggered. This is required because if you are given a tuple for which no rule is triggered, which class level will you predict? There would be nothing to say. Exhaustiveness guarantees you are never in that situation.

Formalize. Every tuple, whatever its attribute values, is routed by the tree and lands in some leaf — there is no "nowhere" a tuple can fall as long as each test's branches cover every value it can take. Since every leaf produced a rule, every tuple triggers at least one rule. Together the two properties give the strong guarantee: every tuple triggers exactly one rule — no conflicts, no gaps.

Scope. Both properties are free because the rules were transcribed from a tree: path disjointness gives mutual exclusion, full branch coverage gives exhaustiveness. Hand-written rules, or rules simplified after extraction (Section 8.6), get neither property for free — Sections 8.7 and 8.8 exist to fix what is lost.

8.5.3 Example: Four Rules from a Refund Tree

Suppose the decision tree built from the dataset has four leaf nodes — one, two, three, four — so there will be four rules. The first rule starts from the root and walks to the first leaf: if refund = yes then class label = no. The remaining rules walk the other paths, combining multiple attributes with AND on the way to each leaf. With this tree, the rules are mutually exclusive (no two rules trigger for the same tuple) and exhaustive in nature (for each tuple, at least one rule is written). And, as above, the rule set carries all the information the tree carried.

Worked example: the refund tree. The root tests refund (yes / no). The yes branch is a leaf with class no. The no branch continues with marital status (married / single), and the single branch splits once more on taxable income (low / high). Four leaves, four rules:

Path	Rule
refund = yes	`if refund = yes then class label = no`
refund = no, married	`if refund = no and marital status = married then class label = no`
refund = no, single, income = low	`if refund = no and marital status = single and taxable income = low then class label = yes`
refund = no, single, income = high	`if refund = no and marital status = single and taxable income = high then class label = no`

Check the two properties on the four rules. Mutual exclusion: a tuple can satisfy at most one path — the branches at each node are disjoint, so a tuple cannot simultaneously be married and single, or income = low and income = high. Exhaustiveness: any tuple the tree can route lands in some leaf, so every tuple satisfies some path. Sense-check: the four rules are literally the four root-to-leaf paths written out, so their union covers exactly the territory the tree covers.

Pitfalls.

Assuming every rule set has these properties: they hold for tree-transcribed rules; hand-built rule sets (direct method, Section 8.3) routinely violate both.
Believing mutual exclusion makes conflicts impossible forever: simplification (Section 8.6) can make two rules fire on one tuple again — the properties are "free with the tree", not "free after any edit".
Confusing exhaustiveness with correctness: "at least one rule fires" says nothing about that rule being right — accuracy is a separate question (Section 8.2).

Visual intuition. The decision tree is a funnel: every tuple drops in at the top and exits through exactly one of the bottom spouts (the leaves). One spout per tuple = mutual exclusion; no plug hole where a tuple can get stuck = exhaustiveness. The rule set is the same funnel cut into one pipe per spout — which is why the rule set and the tree carry the same information.

Recap + bridge. Tree rules come with two free guarantees — at most one rule fires per tuple (mutual exclusion) and at least one rule fires per tuple (exhaustiveness). Both are a direct gift of the tree structure. Next: can we make the rules cheaper to execute — and what does that simplification cost us?

8.6 Rule Simplification

8.6.1 Why Simplify

Now take any of these rules, say one with several conditions in the LHS. If we are building the rule into hardware or running it on a system, all these comparisons actually get executed. That execution is not free — there is a cost associated with doing all these operations. So we ask: can we simplify the rules? Simplification means reducing the number of conditions such that the quality of the rule is not compromised — we do the same prediction, but with one less check.

Intuition. Every conjunct in the LHS is a computation the system must run at prediction time: a chip evaluates refund = no, then marital status = married, then reads the class. In embedded hardware or a high-frequency system, each dropped condition saves real work per prediction, multiplied by millions of tuples. Simplification cuts that work while keeping the rule's behavior identical — fewer conditions, same decisions, cheaper rules.

Professor's rule of thumb: fewer conditions on the left-hand side means a more efficient rule — the same prediction with less computation.

8.6.2 Worked Example: Dropping a Redundant Condition

Take the rule extracted from a tree: if refund = no and marital status = married then class = no. Look carefully at what this rule covers. The condition marital status = married is the discriminating one — this rule is actually getting triggered for four tuples out of a 10-tuple dataset. So:

$coverage = \frac{n _{co v er}}{∣ D ∣} = \frac{4}{10} = 40%$

and every one of those four tuples has actual class label no, matching the rule's prediction, so:

$accuracy = \frac{n _{cor r ec t}}{n _{co v er}} = \frac{4}{4} = 100%$

Coverage is 40% and accuracy is 100%. The only problem: we are doing two condition checks — two computations on the LHS. Can we reduce it? If we consider only one attribute, marital status = married, we get the same result: the rule has the same coverage and the same accuracy. So why not drop the other condition? The rule becomes more efficient — less computation on the left-hand side — while the quality stays identical. This is called rule simplification: reducing the LHS conditions of the rules while keeping accuracy and coverage the same, because we want the rule to be more efficient.

Worked example, step by step. Original rule: if refund = no and marital status = married then class = no, dataset of 10 tuples.

Count the coverage. The rule triggers for the 4 married tuples whose refund is no: $n_{co v er} = 4$ , $∣ D ∣ = 10$ :

$coverage = \frac{n _{co v er}}{∣ D ∣} = \frac{4}{10} = 40%$

Count the accuracy. All 4 covered tuples really have class no, so $n_{cor r ec t} = 4$ :

$accuracy = \frac{n _{cor r ec t}}{n _{co v er}} = \frac{4}{4} = 100%$

Ask which conjunct discriminates. Inside this tree path, refund = no adds no filtering power: the married tuples in this region are exactly the refund-no married tuples, so dropping refund = no changes nothing about which tuples fire the rule.
Drop it. Simplified rule: if marital status = married then class = no. Re-check: still triggered for the same 4 tuples, still 4 correct — coverage 40%, accuracy 100% unchanged.
Final answer: the simplified rule has identical quality (coverage 40%, accuracy 100%) at half the LHS cost.

Sense-check: one check instead of two, same four predictions, same four correct answers — the removal was free because the dropped conjunct never excluded any tuple.

8.6.3 What Simplification Breaks

Once we simplify rules, we have to go back and re-check the properties we assumed earlier. The rules after simplifying might not be mutually exclusive — two rules might now get triggered for a single tuple. Then how do you resolve the conflict? That is the first question. Second, simplification might break exhaustiveness: there might now be tuples for which no rule gets triggered at all. So if we do rule simplification, we must check both properties, and when they no longer hold we need mechanisms — conflict resolution strategies for the first problem, and a default strategy for the second.

Scope. Simplification keeps this rule's quality identical on the training data, but it can change how the rule set behaves as a whole: a dropped conjunct may leave the rule overlapping another rule's territory (breaking mutual exclusion) or may leave a corner of the attribute space with no covering rule (breaking exhaustiveness). The same idea appears in the reference book, which merges three positive-class rules into two once they all fire whenever Q = yes. After any simplification, re-run the two property checks before trusting the set.

Pitfalls.

Dropping a conjunct because it is redundant on the training set and assuming it will stay redundant on new data: the gain is permanent, but the risk belongs to future tuples; reference books prune with validation data to keep this risk measured.
Forgetting the follow-up: simplification is never "just editing a rule" — it triggers the conflict-resolution machinery (Section 8.7) and the default-rule fallback (Section 8.8).
Simplifying a rule so far that it duplicates another rule in the set: duplicates change nothing and just waste checks.

Recap + bridge. Simplification removes LHS conditions when quality stays identical — the same coverage and accuracy at lower execution cost. The price: the two free properties can break, so we need (1) conflict resolution for over-triggering and (2) a default rule for under-triggering — the subjects of Sections 8.7 and 8.8.

8.7 Conflict Resolution Strategies

8.7.1 The Two Problems

We have two problems to solve. Problem one: for a particular tuple, more than one rule gets triggered. If all the triggered rules predict the same class, there is no issue. If they predict different classes, how do we resolve the conflict? This problem comes out of breaking mutual exclusion. Problem two: for a particular tuple, no rule gets triggered. Then how does the rule-based classifier do the final prediction? This comes out of breaking exhaustiveness. The literature offers several conflict resolution strategies: size ordering, rule ordering, class-based rule ordering, and more — let's look at each.

8.7.2 Size Ordering

Size ordering arranges the rules based on their size. The toughest rule goes on top: the toughest rule is the one with a lot of conditions in the antecedent — if A = 1 and B = 2 and C = 3 and D = 4 ... then class = .... A rule with many conditions is hard to trigger, because all of them must hold true; a rule with few conditions fires easily. So the toughest rule is put first, the second toughest second, and so on. Whenever we do the final prediction, we search from top to bottom: check whether R1 is triggered; if yes, R1's prediction is the final answer. If R1 is not triggered, check R2, then R3, and so on. The idea: prefer the most specific rule — the one that earned its trigger by satisfying the most conditions.

8.7.3 Rule Ordering

Rule ordering is the same arrangement game with a different sort key: we arrange the rules in a particular order, and whenever a tuple is given, we check R1, then R2, then R3, and so on until one triggers — the first triggered rule decides, end of story. The order itself can be based on any quality measure we choose: the rule with the highest accuracy goes on top, then the second highest, and so on; or we can order by coverage (highest coverage first); or by antecedent size — the LHS size, which is exactly size ordering; or by a domain expert's opinion. You decide the parameter, arrange the rules, and the first rule that triggers gives the final prediction.

8.7.4 Class-Based Rule Ordering

Class-based rule ordering bundles all the rules that predict the same class together. All rules predicting class C1 are put together in a bundle, all rules predicting class C2 in the next bundle, and so on; if there are $n$ classes, you bundle class 1 first, class 2 second, and so forth. Which class comes first is decided based on domain expertise. Given a tuple T1, you check rule 1, rule 2, rule 3... in bundle order; if any rule holds true, that rule's class is the final prediction; otherwise you move to the next rule.

Formalize: the three orderings in one line each.

Size ordering sorts by the number of conjuncts in the LHS, most conditions first ("toughest to trigger on top"). A many-condition rule fires only when every condition holds, so finding it triggered is strong evidence its specific prediction is right.
Rule ordering sorts by any chosen quality measure — accuracy, coverage, antecedent size (which reproduces size ordering), or a domain expert's judgment. The rule with the best score sits on top.
Class-based ordering partitions the rule set into bundles, one per predicted class; the classes themselves are ordered by domain expertise (the reference algorithm C4.5rules orders classes by their total description length). Within a bundle, any fired rule gives the same class.

All three are used identically at prediction time: walk the ordered list top-down, stop at the first triggered rule, and take its consequent as the prediction. The reference book calls this an ordered rule set or decision list.

8.7.5 Majority Voting: The Alternative Usually Avoided

Another way to handle multiple triggered rules is a voting scheme. If three rules are triggered for a tuple, you run all three and combine their votes: for example, two rules say the class label is no and one says yes, so the final prediction of the rule-based classifier is no based on the voting scheme. But majority voting is typically not used in practice, because there are a lot of rules and it is not cost efficient: for each tuple you would have to check every rule and combine all the results. What existing systems typically use is the ordered approach — write rules R1, R2, ... and start checking from the top until one triggers. Voting exists as an option, and some systems may need it, but the ordered scheme is the norm.

Comparison — the four strategies side by side:

Strategy	Sort key / grouping	Decision rule	Cost per tuple	Used by
Size ordering	LHS size, most conditions first	first triggered rule wins	stops early, few checks	hand-ordered rule sets
Rule ordering	any quality measure (accuracy, coverage, size, expert opinion)	first triggered rule wins	stops early, few checks	general ordered rule sets
Class-based ordering	rules bundled by class; class order from domain expertise	first triggered rule's class wins	stops early, few checks	C4.5rules, RIPPER
Majority voting	no order; every triggered rule casts a vote	class with most votes wins	every rule checked for every tuple	rare; small or special systems

When to pick which: use one of the ordered schemes whenever rules and tuples are many — the cost is proportional to how far down the list you walk, and most tuples are decided near the top. Keep voting only when the rule set is tiny or when every prediction must be argued from all evidence.

8.7.6 Worked Example: Reptile or Amphibian?

Here is a concrete ordering example. Suppose we have written five rules, and a test sample is given to us for prediction:

Tuple: name = turtle, blood type = cold, give birth = no,
       can apply for student = yes, live in water = sometimes

Step through the five rules and see which ones trigger. name = turtle appears in no rule — no trigger there. blood type = cold — still no rule triggered. give birth = no — this matches several rules; three rules might be triggered by this condition. can apply for student = yes — this kills rule R1 (R1 needs a different value), and also disqualifies two others. live in water = sometimes — this triggers one more. When the dust settles, exactly two rules are triggered for this tuple: R4 and R5. Now look at the final class labels of those two rules: they are different. One rule says reptile, the other says amphibian. So which one should the classification system take? We need a conflict resolution strategy: arrange the rules in a particular order — by accuracy (highest accurate rule on top), or by size ordering (toughest rule on top), or by coverage — and the first rule that gets triggered is used for the final prediction. In this example R4 is the first of the two to be checked, so the final prediction is reptile.

Worked example, step by step. Five rules R1–R5; the test tuple is the turtle given above.

Test R1 against the tuple — fails on can apply for student (R1 needs a different value): not triggered.
R2 and R3 — both fail on the same condition: not triggered.
R4 — give birth = no and live in water = sometimes both hold for the tuple: triggered, predicts reptile.
R5 — the same two conditions hold: triggered, predicts amphibian.
Two rules, two different classes. Under any ordered strategy (accuracy order, size order, coverage order — whichever ranks R4 above R5), R4 is checked first and decides the answer.

Final answer: the final prediction is reptile — R4 is first in the ordering and it fires.

Sense-check: both rules legitimately fire — this tuple is genuinely ambiguous for the rule set — and the ordering is what breaks the tie. Every ordered strategy gives exactly one deterministic answer; only a different order could change it.

Pitfalls.

Assuming conflicts only matter when the classes differ: even when two triggered rules agree, ordering decides which rule "earns" the prediction — but only differing predictions force a resolution.
Ordering by accuracy naively: a 100%-accuracy rule covering one tuple can outrank a 95% rule covering forty (Section 8.9) — the exact trap the lecture warns about.
Believing voting is safer because it is "democratic": it checks every rule for every tuple, which is why production systems prefer ordered evaluation (the class notes the cost explicitly).

Recap + bridge. When mutual exclusion breaks, order the rules — by size, by quality, or by class — and let the first triggered rule decide; voting works but is too expensive for production use. That solves problem one. Problem two — no rule firing at all — needs a different mechanism: the default rule, next.

8.8 Default Rules: When No Rule Fires

8.8.1 The Default Rule Idea

The second problem: if given a tuple, no rule gets triggered, what should your prediction be? The answer is a default rule — a fallback that always fires. One standard way to build it: the default class is the majority class in your dataset. If most of the elements in the dataset belong to, say, the positive class, the default rule says: when no rule is triggered, predict the class level as positive, because the majority class was positive. There is no thumb rule here — this is one of the strategies that can help you trigger one of the rules, and it is a complete resolution strategy.

Formalize. A default rule is a rule with an empty antecedent:

$r_{d} : () \to y_{d}$

No conditions at all, so it fires for every tuple that reaches it. The reference book writes exactly this form and calls $y_{d}$ the default class, typically the majority class among the training records the other rules did not cover. The professor's "there is no thumb rule" means the choice is free: majority class, a class suggested by domain knowledge, or the class that minimizes misclassification cost — any of them gives a complete resolution strategy, and the default rule guarantees that one rule always triggers.

Worked example: the default rule for the buys-computer data. The classic buys-computer dataset has 14 tuples: 9 with buys_computer = yes and 5 with no. Suppose the extracted rules cover the 5 no tuples and 8 of the 9 yes tuples; one yes tuple has no rule that fires for it.

Majority class over the whole dataset: yes — 9 of 14.
Default rule: else -> buys_computer = yes (empty antecedent).
The leftover tuple now gets a prediction — yes — instead of having nothing said about it.
The default rule's own coverage is not meaningful in the usual sense: it fires only on whatever falls through, and its job is purely to close the exhaustiveness gap.

Sense-check: the default rule is the safety net, not the main act — it only ever speaks when every other rule has stayed silent.

8.8.2 What the Default Rule Guarantees

It is worth being honest about what the default rule does and does not guarantee: the default rule might be of poor quality; we are not commenting on the rule's quality, only on the requirement that at least one rule should be triggered for each tuple. That guarantee — one rule per tuple — is what the default rule buys. So both problems are solved. If more than one rule is triggered, arrange the rules in a particular order (by coverage, by accuracy, by antecedent size, by whatever we choose) and walk from top to bottom; whichever rule is triggered first gives the final prediction. If no rule is triggered, use a default rule that predicts the majority class — or anything else the domain knowledge suggests.

Scope — what the default rule buys and does not buy. The guarantee is coverage, not quality: the default rule may be wrong on many of the tuples it absorbs — it predicts the majority class for a mixed remainder. Its only contract is that every tuple gets at least one prediction, closing the exhaustiveness gap that simplification opened. If one class dominates the data (95% of a dataset is one class), the default rule alone already looks strong — the danger is letting it do the real work instead of the rules.

Pitfalls.

Confusing "default class" with "best class": it is the fallback's answer, chosen for coverage, not for accuracy.
Letting the default rule override a triggered rule: it fires only when nothing else does.
Building the default class from the whole dataset instead of the uncovered remainder: the reference book computes the majority among the records the existing rules did not cover — a subtle but examinable difference.

Recap + bridge. The default rule — empty antecedent, fires for everything — solves problem two: at least one rule per tuple, even if its quality is not guaranteed. With ordered rules (problem one) and a default rule (problem two), the rule-based classifier can make a prediction for every tuple. Next: a warning about trusting coverage and accuracy alone when judging rules.

8.9 Accuracy and Coverage Alone Can Mislead

8.9.1 Worked Example: 95% versus 100%

Take a two-class dataset — class A and class R — projected into a two-dimensional space, with some A's and some R's scattered across it. Suppose we decide to write two rules, R1 and R2, and we compute the accuracy of each. The accuracy of R1 comes out to 95%, and the accuracy of R2 comes out to one hundred percent. If we blindly look at the numbers, R2 is the better rule, because 100 is greater than 95. But look carefully: rule R2 is actually only getting triggered for two tuples, and both of its predictions were correct. R1, on the other hand, does 40 predictions — it is triggered for 40 tuples — and 38 of those predictions were correct, with only two wrong. So accuracy alone tells you that R2 is numerically better, but coverage alone shows R2 is barely used. In this case R1 is the better rule, because it gives you a better picture of the classification model as a whole. The point: do not look at only one parameter — accuracy or coverage on its own might not give you the complete picture. Accuracy on its own might not be a reliable estimate of rule quality, and coverage alone might not be useful either.

Worked example, both numbers side by side.

	Rule R1	Rule R2
Predictions made ( $n_{co v er}$ )	40	2
Correct ( $n_{cor r ec t}$ )	38	2
Accuracy $n_{cor r ec t} / n_{co v er}$	38/40 = 95%	2/2 = 100%
Coverage	speaks about most of the data	tiny — 2 tuples
Wrong answers	2	0

By accuracy alone, R2 "wins" — 100 > 95. But R2's perfect score is earned on two tuples; R1's 95% is earned on forty. If a hundred new tuples arrive tomorrow, R2 will comment on roughly none of them, while R1 will predict for all of them.

Final answer: R1 is the better rule — 38 correct out of 40 on the whole picture beats 2 out of 2 on a corner of it.

Sense-check: the same logic appears in the reference book, where a rule covering 50 positive and 5 negative examples (90.9% accuracy) is preferred over a rule covering 2 positive and no negative examples (100%) — a high accuracy on a tiny base is potentially spurious.

8.9.2 Combining Measures

Many times we integrate the two measures together to get a better way of measuring the quality of the rule — we combine coverage and accuracy. This combined measure is sometimes called FOIL information gain, which the class returns to later. The general lesson: combine multiple performance measures, like coverage and accuracy, to better visualize the quality of the rule.

Intuition: why combining works. A lone accuracy is easy to game: cover one easy tuple, score 100%. A lone coverage is easy too: cover everything, and speak about 100% of the data — while being wrong half the time. A combined measure makes both fakes visible at once. The reference book folds coverage into the score with measures like the Laplace estimate and the m-estimate, which shrink an accuracy that was earned on very few tuples; the lecture's combined measure of choice is FOIL information gain (Section 8.12), which rewards rules with both high support (many positive tuples covered) and high purity.

Visual intuition. Picture the two-dimensional space: R2 is a pin-sized box that is perfectly clean inside; R1 is a large box covering a broad region, 95% clean. From a distance the pin-box looks perfect; walk close enough to see its area and the comparison inverts. The metric you choose decides which illusion you see — coverage, accuracy, or both at once.

Pitfalls.

Ranking rules by accuracy alone inside any ordering scheme — the same trap as Section 8.7: a tiny, perfect rule can outrank a big, nearly-perfect one.
Comparing rules' accuracies without also reading their coverage: the two numbers must be read together, like the table above.
Concluding a rule is useless because its accuracy is below 100%: a rule that is 95% right on 40 tuples may be the most useful single rule in the set.

Recap + bridge. Accuracy alone overrates tiny rules; coverage alone underrates them — read both, and prefer combined measures such as FOIL information gain. Next, the algorithms that build rules in the first place: sequential covering (8.10), CN2 (8.11), and RIPPER with FOIL gain (8.12).

8.10 Direct Method: Sequential Covering

8.10.1 The Algorithm

The direct method, as said, means you look straight into the dataset and start writing the rules — R1, R2, and so on. The algorithm for this is the sequential covering algorithm: it extracts rules directly from the training dataset, with no model built in advance to guide you. There are multiple algorithms that do this — FOIL, RIPPER, and CN2 are the well-known direct-method rule learners (RIPPER and CN2 are the two the class names explicitly).

The name comes from the notion that rules are learned sequentially, one at a time: we write rule one, then rule two, and so on. The expectation is that the first rule you write will cover a large number of tuples — hopefully of the same class — so that the rule's accuracy is high. The accuracy may still be less than 100% if a few tuples get wrong predictions; that is accepted. And you combine multiple attributes with AND as needed. The algorithm itself is simple: start with R1 as an empty rule; use a learn-one-rule function — put one attribute into the rule, check the quality of the rule; if the quality is good, hold that attribute; otherwise add one more attribute. Do this recursively and iteratively — attributes go in one by one until one of the stopping criteria is reached. One rule is learned this way, then the next rule starts again from empty.

Purpose. Extract a complete, ordered rule set straight from the training data, with no intermediate model — the direct method's signature move: rules come from the data, not from a tree.

Inputs & Outputs. In: the training records $E$ (each with its class label) and the candidate attribute-value pairs. Out: an ordered rule list $R = r_{1} \lor r_{2} \lor \dots \lor r_{k}$ plus a default rule for whatever remains uncovered.

Steps. (The reference book's Algorithm 5.1.)

Decide the order in which classes will be learned — by class prevalence or misclassification cost; for a two-class problem the majority class is typically saved for the default rule.
For the current class $y$ , treat its records as positive examples; everything else is negative.
Grow one rule with the Learn-One-Rule loop: start from an empty rule, add one attribute-value condition at a time, and keep each addition only while the rule's quality (accuracy, coverage, entropy, FOIL gain) improves; stop at the stopping criterion.
Remove from $E$ every record the new rule covers — they are now explained.
Append the rule to the list and repeat from step 3 until the class's stopping condition is met.
Move to the next class; when all classes are done, append the default rule at the bottom of the list.

8.10.2 Visual Walkthrough: Covering the Data Rule by Rule

Given a dataset with two classes — positive class and negative class — start writing rules. Suppose we write a rule that covers a batch of tuples, all of them positive class: that becomes rule R1. Since R1 is getting triggered for all these tuples, remove those tuples from the dataset — they are already explained. Now write another rule covering the next batch of tuples: that becomes R2. Iterate until every tuple is covered. In the visual example, R1 covers the first batch, R2 the second batch, R3 the third, and then we put a default rule that predicts the negative class. Four rules and we are done: for one group of tuples R1 was triggered, for another R2, for another R3, and for the leftovers the default rule predicts the negative class. The guiding idea: try to cover each tuple, and cover each tuple with a rule of one class — if a tuple ends up uncovered, write a default rule.

Trace: covering the plane rule by rule. Start with a two-class scatter (positives as +, negatives as −).

Write R1 to cover the largest batch of + tuples — say 12 of them, all +. Coverage good, accuracy 100%.
Remove those 12 tuples — they are explained; the learner never looks at them again.
Write R2 for the next + batch (8 tuples). Remove them.
Write R3 for the last + batch (5 tuples). Remove them.
Everything left is −; write the default rule: else -> negative class.

Final rule set: R1 (12 +), R2 (8 +), R3 (5 +), default (−). Every tuple is covered: exactly one of R1/R2/R3 fires for each + tuple; the default rule catches all the − leftovers. Sense-check: the rule list mirrors the funnel of Section 8.5 — each rule owns a region, and the default rule owns the rest.

8.10.3 From a Broad Rule to a Tight Rule

When you write your first rule, you start broad. The broad rule has both positive-class and negative-class samples inside its coverage — a few samples whose class labels are positive and a few whose labels are negative. That is a problem: with one rule you can make only one prediction, one class, so if the rule covers both classes its accuracy will be very poor. So you restrict the rule: add one more attribute to shrink the area of the rule — the coverage — so it is triggered for fewer tuples, hopefully only positive class. In the example, first we use only one attribute; then we add a second attribute and check what the accuracy of the rule becomes; then we add a third to tighten further. The final rule covers only positive-class samples inside its coverage: the accuracy of this rule is 100% and the coverage is still high. That is how the direct method generates each rule: start broad, keep adding LHS conditions until the rule is tight enough.

Trace: from broad to tight. A 100-tuple dataset with 60 + and 40 − scattered as two clumps.

Start broad with one condition A = x: the rule box covers both clumps — 45 + and 35 − inside. Accuracy: 45/80 = 56%, unusable.
Add a second condition B = y: the box shrinks toward the + clump — 40 +, 5 − inside. Accuracy: 40/45 ≈ 89%. Better — keep B.
Add a third condition C = z: the box shrinks again to 38 +, 0 −. Accuracy: 38/38 = 100%. Coverage: 38% of the data — still high.

Final answer: the tightened rule covers only + tuples (accuracy 100%) with respectable coverage.

Sense-check: each added condition can only shrink the box — never enlarge it — so accuracy can only rise as the box zeroes in on the pure region, at the price of coverage.

Pitfalls.

Expecting the first broad rule to be the final rule: it is deliberately too wide; tightening is part of the algorithm.
Adding conditions forever: every conjunct costs runtime (Section 8.6) and shrinks coverage — the stopping criterion exists to stop before the rule becomes a memorized one-liner per tuple.
Forgetting the removal step: without deleting covered records, the next rule would relearn the previous rule.

Complexity & cost. The search is greedy: each Learn-One-Rule step examines candidate conditions and keeps the best, so the number of candidate evaluations is bounded by the attributes times their values. Because a greedy choice can lock in a suboptimal conjunct, the reference book's CN2 uses a beam search: keep the k best partial rules instead of only the best one. At prediction time the ordered list means most tuples trigger a rule near the top — the expected cost per tuple is a few condition checks, far less than the every-rule check of voting.

Recap + bridge. Sequential covering: learn rules one at a time straight from the data, remove what each rule covers, add a default rule for the rest. The grow-one-rule loop inside it — start broad, add conditions while quality improves — is formalized next in CN2.

8.11 Growing One Rule: The CN2 Algorithm

8.11.1 Incremental Attribute Addition

The rule-growing procedure just described is formalized in the CN2 algorithm. It is simple and it is in the book. For each rule R1 we start with the null set — an empty rule. Then we put one attribute into the rule and check the quality of the rule. The quality can be measured by accuracy, coverage, entropy, or whatever we choose. If the quality of the rule improves — say the rule's quality was 90% and after adding the attribute it gets better, in the sense that the rule is purer — that is good, and we add the next attribute. If a further attribute makes the rule worse — the rule gets less pure — we do not consider that attribute. So we build the rule incrementally: start empty, add one attribute, measure quality; add another, measure again; keep adding while performance improves, and stop the moment a new attribute hurts.

This should feel familiar: in the feature-selection and attribute-subset discussion we talked about forward selection and backward elimination — randomly adding or removing features and measuring the effect, with entropy available as the criterion there as well. The rule-growing loop in CN2 is the same spirit: add features one by one and keep the ones that help.

8.11.2 Worked Example: A1, A2, A3

Concretely: to write rule R1, start with a null rule. Add the condition A1 = A. The rule now has high coverage — it fires for many tuples — but check its accuracy: 50%. The rule is too broad to trust. Add a second condition, A2 = B. Now the coverage is reduced and the accuracy is increased — the rule is tighter and purer. This had a positive impact, so we can add one more. Add A3; check accuracy and coverage again: the coverage is fine, but the accuracy reduced. So we do not use A3. The final rule keeps A1 and A2: if A1 = A and A2 = B then class = .... That is how you build rules in rule-based classification when using the direct method — one condition at a time, keeping each condition that improves the rule and dropping each one that hurts it.

8.11.3 Entropy as a Rule-Quality Measure

Besides accuracy and coverage, the class shows entropy used as the quality criterion for rule growth. Start with one attribute and check the quality of the rule; suppose the entropy of the rule is 90%. Add another attribute: if the entropy is reduced to 80%, it is good — the rule has become purer — so keep going. Add one more attribute: now the entropy of the rule increased, so we stop and do not consider the third attribute. Whichever measure we use — accuracy, coverage, entropy — the loop is the same: add an attribute only if it improves the rule, and stop when the improvement stops.

Formalize the CN2 loop. Let $r^{(0)} = \emptyset \to y$ be the empty rule, and let $q (\cdot)$ be the quality measure — accuracy, coverage, or entropy. The loop: form the candidate $r^{(t + 1)} = r^{(t)} \land (A_{j} = v_{j})$ , compute $q (r^{(t + 1)})$ , and accept the new conjunct if and only if the measure improves — for entropy, decreases, because a purer rule has lower entropy (in the lecture's numbers, entropy falling from 90% to 80% is an improvement); for accuracy or coverage, increases. Otherwise try another candidate or stop. One rule is built this way; the next rule restarts from empty.

Reference notes. The book describes CN2 as growing rules general-to-specific (start with an empty antecedent, add conjuncts that increase quality), evaluating candidates with entropy and a likelihood-ratio statistic, and — instead of greedy one-best search — keeping the k best partial rules in a beam search to avoid committing to a bad early conjunct. The lecture's "start empty, add one attribute, measure" loop is exactly the general-to-specific strategy.

Worked example: A1, A2, A3 traced with real numbers. Write rule R1 for a two-class dataset.

Null rule: fires everywhere; accuracy equals the class prior, say 50%.
Add A1 = A: high coverage, accuracy still 50% — too broad, no better than guessing.
Add A2 = B: coverage shrinks, accuracy rises to, say, 85% — positive impact, keep A2 = B.
Try adding A3: coverage is fine but accuracy drops back to 70% — negative impact, drop A3.
Final answer: if A1 = A and A2 = B then class = ... — the rule that maximized quality.

Sense-check: every kept conjunct pulled the rule toward purity; the dropped one pulled it back, so the loop did exactly its job. Entropy version of the same trace: with one attribute the entropy is 90% (impure); adding the second drops it to 80% (purer — keep); the third raises it again (worse — stop). Same decisions, different measure.

Pitfalls.

Mixing the two scales across iterations: entropy goes down when the rule improves; accuracy goes up. Decide your measure first and keep it for the whole loop.
Adding a condition that only improves training accuracy: like forward selection, the greedy loop can overfit — a conjunct that looks great on training data may not generalize; the reference book stops growth early and prunes with validation data.
Restarting the next rule with a non-empty rule: each rule starts from the null set — otherwise rules overlap and mutual exclusion is lost.

Recap + bridge. CN2 formalizes rule growing: start empty, add one condition at a time, keep only the improvements, stop when the measure stops improving — the forward-selection spirit from the feature-selection lecture. RIPPER runs the same loop with a different quality meter — FOIL information gain — covered next.

8.12 RIPPER and FOIL Information Gain

8.12.1 The RIPPER-Style Rule Growth

There is another algorithm with the same idea: RIPPER. Like CN2, it starts with an empty rule whose conditions list is also empty, then adds one attribute at a time, checking after each addition whether the quality of the rule improved.

The reference book's summary of RIPPER fills in the details: it grows rules general-to-specific; for a two-class problem it chooses the majority class as its default and learns rules for the minority class; for multiclass problems the classes are ordered least-frequent first, the least frequent being learned first and the most frequent being kept as the default class; it stops adding conjuncts when the rule starts covering negative examples; it prunes each rule against a validation set, removing the most recently added conjuncts while the validation metric $(p - n) / (p + n)$ improves (where $p$ and $n$ are the positive and negative validation examples the rule covers); and it stops adding rules when the minimum description length cost exceeds 64 bits or a rule's validation error exceeds 50%. The lecture's framing stays closer to the loop: start with an empty rule, add one attribute at a time, and keep each addition only if the rule's quality improved.

8.12.2 FOIL Information Gain as the Quality Measure

To check rule quality, we can use FOIL information gain — the combined measure mentioned with coverage and accuracy. The rule is grown until the quality gain stops. So the direct method family reduces to one loop: empty rule, add conditions one by one, measure quality after each addition, keep the additions that improve the rule, and stop when the rule is satisfying enough.

Formalize: FOIL information gain. Suppose the current rule $r : A \to +$ covers $p_{0}$ positive and $n_{0}$ negative training examples. We consider extending it with a new conjunct $B$ ; the extended rule $r^{'} : A \land B \to +$ would cover $p_{1}$ positive and $n_{1}$ negative examples. The FOIL information gain of the extension is:

$FOIL (r^{'}) = p_{1} \times (lo g_{2} \frac{p _{1}}{p _{1} + n _{1}} - lo g_{2} \frac{p _{0}}{p _{0} + n _{0}})$

Every symbol: $p_{0}, n_{0}$ — positives and negatives covered before the addition; $p_{1}, n_{1}$ — covered after the addition; $p_{1} / (p_{1} + n_{1})$ — the extended rule's accuracy (fraction of covered tuples that are positive); $p_{0} / (p_{0} + n_{0})$ — the current rule's accuracy; $lo g_{2}$ — the base-2 logarithm. The first log term measures how pure the extended rule is; the second subtracts the purity already present, so the gain is the improvement the new conjunct earns. The multiplier $p_{1}$ makes the measure proportional to support — how many positive tuples the rule actually covers. This is the combined coverage-and-accuracy measure promised in Section 8.9.

Why both factors matter. A conjunct that shrinks the rule to one perfect positive tuple has a great purity term, but $p_{1} = 1$ keeps the gain tiny. A conjunct that keeps 500 positives but adds 300 negatives barely raises the purity term. FOIL gain scores high only when a conjunct delivers many positives and near-purity at the same time.

Worked example: FOIL gain with real numbers. Training set: 40 positive, 60 negative. The current rule has an empty antecedent and covers all of them: $p_{0} = 40$ , $n_{0} = 60$ .

Candidate conjunct B1 — the extended rule covers 30 positive, 10 negative ( $p_{1} = 30$ , $n_{1} = 10$ ):

$FOIL (B_{1}) = 30 \times (lo g_{2} \frac{30}{40} - lo g_{2} \frac{40}{100}) = 30 \times (- 0.4150 + 1.3219) = 30 \times 0.9069 \approx 27.2$

Candidate conjunct B2 — the extended rule covers 2 positive, 0 negative ( $p_{1} = 2$ , $n_{1} = 0$ ):

$FOIL (B_{2}) = 2 \times (lo g_{2} \frac{2}{2} - lo g_{2} \frac{40}{100}) = 2 \times (0 + 1.3219) \approx 2.6$

Final answer: B1 wins — FOIL gain ≈ 27.2 vs ≈ 2.6 — despite B2's perfect 100% accuracy.

Sense-check: B1 adds 27 weighted units of useful separation across 30 tuples; B2 is perfectly pure but barely touches the data, so its gain is small — the 95%-versus-100% lesson from Section 8.9, now built into the algorithm's own quality measure.

Pitfalls.

Reading the log ratio backwards: the term is $lo g_{2} (new purity) - lo g_{2} (old purity)$ — the improvement, not the final purity.
Forgetting the $p_{1}$ multiplier: without it, a one-tuple perfect rule would score the highest possible purity gain; with it, FOIL gain stays tiny.
Confusing the measures: RIPPER uses FOIL gain to pick conjuncts; CN2 (as described in the reference) uses entropy and a likelihood-ratio statistic — but both follow the same add-if-improves loop.

Recap + bridge. RIPPER grows rules with the same empty-rule loop as CN2, powered by FOIL information gain — a combined quality measure that needs both many positives and high purity to score well. That closes the direct-method family: sequential covering (8.10), CN2 (8.11), RIPPER with FOIL gain (8.12) — three names, one loop.

Exam Guidance Summary

Exam note: Everything covered in this class is part of the exam syllabus — the session opened by saying whatever we covered is exam material, so all sections above (rules, coverage and accuracy, direct and indirect methods, tree extraction, mutual exclusion and exhaustiveness, simplification, conflict resolution, default rules, sequential covering, CN2, RIPPER/FOIL) are in scope.

Question style: expect good theoretical questions and numerical questions. Do not expect generic "what is data mining" type questions — the exam will use logical questions and numericals so you can visualize things and solve properly.
Numerical checklist: be able to compute coverage ( $n_{co v er} /∣ D ∣$ ) and accuracy ( $n_{cor r ec t} / n_{co v er}$ ) for a rule on a given dataset, exactly as in the buys-computer worked example (5/14 ≈ 35%, 2/5 = 40%). Also be ready to redo the simplification numbers (4/10 = 40% coverage, 4/4 = 100% accuracy) and the tightening trace from Section 8.10.
Conceptual checklist: distinguish direct (RIPPER, CN2) from indirect (C4.5 rules) methods; explain the two implicit properties of tree-extracted rules (mutual exclusion, exhaustiveness) and what happens when simplification breaks them; name the conflict resolution strategies (size ordering, rule ordering, class-based ordering, majority voting) and the default-rule fallback; explain why accuracy alone (95% vs 100%) or coverage alone can mislead; walk through the sequential covering loop and the CN2-style "add one attribute, keep it only if quality improves" procedure.
Conflict-resolution drill: be ready to take a small rule set and a test tuple, mark which rules trigger, and state the prediction under (a) size ordering, (b) accuracy ordering, (c) class-based ordering — the turtle example (Section 8.7.6) is the template.
One-line memory hooks: coverage = how much of the data the rule touches; accuracy = how often it is right where it touches; tree rules are mutually exclusive and exhaustive for free; simplification breaks both; FOIL gain = support × purity improvement.

Key Industry Applications

Ordered rule evaluation in production systems — the class notes that what is typically used in existing systems is the ordered rule set: write rules R1, R2, ... and check them top-down until one triggers, rather than majority voting, because evaluating every rule for every tuple is not cost efficient. This is the pattern behind production rule engines, where a request (a loan application, a network packet, a support ticket) is pushed down an ordered rule list and the first matching rule's action executes.
Computational cost on hardware — when a rule set is built into hardware or runs on a system, every LHS comparison is actually executed and has a cost; rule simplification exists to cut those comparisons without losing prediction quality. In embedded and high-throughput settings — firewall rule tables, network access-control lists, fraud screens on payment rails — each dropped condition directly saves chip cycles per event, multiplied over millions of events.
Interpretable knowledge-style classifiers — rule-based classifiers predict by readable if-then statements (e.g., the reptile-versus-amphibian example), the style of rule systems used where the reasoning behind each prediction must be explainable; the buys-computer data itself is the canonical rule-extraction teaching dataset. Regulated domains — banking credit decisions, insurance claims, medical triage — need exactly this: a prediction that can be printed out and defended line by line, which is why rule sets still sit alongside black-box models as the auditable layer.

DM Lecture 8 notes · Rule-Based Classification

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

18.1 What Is Rule-Based Classification

The if-then anatomy of a rule: antecedent, consequent, conjuncts, and when a rule is triggered.

28.2 Rule Quality: Coverage and Accuracy

The two quality measures, their formulas, and the buys-computer worked example.

38.3 Two Ways to Build Rules: Direct and Indirect

Rules written straight from data (RIPPER, CN2) versus rules extracted from a model (C4.5 rules).

48.4 Indirect Method: Rules from a Decision Tree

One rule per root-to-leaf path; the rule set carries exactly the tree's information.

58.5 Two Free Properties: Mutual Exclusion and Exhaustiveness

Why tree-transcribed rules trigger at most one and at least one rule for every tuple.

68.6 Rule Simplification

Dropping redundant LHS conditions when coverage and accuracy stay identical, and what that breaks.

78.7 Conflict Resolution Strategies

Size ordering, rule ordering, class-based ordering, and majority voting, with the reptile-or-amphibian example.

88.8 Default Rules: When No Rule Fires

The empty-antecedent fallback rule that guarantees one prediction per tuple.

98.9 Accuracy and Coverage Alone Can Mislead

The 95%-versus-100% worked example and why combined measures like FOIL gain are needed.

108.10 Direct Method: Sequential Covering

Learning rules one at a time from the data and removing the tuples each rule covers.

118.11 Growing One Rule: The CN2 Algorithm

The null-rule loop: add one attribute at a time, keep it only while quality improves.

128.12 RIPPER and FOIL Information Gain

FOIL information gain as the combined support-and-purity quality measure behind RIPPER.

13Exam Guidance Summary

Question styles to expect and a numerical and conceptual preparation checklist.

14Key Industry Applications

Ordered rule evaluation, hardware cost of rule comparisons, and explainable rule systems.

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

What Is Rule-Based Classification

Must-know: A rule (A1=v1) AND ... AND (Ak=vk) -> y: antecedent on the left implies the class on the right; triggered/covers/satisfied are synonyms for the LHS holding.

$(A_{1} = v_{1}) \land (A_{2} = v_{2}) \land \dots \land (A_{k} = v_{k}) \to y$

⚠️ Top pitfall: Reading AND as OR (all conditions must hold), or putting the class on the left-hand side.

Self-check: Does the rule 'if age = youth and student = yes then buys_computer = yes' fire for a 35-year-old student?

Connects to: 8.2, 8.8

Rule Quality: Coverage and Accuracy

Must-know: Compute both ratios with the right denominators: coverage divides by |D|, accuracy divides by n_cover. Buys-computer: R1 coverage 5/14 ~ 35%, accuracy 2/5 = 40%.

$coverage (R) = \frac{n _{co v er}}{∣ D ∣}, accuracy (R) = \frac{n _{cor r ec t}}{n _{co v er}}$

⚠️ Top pitfall: Swapping denominators: coverage over n_cover or accuracy over |D|.

Self-check: A rule triggers on 4 of 10 tuples and is right on 3: what are coverage and accuracy?

Connects to: 8.1, 8.6, 8.9

Two Ways to Build Rules: Direct and Indirect

Must-know: Direct = rules from data (RIPPER, CN2); indirect = rules from a model (C4.5 rules from a decision tree).

⚠️ Top pitfall: Attributing the wrong algorithm family: C4.5 rules is indirect, RIPPER/CN2 are direct.

Self-check: Which method classifies RIPPER, CN2, and C4.5 rules?

Connects to: 8.4, 8.10, 8.11, 8.12

Indirect Method: Rules from a Decision Tree

Must-know: Number of rules = number of leaf nodes; each rule walks a root-to-leaf path and ANDs the conditions; nothing added, nothing lost in the conversion.

⚠️ Top pitfall: Writing one rule per internal node instead of per leaf.

Self-check: A tree with five leaves yields how many rules?

Connects to: 8.5, 8.6

Two Free Properties: Mutual Exclusion and Exhaustiveness

Must-know: Mutual exclusion: no two tree rules fire on the same tuple. Exhaustiveness: at least one rule fires per tuple. Both are free because paths are disjoint and cover all leaves.

⚠️ Top pitfall: Assuming hand-written or simplified rule sets keep these properties.

Self-check: Why can no tuple trigger two different root-to-leaf paths?

Connects to: 8.6, 8.7, 8.8

Rule Simplification

Must-know: Simplify only when quality is unchanged (here 4/10 coverage, 4/4 accuracy before and after); then re-check mutual exclusion and exhaustiveness.

$coverage = \frac{4}{10} = 40%, accuracy = \frac{4}{4} = 100%$

⚠️ Top pitfall: Simplifying without recomputing quality or re-checking the two free properties.

Self-check: Why is 'if marital status = married then class = no' as good as the two-condition rule?

Connects to: 8.5, 8.7, 8.8

Conflict Resolution Strategies

Must-know: Four strategies: size ordering (most conditions on top), rule ordering (any quality measure, first fired wins), class-based ordering (bundles by predicted class), majority voting (expensive, usually avoided). Turtle tuple triggers R4 (reptile) and R5 (amphibian); R4 first in order, so prediction is reptile.

⚠️ Top pitfall: Naive accuracy ordering lets a one-tuple 100% rule outrank a 40-tuple 95% rule.

Self-check: Two rules fire for a tuple predicting different classes: which strategy says to check R1, R2, ... top-down until one triggers?

Connects to: 8.5, 8.6, 8.9

Default Rules: When No Rule Fires

Must-know: Default rule = empty antecedent, fires for anything uncovered; default class usually the majority class (buys-computer: yes, 9 of 14); its only guarantee is at least one rule per tuple, not quality.

$r_{d} : () \to y_{d}$

⚠️ Top pitfall: Believing the default rule is high quality, or letting it override a triggered rule.

Self-check: What does the default rule guarantee, and what does it not guarantee?

Connects to: 8.6, 8.7

Accuracy and Coverage Alone Can Mislead

Must-know: Accuracy alone overrates tiny rules (R2: 2/2 = 100% on 2 tuples); coverage alone underrates them (R1: 38/40 = 95% on 40 tuples is the better rule). Read both, or use a combined measure like FOIL gain.

⚠️ Top pitfall: Ranking rules by accuracy only, ignoring coverage.

Self-check: Why is a 95%-accurate rule on 40 tuples better than a 100%-accurate rule on 2 tuples?

Connects to: 8.2, 8.7, 8.12

Direct Method: Sequential Covering

Must-know: Loop: start empty rule -> Learn-One-Rule adds attributes while quality improves -> remove covered tuples -> next rule; first rule should cover many same-class tuples; default rule predicts the leftover class (negative in the example).

⚠️ Top pitfall: Forgetting to remove covered tuples before learning the next rule.

Self-check: After R1 covers the positive batch, what happens to those tuples?

Connects to: 8.3, 8.11, 8.12

Growing One Rule: The CN2 Algorithm

Must-know: CN2 loop: null rule -> add A1=A (accuracy 50%, too broad) -> add A2=B (coverage down, accuracy up: keep) -> try A3 (accuracy down: drop). Final rule: if A1=A and A2=B then class = ... . With entropy, a decrease (90% to 80%) is the improvement.

⚠️ Top pitfall: Mixing measures across iterations: entropy decreases when the rule improves; accuracy increases.

Self-check: In the A1/A2/A3 example, why is A3 not used in the final rule?

Connects to: 8.10, 8.12

RIPPER and FOIL Information Gain

Must-know: FOIL gain = p1 x (log2(p1/(p1+n1)) - log2(p0/(p0+n0))): purity improvement times support. RIPPER: general-to-specific growth, FOIL gain for conjunct choice, majority class as default, MDL stopping.

$FOIL (r^{'}) = p_{1} \times (lo g_{2} \frac{p _{1}}{p _{1} + n _{1}} - lo g_{2} \frac{p _{0}}{p _{0} + n _{0}})$

⚠️ Top pitfall: Dropping the p1 multiplier or reading the log ratio backwards.

Self-check: Why does a perfect conjunct covering 2 positives score lower FOIL gain than one covering 30 positives at 75% purity?

Connects to: 8.9, 8.11

Exam Guidance Summary

Must-know: Expect theoretical and numerical questions; practice the buys-computer coverage/accuracy numbers and the conceptual distinctions (direct vs indirect, mutual exclusion vs exhaustiveness, four conflict strategies, default rule, 95%-vs-100% lesson).

⚠️ Top pitfall: Studying generic 'what is data mining' questions instead of logical and numerical rule questions.

Self-check: Name the four conflict resolution strategies and the fallback when no rule fires.

Connects to: 8.1, 8.2, 8.7

Previous LectureLecture 07 · Decision Trees

Next LectureLecture 09 · K-Nearest Neighbor and Ensemble Methods

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

8.1 What Is Rule-Based Classification

8.1.1 The Core Idea: Rules That Predict

8.1.2 The Anatomy of a Rule

8.1.3 When Is a Rule Triggered?

8.2 Rule Quality: Coverage and Accuracy

8.2.1 The Two Measures

8.2.2 Worked Example: Rule R1 on the Buys-Computer Data

8.2.3 What Coverage and Accuracy Count

8.3 Two Ways to Build Rules: Direct and Indirect

8.3.1 Direct Method

8.3.2 Indirect Method

8.4 Indirect Method: Rules from a Decision Tree

8.4.1 The Procedure

8.4.2 Example: Five Leaf Nodes, Five Rules

8.4.3 The Rule Set Carries All Tree Information

8.5 Two Free Properties: Mutual Exclusion and Exhaustiveness

8.5.1 Mutual Exclusion

8.5.2 Exhaustiveness

8.5.3 Example: Four Rules from a Refund Tree

8.6 Rule Simplification

8.6.1 Why Simplify

8.6.2 Worked Example: Dropping a Redundant Condition

8.6.3 What Simplification Breaks

8.7 Conflict Resolution Strategies

8.7.1 The Two Problems

8.7.2 Size Ordering

8.7.3 Rule Ordering

8.7.4 Class-Based Rule Ordering

8.7.5 Majority Voting: The Alternative Usually Avoided

8.7.6 Worked Example: Reptile or Amphibian?

8.8 Default Rules: When No Rule Fires

8.8.1 The Default Rule Idea

8.8.2 What the Default Rule Guarantees

8.9 Accuracy and Coverage Alone Can Mislead

8.9.1 Worked Example: 95% versus 100%

8.9.2 Combining Measures

8.10 Direct Method: Sequential Covering

8.10.1 The Algorithm

8.10.2 Visual Walkthrough: Covering the Data Rule by Rule

8.10.3 From a Broad Rule to a Tight Rule

8.11 Growing One Rule: The CN2 Algorithm

8.11.1 Incremental Attribute Addition

8.11.2 Worked Example: A1, A2, A3

8.11.3 Entropy as a Rule-Quality Measure

8.12 RIPPER and FOIL Information Gain

8.12.1 The RIPPER-Style Rule Growth

8.12.2 FOIL Information Gain as the Quality Measure

Exam Guidance Summary

Key Industry Applications

DM Lecture 8 notes · Rule-Based Classification

Sections Breakdown

Exam Revision Notes

What Is Rule-Based Classification

Rule Quality: Coverage and Accuracy

Two Ways to Build Rules: Direct and Indirect

Indirect Method: Rules from a Decision Tree

Two Free Properties: Mutual Exclusion and Exhaustiveness

Rule Simplification

Conflict Resolution Strategies

Default Rules: When No Rule Fires

Accuracy and Coverage Alone Can Mislead

Direct Method: Sequential Covering

Growing One Rule: The CN2 Algorithm

RIPPER and FOIL Information Gain

Exam Guidance Summary

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat