Structure-Based Attribute Reduction: A Rough Set Approach - Feature Selection for Data and Pattern Recognition - page 109

One of the major topics for rough set based data analysis is (relative) attribute
reduction [ 37 , 39 ]. Attribute reduction is a problem to delete redundant condition
(explanatory) attributes for the classification of the decision classes. Minimal sets
of attributes preserving a part of information of the classification are called reducts.
Reducts can be interpreted as important sets of attributes for the classification. Several
types of reducts have been proposed according to a part of the information which
should be preserved [ 23 , 36 , 43 , 45 ]. Originally, Pawlak proposed reducts preserving
the positive region [ 36 , 43 ], which is the union of all lower approximations of decision
classes, in other words, the set of all certainly classified objects. Slezak proposed
ones preserving all boundaries of decision classes [ 45 ]. One of the authors also
proposed two types of reducts, which preserve all lower approximations and all
upper approximations of decision classes, and show that they are equivalent to reducts
preserving the positive region and all boundaries, respectively [ 23 ].
Inspired by the above studies, we provide a framework to discuss attribute reduc-
tion in the rough set theory. We regard attribute reduction as removing condition
attributes with preserving some part of the lower/upper approximations of the deci-
sion classes, because the approximations summarize the classification ability of the
condition attributes. Hence, we define several types of reducts according to structures
of the approximations [ 23 , 24 ]. They are called “structure-based” reducts.
When several types of structure-based reducts are defined, we would be interested
in whether one reduct is stronger/weaker than another reduct, in other words, one
preserves more/less structure than the other. Therefore, we have investigated the
strong-weak relation among different types of structure-based reducts. As a result of
the investigation, we obtain a strong-weak hierarchy of structure-based reducts. The
strong-weak hierarchy is useful when we search the best reduct for an application,
because it provides a trade-off between the size (cost for precise classification) of a
reduct and its classification ability. It is an advantage of the variations of structure-
based reducts.
The rough set model is extended to apply to various kinds of data sets [ 12 , 16 ,
22 , 29 , 38 , 43 , 47 , 53 , 54 ]. Two important extensions of the rough set model are
the variable precision rough set model [ 53 , 54 ] and the dominance-based rough set
model [ 16 ]. The variable precision rough set model is a probabilistic extension. Given
precision parameters, requirements for lower and upper approximations are relaxed
to tolerate errors in decision tables. The dominance-based rough set model is applied
to decision tables with ordinal attributes, where decision classes are ordered and
monotonically depend on the ordinal attributes. It deals with inconsistency between
the classification of the ordinal decision classes and the monotonic dependence.
Instead of decision classes, upward unions and downward unions of decision classes
are approximated. In the extended rough set models, we have studied structure-based
reducts [ 20 , 21 , 25 , 26 , 31 ].
In the classical rough set model, it is well-known that reducts are associated
with prime implicants of a Boolean function [ 37 , 43 ]. We can efficiently enumerate
reducts by converting it to enumerating prime implicants of the Boolean function.
Like that conversion, the methodology solving a problem by solutions of a Boolean
equation is called Boolean reasoning [ 37 , 43 ]. In this chapter, we propose a unified