Given the following transaction record Transaction Records Transaction ID Items #1 apple, banana, coca-cola, doughnut #2 banana, coco-cola #3 banana, doughnut #4 apple, coca-cola #5 apple, banana, doughnut #6 apple, banana, coca-cola Build the FP-tree using a minimum support min_sup = 2. Show how the tree evolves for each transaction. Use the FP-Growth algorithm to discover frequent itemsets from the FP-tree. With the previous transaction record, Use the Apriori algorithm on this dataset and verify that it will generate the same set of frequent itemsets with min_sup = 2. Suppose that { Apple, Banana, Doughnut } is a frequent item set, derive all its association rules with min_confidence = 70%

Building the FP-tree:

Transaction ID #1: apple, banana, coca-cola, doughnut

   root
   |
   a
   |
   p
   |
   p - b
   |   |
   |   c
   |   |
   |   d

Transaction ID #2: banana, coca-cola

   root
   |
   a
   |
   p - b - c
   |   |
   |   d

Transaction ID #3: banana, doughnut

   root
   |
   a
   |
   p - b - c
   |   |   |
   |   |   d
   |   |
   |   d

Transaction ID #4: apple, coca-cola

   root
   |
   a - c
   |   |
   |   p - b - c
   |   |   |
   |   |   d
   |   |
   |   d

Transaction ID #5: apple, banana, doughnut

   root
   |
   a - b - d
   |   |   |
   |   |   c
   |   |
   |   p - b - c
   |       |
   |       d
   |
   b - d
       |
       c

Transaction ID #6: apple, banana, coca-cola

   root
   |
   a - b - c
   |   |   |
   |   |   d
   |   |
   |   p - b - c
   |       |
   |       d
   |
   b - d
       |
       c

Using the FP-Growth algorithm to discover frequent itemsets:

Starting with the most frequent item (d):
- d (4)
- b-d (3)
- c-b-d (2)
- a-b-d (2)
- a-p-b-d (2)

Next, starting with the next most frequent item (b):
- b (4)
- a-b (3)
- p-b (3)
- c-b (2)
- a-p-b (2)
- c-b-d (2)
- a-b-d (2)
- a-p-b-d (2)

Finally, starting with the least frequent item (c):
- c (3)
- b-c (2)
- a-b-c (2)
- p-b-c (2)
- c-b-d (2)
- a-b-d (2)
- a-p-b-d (2)

All sets of frequent itemsets with minimum support of 2 are:
- {d} (4)
- {b} (4)
- {c} (3)
- {a, d} (2)
- {b, d} (3)
- {p, b, d} (2)
- {c, b, d} (2)
- {a, b, d} (2)
- {a, p, b, d} (2)
- {a, b} (3)
- {p, b} (3)
- {c, b} (2)
- {a, p, b} (2)
- {c, b, d} (2)
- {a, b, d} (2)
- {a, p, b, d} (2)
- {a, c, b} (2)
- {p, c, b} (2)
- {a, p, c, b} (2)

Using the Apriori algorithm to verify the frequent itemsets with minimum support of 2:

Starting with 1-itemsets:
- {apple} (3)
- {banana} (4)
- {coca-cola} (3)
- {doughnut} (4)

Next, starting with 2-itemsets:
- {apple, banana} (2)
- {apple, coca-cola} (1)
- {apple, doughnut} (2)
- {banana, coca-cola} (2)
- {banana, doughnut} (2)
- {coca-cola, doughnut} (2)

Finally, starting with 3-itemsets:
- {apple, banana, doughnut} (2)

All sets of frequent itemsets with minimum support of 2 are:
- {banana} (4)
- {doughnut} (4)
- {apple} (3)
- {coca-cola} (3)
- {banana, doughnut} (2)
- {apple, doughnut} (2)
- {apple, banana} (2)
- {banana, coca-cola} (2)
- {coca-cola, doughnut} (2)
- {apple, banana, doughnut} (2)

The Apriori algorithm generates the same set of frequent itemsets with minimum support of 2 as the FP-Growth algorithm.

Deriving all association rules with 70% minimum confidence for the frequent itemset {Apple, Banana, Doughnut}:

First, find all the subsets of {Apple, Banana, Doughnut}:
- {Apple, Banana}
- {Apple, Doughnut}
- {Banana, Doughnut}
- {Apple}
- {Banana}
- {Doughnut}

Next, calculate the confidence for each rule:
- {Apple, Banana} -> {Doughnut} (2/2 = 100%)
- {Apple, Doughnut} -> {Banana} (2/2 = 100%)
- {Banana, Doughnut} -> {Apple} (2/2 = 100%)
- {Apple} -> {Banana, Doughnut} (2/3 = 67%)
- {Banana} -> {Apple, Doughnut} (2/4 = 50%)
- {Doughnut} -> {Apple, Banana} (2/4 = 50%)

All association rules with minimum confidence of 70% for the frequent itemset {Apple, Banana, Doughnut} are:
- {Apple, Banana} -> {Doughnut}
- {Apple, Doughnut} -> {Banana}
- {Banana, Doughnut} -> {Apple}