Minimal approximate hitting sets and rule templates

A set S that has a non-empty intersection with every set in a collection of sets C is called a hitting set of C. If no elements can be removed from S without violating the hitting set property, then we say that S is minimal. Several interesting problems can in part be formulated as that of having to find one or more minimal hitting sets. Many of these problems require proper solutions, but sometimes approximate solutions suffice. We define an r-approximate hitting set as a set that intersects at least a fraction r of the sets in C. This notion is extended to the case, where C is a weighted multiset, and properties of I are explored with respect to simplification of C by absorption of supersets, Also, approximations of reducts from rough set theory are defined by means of minimal r-approximate hitting sets, and some links to the notion of dynamic reducts are established. The most common use of reducts are as templates for the generation of minimal classification rules from empirical data. A genetic algorithm is devised to compute r-approximate hitting sets, and applied to induce classifiers from selected real-world databases. These classifiers are then compared to those generated from proper reducts and dynamic reducts, respectively. The improvement in discriminatory ability yielded by the r-approximate reduct based classifiers was statistically significant (p < 0.05)., Furthermore, they were smaller, i.e., had fewer rules. (C) 2000 Elsevier Science Inc. All rights reserved.