Question

Consider the following set of frequent 3-itemsest:
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {2, 3, 5}, {3, 4, 5}.
Assume that there are only five items in the data set.
a. List all candidate 4-itemsets obtained by a candidate generation procedure using the
F_k-1 x F₁ merging strategy.
b. List all candidate 4-itemsets obtained by the candidate generation procedure in
Apriori.
c. List all candidate 4-itemsets that survive the candidate pruning step of the Apriori
algorithm.

Answer 1

a) •{1, 2, 3}: {1, 2, 3, 4}, {1, 2, 3, 5}

• {1, 2, 4}: {1, 2, 4, 5}
  • {1, 3, 4}: {1, 3, 4, 5}

• {2, 3, 4}: {2, 3, 4, 5}

Other combinations were duplicates or not extendible from 3-itemsets to 4-itemsets.

b) From the frequent 3-itemsets, we can assume that minsup = 4. All 4-itemsets from the previous part were generated from frequent 3-itemsets, so we get the same candidates as before:
{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}.
c) {1, 2, 3, 4} survives as all of it’s subsets ( {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}) are frequent. {1, 2, 3, 5} survives as all of it’s subsets ( {1, 2, 3}, {1, 2, 5}, {1, 3, 5}, {2, 3, 5}) are frequent. Other 4-itemsets are pruned.

Please upvote the solution, comment in case of doubt