written 5.4 years ago by |

**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**: {} →→ classAdd 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)**

- Start from an
**empty conjunct**: {} - Add conjuncts that
**minimizes the entropy measure**: {A}, {A,B}, … - 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 :**

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