Reduced Complexity Rule Induction

Abstract

We present an architecture for rule induction that emphasizes compact, reduced-complexity rules. A new heuristic technique for finding a covering rule set of sample data is described. This technique refines a set of production rules by iteratively replacing a component of a rule with its single best replacement. A method for rule induction has been developed that combines this covering and refinement scheme with other techniques known to help reduce the complexity of rule sets, such as weakest-link pruning, resampling, and the judicious use of linear discriminants. Published results on several real-world datasets are reviewed where decision trees have performed relatively poorly. It is shown that far simpler decision rules can be found with predictive performance that exceeds those previously reported for various learning models, including neural nets and decision trees. 1