Sequential Covering Method

Extracts IF-THEN Rules for Classification directly from training data. It works by sequentially generating rules and removing positive target tuples that satisfy the generated rule.

Now rules are being generated by, at each iteration, finding the best predicate $p$ according to the FOIL_Gain measure and adding it to the current rule if it exceeds a given threshold.

$\text{FOIL Gain}={\mathrm{pos}}^{\prime }\left({\log }_2\frac{{\mathrm{pos}}^{\prime }}{{\mathrm{pos}}^{\prime }+{\text{ neg }}^{\prime }}-{\log }_2\frac{\text{ pos }}{\text{ pos }+\text{ neg }}\right).$ This measure favors rules with high Accuracy and rules which cover many positive tuples.

Of course this method can also lead to Overfitting. Thus, rules for which FOIL_Prune is higher for the pruned version, have to be pruned (removing a conjunct from the rule).

$\text{ FOIL Prune }(R)=\frac{\text{ pos }-\text{ neg }}{\text{ pos }+\text{ neg }}$

Algorithm Examples

• FOIL
• AQ
• CN2
• RIPPER

Visual