A method for finding minimal sets of features adequately describing discrete information objects

摘要

One of the classical Data Mining problems is the problem of classifying new objects on the basis of available information when the information associated with these objects does not allow identifying them unambiguously as elements of some set. In such cases using rough sets theory is often an effective solution. This theory operates with such concepts as "indiscernible" elements and relations. A rough set is characterized by lower and upper approximations for finding which the authors earlier suggested an original algebraic method. The given method uses only logic operations, which makes the process of searching logic rules very quick and efficient.rnThe upper and lower approximations of a rough set allow describing elements of this set as completely as it is possible from the viewpoint of available information. In this connection it seems interesting and important to find irreducible sets of features describing a rough set with the same "precision" as with the help of a full set of features (so called reducts). This problem is quite difficult and complicated and at present it does not have good solutions. Our paper continues research carried out by the authors earlier and we suggest a method for finding reducts based on eliminating non-salient features in the reverse order of their importance. The suggested procedure allows us to avoid exhaustive searching by extracting a predefined number of most significant reducts. In this paper we consider arbitrary features taking on their values from finite sets.