Consider the transactional database shown in the following table. Transaction ID Items Bought
T100 Milk, Bread, Salad, Fruit, Soup, Noodle
T200 Beef, Bread, Salad, Fruit, Soup, Noodle
T300 Milk, Rice, Fruit, Soup, Pork, Lamb
T400 Milk, Chicken, Fish, Fruit, Noodle
T500 Fish, Bread, Fruit, Shrimp, Soup
T600 Fruit, Noodle, Milk, Bread, Bean, Duck
Let minimum support be 50% and let minimum confidence be 30%.
(A) Find all frequent itemsets using the Apriori algorithm. Show how the Apriori algorithm
works in a step by step manner.
(B) List all the association rules found by the Apriori algorithm.
(C) Find all frequent itemsets using the FP-tree algorithm. Show the final FP-tree you
constructed. Note that the FP-tree algorithm has a pre-processing step, which sorts items in a
transaction based on the support values of the items. If two items have the same support value,
they must be sorted in alphabetical (lexicographical) order in the transaction.
(D) List all the association rules found by the FP-tree algorithm.
(E) In this example, indicate whether the association rules produced by the Apriori algorithm are
the same as those produced by the FP-tree algorithm.
(F) Compare the efficiency of the Apriori algorithm and the FP-tree algorithm using this
example. Indicate which algorithm is more efficient and explain why based on this example.