598 Y.H. Qian et al. / Artificial Intelligence 174 (2010) 597–618
measures can be divided into two main categories: distance-based measures and consistency-based measures [20]. Rough
set theory by Pawlak [33–36] is a relatively new soft computing tool for the analysis of a vague description of an object,
and has become a popular mathematical framework for pattern recognition, image processing, feature selection, neuro-
computing, data mining and knowledge discovery from large data sets [7,11,31]. Attribute reduction in rough set theory
offers a systematic theoretic framework for consistency-based feature selection, which does not attempt to maximize the
class separability but rather attempts to retain the discernible ability of original features for the objects from the universe
[13,14,53].
Generally speaking, one always needs to handle two types of data, viz. those that assume numerical values and symbolic
values. For numerical values, there are two types of approaches. One relies on fuzzy rough set theory, and the other is
concerned with the discretization of numerical attributes. In order to deal with numerical attributes or hybrid attributes,
several approaches have been developed in the literature. Pedrycz and Vukovich regarded features as granular rather than
numerical [37]. Shen and Jenshen generalized the dependency function in classical rough set framework to the fuzzy case
and proposed a fuzzy-rough QUICKREDUCT algorithm [13,14,48]. Bhatt and Gopal provided a concept of fuzzy-rough sets
formed on compact computational domain, which is utilized to improve the computational efficiency [3,4]. Hu et al. pre-
sented a new entropy to measure of the information quantity in fuzzy sets [21] and applied this particular measure to
reduce hybrid data [22]. Data discretization is another important approach to deal with numerical values, in which we usu-
ally discretize numerical values into several intervals and associate the intervals with a set of symbolic values, see [5,28]. In
the “classical” rough set theory, the attribute reduction method takes all attributes as those which assume symbolic values.
Through preprocessing of original data, one can use the classical rough set theory to select a subset of features that is the
most suitable for a given recognition problem.
In the last twenty years, many techniques of attribute reduction have been developed in rough set theory. The concept
of the
β-reduct proposed by Ziarko provides a suite of reduction methods in the variable precision rough set model [60].
An attribute reduction method was proposed for knowledge reduction in random information systems [57]. Five kinds of
attribute reducts and their relationships in inconsistent systems were investigated by Kryszkiewicz [18], Li et al. [24] and
Mi et al. [29], respectively. By eliminating some rigorous conditions required by the distribution reduct, a maximum distri-
bution reduct was introduced by Mi et al. in [29]. In order to obtain all attribute reducts of a given data set, Skowron [49]
proposed a discernibility matrix method, in which any two objects determine one feature subset that can distinguish them.
According to the discernibility matrix viewpoint, Qian et al. [42,43] and Shao et al. [47] provided a technique of attribute
reduction for interval ordered information systems, set-valued ordered information systems and incomplete ordered infor-
mation systems, respectively. Kryszkiewicz and Lasek [17] proposed an approach to discovery of minimal sets of attributes
functionally determining a decision attribute. The above attribute reduction methods are usually computationally very ex-
pensive, which are intolerable for dealing with large-scale data sets with high dimensions. To support efficient attribute
reduction, many heuristic attribute reduction methods have been developed in rough set theory, cf. [19,20,22,25,26,39,52,
54–56]. Each of these attribute reduction methods can extract a single reduct from a given decision table.
1
For convenience,
from the viewpoint of heuristic functions, we classify these attribute reduction methods into four categories: positive-region
reduction, Shannon’s entropy reduction, Liang’s entropy reduction and combination entropy reduction. Hence, we review
only four representative heuristic attribute reduction methods.
(1) Positive-region reduction
The concept of positive region was proposed by Pawlak in [33], which is used to measure the significance of a condition
attribute in a decision table. While the idea of attribute reduction using positive region was originated by J.W. Grzymala-
Busse in [9] and [10], and the corresponding algorithm ignores the additional computation required for selecting significant
attributes. Then, Hu and Cercone [19] proposed a heuristic attribute reduction method, called positive-region reduction,
which remains the positive region of target decision unchanged. The literature [20] gave an extension of this positive-
region reduction for hybrid attribute reduction in the framework of fuzzy rough set. Owing to the consistency of ideas and
strategies of these methods, we regard the method from [19] as their representative. These reduction methods are the first
attempt to heuristic attribute reduction algorithms in rough set theory.
(2) Shannon’s entropy reduction
The entropy reducts have first been introduced in 1993/1994 by Skowron in his lectures at Warsaw University. Based
on the idea, Slezak introduced Shannon’s information entropy to search reducts in the classical rough set model [50–52].
Wang et al. [54] used conditional entropy of Shannon’s entropy to calculate the relative attribute reduction of a decision
information system. In fact, several authors also have used variants of Shannon’s entropy or mutual information to measure
uncertainty in rough set theory and construct heuristic algorithm of attribute reduction in rough set theory [22,55,56]. Here
1
The attribute reduct obtained preserves a particular property of a given decision table. However, as Prof. Bazan said, from the viewpoint of stabilityof
attribute reduct, the selected reduct may be of bad quality [1,2]. To overcome this problem, Bazan developed a method for dynamic reducts to get a stable
attribute reduct from a decision table. How to accelerate the method for dynamic reducts is an interesting topic in further work.
