Database Reference
In-Depth Information
Table 14.3
Possible worlds for the probabilistic dataset
D
2
of uncertain data
Possible world
W
j
Prob
(
W
j
)
Transactions
W
1
6.349
×
10
−
5
{
t
1
=
{
a
,
b
,
c
}
,
t
2
=
{
a
,
b
,
c
,
d
}
,
t
3
=
{
a
,
b
,
d
,
e
}
,
t
4
=
{
a
,
b
,
c
,
e
}
}
10
−
4
W
2
1.481
×
{
t
1
=
{
a
,
b
,
c
}
,
t
2
=
{
a
,
b
,
c
,
d
}
,
t
3
=
{
a
,
b
,
d
,
e
}
,
t
4
=
{
a
,
b
,
c
}
}
10
−
5
W
3
1.587
×
{
t
1
=
{
a
,
b
,
c
}
,
t
2
=
{
a
,
b
,
c
,
d
}
,
t
3
=
{
a
,
b
,
d
,
e
}
,
t
4
=
{
a
,
b
,
e
}
}
.
.
.
10
−
7
W
32767
1.769
×
{
t
1
=
{}
,
t
2
=
{}
,
t
3
=
{}
,
t
4
=
{
e
}
}
10
−
7
W
32768
4.129
×
{
t
1
=
{}
,
t
2
=
{}
,
t
3
=
{}
,
t
4
=
{}
}
j
Prob
(
W
j
)
=
1
be the true world) over all possible worlds, i.e.,
sup
(
X
,
W
j
)
Prob
(
W
j
)
,
expSup
(
X
,
D
)
=
×
(14.1)
j
where
sup
(
X
,
W
j
) counts the occurrences of
X
(i.e., the number of transactions
containing
all
the items within
X
) and
Prob
(
W
j
) can be computed by the following
equation:
⎡
⎣
x
∈
t
i
in
W
j
⎤
|
D
|
⎦
.
Prob
(
W
j
)
=
P
(
x
,
t
i
)
×
(1
−
P
(
y
,
t
i
))
(14.2)
i
=
1
y
∈
t
i
in
W
j
Table
14.3
shows all “possible worlds” of the probabilistic dataset
D
2
in Table
14.2
.
When items within the pattern
X
are independent, Eq. (
14.1
) can be simplified [
32
]
to become the following equation:
P
(
x
,
t
i
)
.
|
D
|
expSup
(
X
,
D
)
=
(14.3)
i
=
1
x
∈
X
In other words, the expected support of
X
in
D
can be computed as a sum (over
all
transactions) of the product of existential probabilities of all items within
X
.
Then, we can define the research problem of uncertain frequent pattern mining in
terms of
expSup
(
X
,
D
) as follows.
|
D
|
Definition 14.1
Given (i) a probabilistic dataset
D
of uncertain data and (ii) a user-
specified support threshold
minsup
, the research problem of
uncertain frequent
pattern mining
from a probabilistic dataset
D
of uncertain data is to find every
pattern
X
having
expSup
(
X
,
D
)
minsup
. Such a pattern
X
is called an
expected
support-based frequent pattern
or just
frequent pattern
for short.
≥
