Databases Reference
In-Depth Information
child node. When we are done with stable attributes, the last split is based
on a decision attribute for each branch. If at any time all instances at a node
have the same decision value, then we stop developing that part of the tree.
The only thing left to build the tree is to decide how to determine which of
the stable attributes to split, given a set of rules with different classes. The
node selection is based on the stable attributes with the smallest number of
possible values among all the remaining stable attributes.
An e-action tree has two types of nodes: a leaf node and a nonleaf node.
At a nonleaf node in the tree, the set of rules is partitioned along the branches
and each child node gets its corresponding subset of rules. Every path to the
decision attribute node, one level above the leaf node, in the action tree repre-
sents a subset of the extracted classification rules when the stable attributers
have the same value. Each leaf represents a set of rules, which do not contra-
dict on stable attributes and also define decision value
d
i
. The path from the
root to that leaf gives the description of objects supported by these rules.
Let us take Table 1 as an example of a decision system
S
. We assume that
a
,
c
are stable attributes and
b
,
d
are flexible. Assume now that our goal is to
re-classify some objects from the class
d
−
1
(
) into the class
d
−
1
(
{
d
i
}
{
d
j
}
). In
our example, we assume that
d
i
=(
d,L
)and
d
j
=(
d,H
).
First, we represent the set
R
of certain rules extracted from
S
as a table
(see Table 2). The first column of this table shows objects in
S
supporting the
rules from
R
(each row represents a rule). The construction of an action tree
starts with the set
R
as a table (see Table 2) at the root of the tree (
T
1
in
Fig. 1). The root node selection is based on a stable attribute with the smallest
number of states among all stable attributes. The same strategy is used for
the child node selection. After putting all stable attributes on the tree, the
tree is split based on the value of the decision attribute. Referring back to
the example in Table 1, we use stable attribute
a
to split that table into two
sub-tables defined by values
{
1
,
2
}
of attribute
a
. The domain of attribute
a
is
{
. Clearly,
card
[
V
a
] is less than
card
[
V
c
] so we divide the table into two: one table with rules containing
a
=0
and another with rules containing
a
= 2. Each corresponding edge is labelled
by the value of attribute
a
. Next, all objects in the sub-table
T
2
have the same
decision value. We can not generate any e-action rules from this sub-table so
it is not divided any further. Because sub-table
T
3
contains different decision
1
,
2
}
and the domain of attribute
c
is
{
0
,
1
,
2
}
Tabl e 2 .
Set of rules
R
with supporting objects
Objects
a
b
c
d
{x
3
,x
4
,x
11
,x
12
}
1
H
{x
1
,x
2
,x
7
,x
8
}
2
1
L
{x
7
,x
8
,x
9
}
2
0
L
{x
3
,x
4
}
1
0
H
{x
5
,x
6
}
3
2
H
