Frequent Itemsets - Mining of Massive Datasets - page 199

with probability 1/ i , each decision being made independently of all other decisions. That
is, all the baskets contain item 1, half contain item 2, a third contain item 3, and so on. As-
sume the number of baskets is sufficiently large that the baskets collectively behave as one
would expect statistically. Let the support threshold be 1% of the baskets. Find the frequent
itemsets.
EXERCISE 6.1.5 For the data of Exercise 6.1.1 , what is the confidence of the following as-
sociation rules?
(a) {5 , 7} → 2.
(b) {2 , 3 , 4} → 5.
EXERCISE 6.1.6 For the data of Exercise 6.1.3 , what is the confidence of the following as-
sociation rules?
(a) {24 , 60} → 8.
(b) {2 , 3 , 4} → 5.
!! EXERCISE 6.1.7 Describe all the association rules that have 100% confidence for the
market-basket data of:
(a) Exercise 6.1.1 .
(b) Exercise 6.1.3 .
! EXERCISE 6.1.8 Prove that in the data of Exercise 6.1.4 there are no interesting association
rules; i.e., the interest of every association rule is 0.
6.2 Market Baskets and the A-Priori Algorithm
We shall now begin a discussion of how to find frequent itemsets or information derived
from them, such as association rules with high support and confidence. The original im-
provement on the obvious algorithms, known as “A-Priori,” from which many variants
have been developed, will be covered here. The next two sections will discuss certain fur-
ther improvements. Before discussing the A-priori Algorithm itself, we begin the section
with an outline of the assumptions about how data is stored and manipulated when search-
ing for frequent itemsets.