Databases Reference
In-Depth Information
making it impossible to reach colossal patterns. Even depth-first search methods like
FP-growth can be easily trapped in a huge amount of subtrees before reaching colossal
patterns. Clearly, a completely new mining methodology is needed to overcome such a
hurdle.
A new mining strategy called
Pattern-Fusion
was developed, which fuses a small
number of shorter frequent patterns into colossal pattern candidates. It thereby takes
leaps in the pattern search space and avoids the pitfalls of both breadth-first and depth-
first searches. This method finds a good approximation to the complete set of
colossal
frequent patterns.
The Pattern-Fusion method has the following major characteristics. First, it traverses
the tree in a bounded-breadth way. Only a fixed number of patterns in a bounded-size
candidate pool are used as starting nodes to search downward in the pattern tree. As
such, it avoids the problem of exponential search space.
Second, Pattern-Fusion has the capability to identify “shortcuts” whenever possible.
Each pattern's growth is not performed with one-item addition, but with an agglomera-
tion of multiple patterns in the pool. These shortcuts direct Pattern-Fusion much more
rapidly down the search tree toward the colossal patterns. Figure 7.8 conceptualizes this
mining model.
As Pattern-Fusion is designed to give an approximation to the colossal patterns, a
quality evaluation model is introduced to assess the patterns returned by the algorithm.
An empirical study verifies that Pattern-Fusion is able to efficiently return high-quality
results.
Let's examine the Pattern-Fusion method in more detail. First, we introduce the con-
cept of
core pattern
. For a pattern
, an itemset
is said to be a
-core pattern
of
if
j
D
j
j
D
j
, 0
< 1, where j
D
j is the number of patterns containing
in database
Pattern candidates
Colossal patterns
Current
Pool
Shortcut
Figure 7.8
Pattern tree traversal: Candidates are taken from a pool of patterns, which results in shortcuts
through pattern space to the colossal patterns.
