The Apriori algorithm uses a candidate generation and frequency counting strategy for frequent itemset mining. Candidate itemsets of size (k + 1) are created by joining a pair of frequent itemsets of size k. A candidate is discarded if any one of its subsets is found to be infrequent during the candidate pruning step. Suppose the Apriori algorithm is applied to the transaction databases, as shown in Table 1 with minsup = 30%, i.e., any itemset occurring in less than 3 transactions is considered to be infrequent.n

1. Draw an itemset lattice representing the transaction database in Table 1. Label each node in the lattice with the following letters: • N: If the itemset is not considered to be a candidate itemset by the Apriori algorithm. • F: If the itemset is frequent; • I: If the candidate itemset is infrequent after support counting.n

2. What is the percentage of frequent itemsets (w.r.t. all itemsets in the attice)?n  

Transcribed Image Text:

Table 1: A Sample of Marekt Basket Transactions Transaction ID | Items Bought {a, b, d, e} {b, с, d} {a, b, d, e} {а, с, d, e] {b, с, d, e} {b, d, e} {c, d} {a, b, c} {a, d, e} {b, d} 1 3 4 5 6. 7 8 9. 10 Table 1: A Sample of Marekt Basket Transactions Transaction ID | Items Bought {a, b, d, e} {b, с, d} {a, b, d, e} {а, с, d, e] {b, с, d, e} {b, d, e} {c, d} {a, b, c} {a, d, e} {b, d} 1 3 4 5 6. 7 8 9. 10