Database Reference
In-Depth Information
Pattern Candidates
Colossal Patterns
Current
Pool
Shortcut
Fig. 4.8
Pattern tree traversal
is observed.
Pattern-Fusion
captures this relationship between a pattern and its
subpattern by the concept of
core pattern
.
Definition 4.13 (Core Pattern)
For a pattern α, an itemset β
⊆
α is said to be a
τ -core pattern of α if
|
D
α
|
|
D
β
|
≥
τ ,
0
<τ
≤
1
. τ is called the core ratio.
For a pattern
α
,
let
C
α
be the set of all its core patterns,
i.e.,
C
α
=
β
τ
for a specified
τ
. The robustness of a colossal pattern can
be further defined as follows.
α
,
|
D
α
|
|
β
⊆
|
D
β
|
≥
Definition 4.14 (
(
d
,
τ
)
-Robustness)
A pattern
α
is (
d
,
τ
)
-robust
if
d
is the maximum
number of items that can be removed from
α
for the resulting pattern to remain a
τ
-core pattern of
α
, i.e.,
d
=
max
β
{|
α
|−|
β
||
β
⊆
α
,
and β is a τ
−
core pattern of α
}
Due to its robustness, a colossal pattern tends to have a large number of core
patterns. Let
α
be a colossal pattern which is (
d
,
τ
)-robust. The following two lemmas
show that the number of core patterns of
α
is at least exponential in
d
. In particular,
it can be shown that for a (
d
,
τ
)-robust pattern
α
,
2
d
.
This core-pattern-based view of the pattern space leads to the following two
observations which are essential in
Pattern-Fusion
design.
Observation 1.
Due to the observation that a colossal pattern has far more core
patterns than a smaller-sized pattern does, given a small
c
, a colossal pattern therefore
has far more core descendants of size
c
.
Observation 2.
A colossal pattern can be generated by merging a proper set of
its core patterns.
These observations on colossal patterns inspires the following mining approach:
First generate a complete set of frequent patterns up to a small size, and then randomly
pick a pattern,
β
. By our foregoing analysis
β
would with high probability be a
core-descendant of some colossal pattern
α
. Identify all
α
's core-descendants in
|
C
α
|≥
