On Mining Instance-Centric Classification Rules

Jianyong Wang and George Karypis
IEEE Transactions on Knowledge and Data Enigneering, 2006
Download Paper
Many studies have shown that rule-based classifiers perform
well in classifying categorical and sparse high-dimensional
databases. However, a fundamental limitation with many rule-based
classifiers is that they find the rules by employing various
heuristic methods to prune the search space, and select the rules
based on the sequential database covering paradigm. As a result,
the final set of rules that they use may not be the globally best
rules for some instances in the training database. To make matters
worse, these algorithms fail to fully exploit some more effective
search space pruning methods in order to scale to large databases.

In this paper we present a new classifier, HARMONY, which directly
mines the final set of classification rules. HARMONY uses an
instance-centric rule-generation approach and it can assure for
each training instance, one of the highest-confidence rules
covering this instance is included in the final rule set, which
helps in improving the overall accuracy of the classifier. By
introducing several novel search strategies and pruning methods
into the rule discovery process, HARMONY also has high efficiency
and good scalability. Our thorough performance study with some
large text and categorical databases has shown that HARMONY
outperforms many well-known classifiers in terms of both accuracy
and computational efficiency, and scales well w.r.t. the database

This is an expanded version of the SIAM DM 2005 conference paper.
Research topics: Classification | Data mining