Databases Reference
In-Depth Information
4 Lower and Upper Approximations
For completely specified decision tables lower and upper approximations are
defined using the indiscernibility relation. Any finite union of elementary sets
of
B
is called a
B-definable set
.Let
X
be any subset of the set
U
of all cases.
The set
X
is called concept and is usually defined as the set of all cases
defined by a specific value of the decision. In general,
X
is not a
B
-definable
set. However, set
X
may be approximated by two
B
-definable sets, the first
one is called a
B-lower approximation
of
X
, denoted by
B
X
anddefinedas
follows
.
The second set is called an
B-upper approximation
of
X
, denoted by
BX
anddefinedasfollows
{
x
∈
U
|
[
x
]
B
⊆
X
}
{
x
∈
U
|
[
x
]
B
∩
X
=
∅}
.
The above way of computing lower and upper approximations, by con-
structing them from singletons
x
, will be called the
first method
.The
B
-lower
approximation of
X
is the greatest
B
-definable set, contained in
X
.The
B
-upper approximation of
X
is the least
B
-definable set containing
X
.
As it was observed in [19], for complete decision tables we may use a second
method to define the
B
-lower approximation of
X
, by the following formula
B
X
=
∪{
[
x
]
B
|
x
∈
U,
[
x
]
B
⊆
X
}
,
and the
B
-upper approximation of
X
may de defined, using the second
method, by
)
.
For Table 1 and
B
=
A
,
A
-lower and
A
-upper approximations are:
BX
=
∪{
[
x
]
B
|
x
∈
U,
[
x
]
B
∩
X
=
∅
A
,
A{
3
,
5
,
6
,
7
}
=
{
3
,
7
},
A
{
1
,
2
,
4
,
8
}
=
{
1
,
2
}
{
1
,
2
,
4
,
8
}
=
{
1
,
2
,
4
,
5
,
6
,
8
}
,
A
{
3
,
5
,
6
,
7
}
=
{
3
,
4
,
5
,
6
,
7
,
8
}
.
For incompletely specified decision tables lower and upper approximations
may be defined in a few different ways. To begin with, the definition of de-
finability should be modified. Any finite union of characteristic sets of
B
is
called a
B-definable
set. Following [7], we suggest three different definitions
of approximations. Again, let
X
be a concept, let
B
be a subset of the set
A
of all attributes, and let
R
(
B
) be the characteristic relation of the incomplete
decision table with characteristic sets
K
B
(
x
), where
x
U
. Our first definition
uses a similar idea as in the previous articles on incompletely specified decision
tables [14, 15, 23-25], i.e., lower and upper approximations are sets of single-
tons from the universe
U
satisfying some properties. Thus we are defining
∈
