Improving Classification Accuracy by Mining Deterministic and Frequent Rules

Patterns underlying the data sometimes take the form of IF conditions THEN outcome. However, not all the classifiers can detect such rules, resulting in compromised classification accuracy. In this paper we proposed an Add-on Rule-based Classifier (ARC) that can be paired with any existing classifier (base). The idea of ARC is improving the accuracy of the base by 1) mining deterministic and frequent rules, and 2) using such rules to assist the base in classification. Key novelty includes 1) a greedy search algorithm that identifies the rules by alternating between adding the ``best'' condition and removing the ``worst", and 2) new heuristics for selecting the best and worst conditions. We theoretically proved that rules detected by ARC are sound, complete, and minimal, indicating that ARC will almost never degrade the accuracy of the base, but instead, could often improve it. To experimentally verify this claim, we paired ARC with 9 leading classifiers and tested the ensembles on 12 UCI datasets. Empirical results show that, ARC never lowers the accuracy of the base and, more importantly, usually increases it (where some of the increases are statistically significant), echoing what we theoretically proved.