Database Reference
In-Depth Information
3.1
Generic Algorithm
The setting which is closest to frequent pattern mining is that of constraint-based
mining under anti-monotonic constraints. In this case, we can perform a level-wise
search that is mostly equal to that of the APRIORI algorithm [
20
]. The search starts
from the empty pattern, and proceeds by specializing this pattern in a breadth-first
fashion.
In Algorithm 1, a description of this algorithm is given. In this pseudo-code,
we use two operators: a
downward refinement operator ρ
to specialize patterns and
an
upward refinement operator δ
to generalize patterns. A downward refinement
operator is an operator which for any pattern
π
returns a
set
of more specific patterns
(i.e. for all patterns
π
∈
π
). Typically, we assume that this
operator is
globally complete
, i.e. its repeated application starting from the empty
pattern will produce the complete pattern language
2
. Furthermore, this operator
works in “small steps”, it tries to create new patterns which are minimally more
specific (
least specific specializations
).
An example of a downward refinement operator for itemset mining is
ρ
(
π
)
ρ
(
π
) it holds that
π
=
{
, assuming a total order
>
on the items; eg., if our language
is 2
{
1,2,3,4
}
, with the usual order of integers over the items,
ρ
(
π
∪{
i
}|
i>
max(
π
)
}
{
}
={{
}
{
}}
.
Similarly, the upward refinement operator
δ
returns generalizations. For a given
pattern
π
, it is assumed to only generate patterns that should have been seen before
pattern
π
by the level-wise algorithm.
The key property on which the algorithm relies is the anti-monotonicity of con-
straint
ϕ
under the chosen generality relation: by refining only patterns that satisfy
the constraint in line 6 and by checking generalizations in line 7, patterns are removed
from consideration that are known to specialize patterns that do not satisfy
ϕ
.
2
)
2, 3
,
2, 4
Note that this algorithm can also be applied to convertible and boundable constraints
[
28
]: in this case, a modified generality relation or constraint is used. It can also
be applied in a straightforward manner if there are both anti-monotonic constraint
More formally, let
ρ
n
(
π
) denote the set
π
∈
ρ
(
π
)
ρ
n
−
1
(
π
), with
ρ
0
(
π
)
2
π
, and let
ρ
∗
(
π
)
=
=
i
=
1
ρ
i
(
π
), then a refinement operator is complete if
ρ
∗
(
∅
) equals the pattern language
L
.
