INCREMENTAL PROBABILISTIC FRE-OF THE AIQ TO K − M, WHERE M IS THE N...

6. INCREMENTAL PROBABILISTIC FRE-

of the AIQ to k − m, where m is the number of highest fre-

quentness probability items already returned. Any itemsets

QUENT ITEMSET MINING (I-PFIM)

that “fall off” the end can safely be ignored. The rational

Our probabilistic frequent itemset mining approach allows

behind this approach is that for an itemset X at position p

the user to control the confidence of the results using τ .

in the AIQ, p − 1 itemsets with a higher frequentness than

However, since the number of results depends on τ , it may

X exist in the AIQ by construction. Additionally, any of

prove difficult for a user to correctly specify this parameter

the m itemsets that have already been returned must have

without additional domain knowledge. Therefore, this Sec-

a higher frequentness probability. Consequently, our top-k

tion shows how to efficiently solve the following problems,

algorithm contrains the size of the initial AIQ to k and re-

which do not require the specification of τ;

duces its size by one each time a result is reported. The

algorithm terminates once the size of the AIQ reaches zero.

• Top-k probabilistic frequent itemsets query: return the

k itemsets that have the highest frequentness proba-