Rule Based Classification

Rule-based classifier makes use of a set of IF-THEN rules for classification. We can express a rule in the following from −
IF condition THEN conclusion
Let us consider a rule R1,

 R1: IF age = youth AND student = yes
       THEN buy_computer = yes

Rule-Based Classifier classify records by using a collection of “if…then…” rules.
(Condition) → Class Label
e.g: (BloodType = Warm) ∧ (LayEggs = Yes) → Birds
(TaxableIncome < 50K) ∨ (Refund = Yes) → Evade = No

Points to remember −

• The Left Hand Side is rule antecedent or condition
• The Right Hand Side is rule consequent
• Coverage of a rule - Fraction of records that satisfy the antecedent of a rule
• Accuracy of a rule - Fraction of records that satisfy both the antecedent and consequent of a rule.

Advantages of Rule-Based Classifiers

• As highly expressive as decision trees -Easy to interpret
• Easy to generate
• Can classify new instances rapidly
• Performance comparable to decision trees

Characteristics of Rule-Based Classifier

If we convert the result of decision tree to classification rules, these rules would be mutually exclusive and exhaustive at the same time.

Mutually exclusive rules

• Classifier contains mutually exclusive rules if the rules are independent of each other.

• Every record is covered by at most one rule.

Exhaustive rules

• Classifier has exhaustive coverage if it accounts for every possible combination of attribute values.

• Each record is covered by at least one rule.

These rules can be simplified. However, simplified rules may no longer be mutually exclusive since a record may trigger more than one rule. Simplified rules may no longer be exhaustive either since a record may not trigger any rules.

Solution to make the rule set mutually exclusive:

• Ordered rule set
• Unordered rule set – use voting schemes

Solution to make the rule set exhaustive:

• Use a default class

Ordered Rule Set

An ordered rule set is known as a decision list. Rules are rank ordered according to their priority. For example, when a test record is presented to the classifier, it is assigned to the class label of the highest ranked rule it has triggered. If none of the rules fired, it is assigned to the default class.

That is, if more than one rule is triggered, need conflict resolution:

• Size ordering - assign the highest priority to the triggering rules that has the “toughest” requirement (i.e., with the most attribute test)

• Class-based ordering - decreasing order of prevalence or misclassification cost per class

• Rule-based ordering (decision list) - rules are organized into one long priority list, according to some measure of rule quality or by experts

Building Rules Through Direct Method

Direct Method extract rules directly from data. Sequential Covering such as CN2 Algorithm and RIPPER Algorithm are common direct methods for building classification rules.

Take Ripper method as example. For 2-class problem, choose one of the classes as positive class, and the other as negative class, learn rules for positive class, and negative class will be default class. For multi-class problem, order the classes according to increasing class prevalence (fraction of instances that belong to a particular class), and learn the rule set for smallest class first, treat the rest as negative class. Repeat with next smallest class as positive class.

Sequential Covering

• Start from an empty rule
• Grow a rule using the Learn-One-Rule function (Rule Growing)
• Remove training records covered by the rule (Instance Elimination)
• Repeat Step (2) and (3) until stopping criterion is met
• (Optional) Rule Pruning

Rule Growing

General-to-Specific Strategy (Ripper Algorithm)

• Start from an empty rule: {} →→ class

• Add conjuncts that maximizes FOIL’s information gain measure:

Gain(R0,R1)=t(logp1p1+n1–logp0p0+n0)Gain(R0,R1)=t(logp1p1+n1–logp0p0+n0)

• R0R0: {} →→ class (initial rule)

• R1R1: {A} →→ class (rule after adding conjunct)

• tt: number of positive instances covered by both R0R0 and R1R1

• p0p0: number of positive instances covered by R0R0

• n0n0: number of negative instances covered by R0R0

• p1p1: number of positive instances covered by R1R1

• n1n1: number of negative instances covered by R1R1

Specific-to-General Strategy (CN2 Algorithm)

1. Start from an empty conjunct: {}
2. Add conjuncts that minimizes the entropy measure: {A}, {A,B}, …
3. Determine the rule consequent by taking majority class of instances covered by the rule

Instance Elimination

• Why do we need to eliminate instances? Otherwise, the next rule is identical to previous rule
• Why do we remove positive instances? Ensure that the next rule is different
• Why do we remove negative instances? Prevent underestimating accuracy of rule

Rule Evaluation

Assume $n_n$ is Number of instances covered by rule, $n_c$ is Number of instances covered by rule, $k_k$ is Number of classes, and $p_p$ is Prior probability.

Accuracy = $\dfrac {n_c}{n_n}$

Laplace = $\dfrac {(n_c+1)}{(n+k)}$

M−estimate = $\dfrac {(n_c+k_p)}{(n+k)}$

Example 1:
Consider a training set that contains 60 positive examples and 100 negative examples. Rule r1 covers 50 positive examples and 5 negative examples Rule r2 covers 2 positive examples and no negative examples.

Ans:
Accuracy of r1=50/55=90.9%
Accuracy of r2=2/2=100%

Stopping Criterion

Compute the gain, if gain is not significant, discard the new rule.

Rule Pruning

Rule Pruning is similar to post-pruning of decision trees.

Reduced Error Pruning :

1. Remove one of the conjuncts in the rule
2. Compare error rate on validation set before and after pruning
3. If error improves, prune the conjunct