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

Consequently, we obtain {Ph, Li} as the unique L ≥ -reduct, {Ma, Ph} as the
unique L ≤ -reduct and {Ma, Li} as the unique L-reduct. Moreover, {Ph, Li}

∪

{Ma,

Ph} = {Ma, Ph, Li} = C is the unique U-reduct, {Ph, Li} ∪ {Ma, Li} = {Ma, Ph,

C is the unique LL ≥ -reduct, and {Ma, Ph}

Li} = ∪ {Ma, Li} = {Ma, Ph, Li} = C

is the unique LL ≤ -reduct.

7.5 Concluding Remarks

In this chapter, we have studied structure-based attribute reduction as a rough set
approach to the attribute selection/reduction problem. We have proposed several
concepts of structure-based reducts. In the rough set model, there are 2 different
types of reducts, U-reducts and L-reducts. U-reducts preserve generalized decisions
∂ C (

u ) for all objects u ∈ U , while L-reducts do so for all certain classified objects u ,

namely, 1. The authors studied refinement of the hierarchy of structure-

based reducts (Fig. 7.1 ) by interpolating reducts which preserve objects u whose
generalized decisions are at most k , namely,

| ∂ C ( u ) |=

k [ 24 ]. The parameter k
provides a trade-off between the size of a reduct and preserved information.
In VPRSM, because approximations may not be monotone with respect to the
set inclusion of condition attributes, classifications of some objects become precise
by reducing condition attributes. From that viewpoint, the authors have proposed
enhancing reducts [ 21 ], which do not preserve but make classification more precise
than that of all condition attributes.
Attribute reduction have been also studied in other extensions of the rough set
model, e.g. tolerance-based RSM [ 44 ], RSM for decision tables with missing val-
ues [ 29 , 30 ], Bayesian RSM [ 47 ], fuzzy RSM [ 27 , 28 ], and variable precision
DRSM [ 26 ]. However, in general, extensions of the rough set model drop some
important properties of approximations. Therefore, in such models, reducts may not
be represented by Boolean functions.
When a measure

| ∂ C ( u ) |≤

(e.g. Eq. 7.8 ) representing a part of consistency of a rough
set model is given, we can define approximate measure-based reducts as follows:
A

ʳ

ↆ C is an approximate reduct if ʳ A ≥ ( 1 − ʵ)ʳ C or ʳ A ≥ ʳ C − ʵ for a small

ʵ ≥ 0. Several measures used for approximate measure-based reducts have been

proposed, e.g. based on the number of discerned object pairs or the information
entropy [ 45 , 46 , 51 ]. Comparingwith structure-based reducts, approximatemeasure-
based approach can easily control size of reducts, but we cannot expect which parts
of the structure of the rough set model deteriorate by reduction.
We show that reducts are (approximately) represented by prime implicants of
Boolean functions (or pairs of Boolean functions). To compute all reducts of a par-
ticular type, we solve the dualization problem(more precisely, positiveDNF (or CNF)
dualization) of the corresponding Boolean function. It probably cannot be solved in
polynomial time (it can be solved in quasi-polynomial time with respect to the sizes
of the input and the output [ 9 ]).