2INSTANCE W ∈ W0,410 350,35T , T UNCERTAIN TRANSACTION DATABASE, TRA...

1,2

instance w ∈ W

0,410 350,35

T , t Uncertain transaction database, transaction

0,30,8

t ∈ T

0,250,60 60,2

I Set of all items

0,150,1

X, x Itemset X ⊆ I, item x ∈ I

0,05

S(X, w) Support of X in world w

00 1 2 3 4 5 6

P i (X) Probability that the support of X is i

minimum support (minSup)

support i

P ≥i (X ) Probability that the support of X is at least i

P i,j (X) Probability that i of the first j transactions

(b) Frequentness

(a) Support proba-

contain X

bility distribution of

probabilities of {D}

P ≥i,j (X ) Probability that at least i of the first j

{D}

transactions contain X

Figure 4: Probabilistic support of itemset X = {D}

Figure 3: Summary of Notations

in the uncertain database of Figure 2.

contrast to {D}. An expected support based technique does

Note that the transaction subset S ⊆ T contains exactly i

not differentiate between the two.

transactions.

The confidence with which an itemset is frequent is very

important for interpreting uncertain itemsets. We there-

Proof. The transaction subset S ⊆ T contains i transac-

tions. The probability of a world w j where all transactions

fore require concepts that allow us to evaluate the uncertain

in S contain X and the remaining |T −S| transactions do not

data in a probabilistic way. In this section, we formally in-

contain X is P(w j ) = Q

troduce the concept of probabilistic frequent itemsets.

t∈S P (X ⊆ t) · Q

t∈T−S (1 − P(X ⊆

t)). The sum of the probabilities according to all possi-