Databases Reference
In-Depth Information
Objects
x
3
,x
4
,x
11
,x
12
x
1
,x
2
,x
7
,x
8
x
7
,x
8
,x
9
x
3
,x
4
x
5
,x
6
a
1
2
2
bc d
H
1
L
L
1
10H
32H
T
1
a=1
a=2
Objects
x
1
,x
2
,x
7
,x
8
Objects
x
3
,x
4
,x
11
,x
12
a
1
bc d
a
21
bcd
H
L
x
3
,x
4
x
7
,x
8
,x
9
10H
2
1
L
x
5
,x
6
x
3
,x
4
30H
10H
T
2
x
5
,x
6
32H
T
3
c=0
c=0
c=0
Objects
x
1
,x
2
,x
7
,x
8
a
21
bcd
Objects
abc d
abc d
Objects
x
1
,x
2
,x
7
,x
8
L
21
L
x
1
,x
2
,x
7
,x
8
21
L
x
3
,x
4
x
5
,x
6
10H
32H
T
4
T
5
x
7
,x
8
,x
9
2
1
L
T
6
d=L
d=H
Objects
x
1
,x
2
,x
7
,x
8
a
21
bcd
Objects
x
5
,x
6
a
bcd
L
32H
T
7
T
8
Fig. 1.
Action tree
values and stable attribute, it is divided into three, one with rules containing
c = 0, one with rules containing c = 1, and one with rules containing c = 2.
At this step, each sub-table does not contain any stable attributes. Table
T
6
can not be split any further for the same reason as sub-table
T
2
. All objects
in sub-table
T
4
have the same value of flexible attribute
b
, so the table is not
partitioned any further. The remaining table
T
5
is partitioned into two sub-
tables. Each leaf represents a set of rules which do not contradict on stable
attributes and also define decision value
d
i
.
The path from the root to that leaf gives the description of objects sup-
ported by these rules. Following the path labelled by value [
a
= 2], [
c
=2],
and [
d
=
L
], we get table
T
7
. Following the path labelled by value [
a
=2],
[
c
=2],and[
d
=
H
], we get table
T
8
. Because
T
7
and
T
8
are sibling nodes, we
can directly compare pairs of rules belonging to these two tables and construct
one e-action rule such as:
[[(
a,
2)
∧
(
b,
1
→
3)]
⇒
(
d,L
→
H
)].
After the rule is formed, we evaluate it by checking its support and its
confidence. We have discovered an extended action rule given below:
[[(
a,
2)
∧
(
b,
1
→
3)]
⇒
(
d,L
→
H
)];
sup
:4
conf
: 100%.
This new algorithm (called DEAR 2.2) was implemented and tested on
many datasets using PC with 1.8 GHz CPU. The time complexity of the action
forest algorithm used in system
DEAR
2is(
k
1) +
log
(
n
)=
O
(
n
+
log
(
n
)), where
n
is the number of classification rules,
k
is the number
∗
n
)+(2
k
∗
n
∗
