A methodology for trading off size and accuracy in sets of classification rules for numerical domains.
Neal Rothleder · Deep Blue (University of Michigan) · 1997
This thesis investigates a method for merging classification rules in order to simplify them and reduce their number. Classification rules are commonly used to model a set of data in order to understand the underlying structure of those data, as well as classify future examples from the same domain. Under the proper set of constraints, particularly that each domain attribute is ordered, it is possible to cast the classification rules as specifying class-labeled regions in a Euclidean space of examples. In particular, rules generated from decision trees can be viewed in this light. It is possible to take advantage of this spatial view of the rules and approximate a group of close rules with a single, more general rule. This rule merging reduces the number of rules, and makes them easier to understand and communicate, although it generally increases the classification error. When applied to decision tree rules, rule merging is able to overcome some of the shortcomings inherent in decision trees, and in some cases increase the classification accuracy while reducing the total number of rules. An implementation of rule merging which performs exhaustive search was tested, and produced very encouraging results. Its high computational cost, however, makes it unsuitable for practical use. The final Merge algorithm employs a greedy search and uses a volume-based heuristic measure to estimate rule accuracy. Using a variety of natural and artificial data sets, the Merge algorithm has been empirically compared with traditional decision tree pruning. Merge was fairly competitive with pruning in that it produced reduced sets of rules with only slightly less accuracy. More importantly, when a hybrid approach combining the two techniques was tested, it consistently achieved better reduction, with no loss of accuracy, than either approach alone. A qualitative analysis of the behavior of the Merge algorithm indicates that overall trends in the reduction/accuracy performance appear directly related to the different types of merges available to the algorithm as it progresses.