Information Technology Reference
In-Depth Information
4 Rule Generation
Since the introduction of association rules in [2] a broad variety of association
rule mining algorithms have been developed. The main challenge when mining
association rules is the great number of rules to be considered.
4.1 Formal Problem Description
Let
R
be the number of all rules existing to a set of distinct literals
I
with
|I|
=
n
. It follows:
|R|
=3
n
−
2
n
+1
+1
Proof: For all
x, y ∈
R and
n ∈
N the following holds , c.f. [12, p. 57]:
n
k
n
(
x
+
y
)
n
=
x
(
n−k
)
y
k
(
∗
)
k
=0
With
x
= 1 and
y
= 1 it follows:
n
k
n
n
=
(
∗∗
)
k
=0
The left side of a rule may contain up to
n −
1 different items. With
k
denoting
the number of items on the left side of the rule, for the right side maximally
n − k
items are left. With that
|R|
can be expressed as follows:
n
k
n
k
n − k
l
n − k
l
n−
1
n−k
n−
1
n−k
|R|
=
=
·
k
=1
l
=1
k
=1
l
=1
n
k
n−k
n − k
l
n − k
0
n−
1
=
·
−
k
=1
l
=0
n
k
n
k
n
k
n−
1
n−
1
n−
1
(
∗∗
)
=
·
(2
n−k
−
1)
2
(
n−k
)
=
−
k
=1
k
=1
k
=1
n
k
n
k
n
n
(
∗
)
=3
n
−
2
n
+1
+1
2
(
n−k
)
1
k
−
2
n
−
1
−
=
+2
k
=0
k
=0
In practical applications
n
may range from “only” about several hundred
items up to several hundred thousand or even more, depending on the actual
application. Therefore mining all rules obviously is infeasible. Moreover from
the point of viewof a person deploying association rules for analysis purposes,
mining all associations would hardly make any sense. Therefore the rule set to
