Sequential covering for rule induction

Sequential covering is a direct method of rule induction: it learns one rule at a time, removes the training records covered by that rule, and repeats on the remaining records until no more good rules can be found. It is the basis of AQ, CN2, RIPPER and FOIL.

Algorithm

R = { }                         (rule set)
repeat for each class c:
    while stopping condition not met:
        r = Learn-One-Rule(Training set, c)
        remove records covered by r from the training set
        add r to R
Add a default rule (majority class) and return R

Learn-One-Rule (rule growing)

Start with the empty rule (IF TRUE THEN class c) and add the attribute test that best improves rule quality (e.g. FOIL's information gain or accuracy), until the rule is accurate enough. A rule is then pruned if needed. Rules are added until the stopping condition is met, such as no records left or the quality of a new rule falling below a threshold.

All records ----> rule R1 covers some --> remove
Rest of records -> rule R2 covers some --> remove
Rest ...                                  --> default rule

Characteristics of a rule-based classifier

• Mutually exclusive rules: a record triggers at most one rule. If not, conflict resolution (ordering) is used.
• Exhaustive rules: every record is covered by some rule; otherwise a default rule is used.
• Rules can be ordered (decision list) or unordered (voting).
• Expressiveness is about equal to a decision tree, and rules are easy to interpret and quick to apply to new records.
• Can handle imbalanced classes, and can be built without building the tree first.