Database Reference
In-Depth Information
Item
a
b
c
d
e
Expected support
2.3
2.2
1.8
1.4
1.0
Link
a
0.2
b
0.9
c
0.4
a
0.6
b
0.6
c
0.6
d
0.9
a
0.6
b
0.5
d
0.5
e
0.7
a
0.9
b
0.2
c
0.8
e
0.3
Fig. 14.1
The UH-struct for the probabilistic dataset
D
2
of uncertain data
4
Hyperlinked Structure-Based Uncertain Frequent Pattern
Mining
An alternative to candidate generate-and-test based mining is
pattern-growth mining
,
which avoids generating a large number of candidates. Commonly used pattern-
growth mining paradigms are mostly based on (i) hyperlinked structures or (ii) tree
structures. In this section, let us focus on hyperlinked structure-based uncertain
frequent pattern mining. As hyperlinked structure based mining employs a pattern-
growth mining paradigm, the candidate generate-and-test mining paradigm of U-
Apriori is avoided. In general, hyperlinked structure based algorithms capture the
contents of datasets in a hyperlinked structure, from which frequent patterns are
mined in a depth-first divide-and-conquer fashion.
Aggarwal et al. [
13
] proposed a hyperlinked structure based algorithm called
UH-mine
to mine frequent patterns from uncertain data. This algorithm captures
the contents of a probabilistic dataset
D
of uncertain data in a hyperlinked structure
called
UH-struct
. See Fig.
14.1
. Like the H-struct for mining precise data, each row
in the UH-struct represents a transaction
t
i
in
D
. Unlike the H-struct, the UH-struct
captures the existential probability of items. In other words, for each item
x
∈
t
i
,
the UH-struct maintains (i)
x
, (ii) its existential probability
P
(
x
,
t
i
), and (iii) its
hyperlink. Once the UH-struct is built, the corresponding UH-mine algorithm mines
frequent patterns by recursively extending every frequent pattern
X
and adjusting its
hyperlinks in the UH-struct.
As a preview, when compared with tree-based uncertain frequent pattern mining
(i.e., another type of mining that relies on the pattern-growth mining paradigm),
the UH-structure is not as compact as the tree structure used in tree-based mining.
However, on the positive side, the UH-mine algorithm keeps only one UH-struct
and adjusts the hyperlinks in it. In contrast, due to their recursive nature, tree-
based mining algorithms usually keep multiple tree structures. Moreover, UH-mine
