Databases Reference
In-Depth Information
The second possibility is to modify the subset definition of lower and upper
approximation by replacing the universe
U
from the subset definition by a
concept
X
.A
concept B
-lower approximation of the concept
X
is defined as
follows:
,
Obviously, the subset
B
-lower approximation of
X
is the same set as the
concept
B
-lower approximation of
X
.A
concept B
-upper approximation of
the concept
X
is defined as follows:
B
X
=
∪{
K
B
(
x
)
|
x
∈
X,K
B
(
x
)
⊆
X
}
BX
=
∪{
K
B
(
x
)
|
x
∈
X,K
B
(
x
)
∩
X
=
∅}
=
∪{
K
B
(
x
)
|
x
∈
X
}
.
The concept
B
-upper approximation of
X
are subsets of the subset
B
-
upper approximations of
X
. For the decision presented in Table 2, the concept
A
-lower and
A
-upper approximations are:
A
{
1
,
2
,
4
,
8
}
=
{
1
,
2
,
4
,
8
}
,
A
{
3
,
5
,
6
,
7
}
=
{
3
,
6
,
7
}
,
A
{
1
,
2
,
4
,
8
}
=
{
1
,
2
,
4
,
8
}
,
A
{
3
,
5
,
6
,
7
}
=
{
3
,
4
,
5
,
6
,
7
,
8
}
.
For complete decision tables, all three definitions of lower approximations,
singleton, subset and concept, coalesce to the same definition. Also, for com-
plete decision tables, all three definitions of upper approximations coalesce
to the same definition. This is not true for incomplete decision tables, as our
example shows.
5 Rule Induction
The same idea of blocks of attribute-value pairs is used in the rule induction
algorithm LEM2. LEM2 explores the search space of attribute-value pairs. Its
input data file is a lower or upper approximation of a concept, so its input
data file is always consistent. Rules induced from the lower approximation
of the concept
certainly
describe the concept, so they are called
certain
.On
the other hand, rules induced from the upper approximation of the concept
describe the concept only
possibly
(or
plausibly
), so they are called
possible
[3].
Rules in LERS format (every rule is equipped with three numbers, the
total number of attribute-value pairs on the left-hand side of the rule, the total
number of cases correctly classified by the rule during training, and the total
number of training cases matching the left-hand side of the rule) induced from
Table 2 using concept approximations are:
the certain rule set:
2, 3, 3
(Temperature, high) & (Headache, yes) —
>
(Flu, yes)
