1756 Y. Qian et al. / Computers and Mathematics with Applications 55 (2008) 1754–1765
Let S = (U, A) be an information system, where U is a non-empty, finite set of objects and A is a non-empty finite
set of attributes. Let P, Q ∈ 2
A
be two attribute subsets, where 2
A
is a power set of A. By IND(P) and IND(Q), we
denote the indiscernible relations induced by P and Q, respectively. A partial relation on 2
A
is defined in [25] as
follows: P Q (Q P) if and only if, for every P
i
∈ U/IND(P), there exists Q
j
∈ U/IND(Q) such that P
i
⊆ Q
j
,
where U/IND(P) = {P
1
, P
2
, . . . , P
m
} and U/IND(Q) = {Q
1
, Q
2
, . . . , Q
n
} are partitions induced by IND(P) and
IND(Q), respectively. A partition induced by an equivalence relation provides a granulation world for describing a
target concept. Thus, a sequence of granulation worlds from coarse to fine can be determined by a sequence of attribute
sets with granulations from coarse to fine in the power set of A. The positive approximation gives the definition of the
upper and lower approximations of a target concept under a given granulation order [18]. It can be used to extract from
a given decision table decision rules with granulations from coarse to fine. The definition of the positive approximation
is as follows.
Definition 2.1 ([18]). Let S = (U, A) be an information system, X ⊆ U and P = {R
1
, R
2
, . . . , R
n
} a family of
attribute sets with R
1
R
2
· · · R
n
(R
i
∈ 2
A
). Let P
i
= {R
1
, R
2
, . . . , R
i
}, we define P
i
-upper approximation
P
i
(X) and P
i
-lower approximation P
i
(X) of P
i
-positive approximation of X as
P
i
(X) = R
i
(X),
P
i
(X) =
i
[
k=1
R
k
X
k
,
where X
1
= X and X
k
= X −
S
k−1
j=1
R
j
X
j
for k = 2, 3, . . . , n, i = 1, 2, . . . , n.
Theorem 2.1 ([18]). Let S = (U, A) be an information system, X ⊆ U and P = {R
1
, R
2
, . . . , R
n
} a family of
attribute sets with R
1
R
2
· · · R
n
(R
i
∈ 2
A
). Let P
i
= {R
1
, R
2
, . . . , R
i
}, then ∀P
i
(i = 1, 2, . . . , n), we have
P
i
(X) ⊆ X ⊆ P
i
(X),
P
1
(X) ⊆ P
2
(X) ⊆ · · · ⊆ P
n
(X).
Theorem 2.1 states that the lower approximation of the positive approximation of a target concept enlarges as a
granulation order becomes longer through adding an equivalence relation, which will help to exactly describe the
target concept.
Theorem 2.2 ([18]). Let S = (U, A) be an information system, X ⊆ U and P = {R
1
, R
2
, . . . , R
n
} a family of
attribute sets with R
1
R
2
· · · R
n
(R
i
∈ 2
A
). Let P
i
= {R
1
, R
2
, . . . , R
i
}, then ∀P
i
(i = 1, 2, . . . , n), we have
α
P
1
(X) ≤ α
P
2
(X) ≤ · · · ≤ α
P
n
(X),
where α
P
i
(X) =
|P
i
(X )|
|P
i
(X )|
is the approximation measure of X with respect to P.
The approximation measure was introduced to the positive approximation in order to describe the uncertainty of
a target concept under a granulation order [18]. From this theorem, one can see that the approximation measure of a
target concept enlarges as a granulation order becomes longer through adding an equivalence relation.
The main motivation of the positive approximation is to extend rough set approximation under static granulation to
rough set approximation under dynamic granulation and to approach a target concept by the change in a granulation
order. Through the positive approximation, one can extract from a given decision table a family of decision rules with
granulations from coarse to fine. In some practical issues, however, we need to mining decision rules on the basis of
keeping the approximation measure of a target concept. Obviously, the positive approximation appears not to be suited
for rule extracting from decision tables on the basis of keeping the approximation measure of every decision class in
decision partition on the universe. Therefore, in the next section, we introduce a notion of converse approximation in
rough set theory.
3. Converse approximation
In this section, we introduce a new set-approximation approach called a converse approximation and investigate
some of its important properties.