Database Reference
In-Depth Information
and non anti-monotonic constraints: in principle, we ignore the non anti-monotonic
constraints during the search, and evaluate the remaining constraints for all found
patterns afterwards ,ina post-processing phase .
In the presence of monotonic constraints, we can improve somewhat on the need
to check all patterns [ 11 , 18 , 20 , 22 ]. The main idea is here to traverse the patterns
in a level-wise fashion in reverse order by starting with the most specific patterns
that satisfy the anti-monotonic constraint. Since the generalizations of a pattern that
does not satisfy a monotonic constraint will not satisfy the constraint either, we can
stop this reverse traversal at the point at which we no longer have patterns that satisfy
the constraint. This does not change the fact that we cannot enforce the monotonic
constraint in the first mining phase, however.
The level-wise algorithm is easily changed to deal with border representations .
Assume that upward refinement operator δ generates all least general generalizations
of a pattern π (a pattern π is a least general generalization for a pattern π if there
is no pattern π with π
π
π ). Then for each pattern π that satisfies an
anti-monotonic constraint, we can essentially identify its immediate generalizations,
which are clearly not maximal, and remove them from the solution set.
For instance, in the case of itemset mining such an operator is δ ( π )
={
π
\{
i
}|
i
}
π
. It would remove all immediate subsets of an itemset from the output. As it is
assumed that the upward refinement operator will always generate patterns that must
have been seen already, we do not need to explicitly remove other generalizations
from the output: they will have been removed at an earlier stage. With similar ideas,
the minimal patterns on the border of a monotonic constraint can also be found.
4
Depth-First Algorithm
Note, however, that even though the output of these modified BFS algorithms for
finding borders is correct, the running time will not be much better than that of an
algorithm that generates all patterns satisfying the constraint. Most algorithms that
are able to obtain dramatically better run times in practice are depth-first algorithms.
4.1
Basic Algorithm
The most basic depth-first constraint-based mining algorithm is given in Fig. 2 and
only supports anti-monotonic constraints.
Search WWH ::




Custom Search