Let c c be a candidate itemset in C k C k generated by the Apriori algorithm.

Let $c$ be a candidate itemset in $C_k$ generated by the Apriori algorithm. How many length- $(k-1)$ subsets do we need to check in the prune step? Per your previous answer, can you give an improved version of procedure has_infrequent_subset in Fig. 4.4?

Fig. 4.4

Transcribed Image Text:

Algorithm: Apriori. Find frequent itemsets using an iterative level-wise approach based on candidate generation Input: D, a database of transactions; min_sup, the minimum support count threshold. Output: L, frequent itemsets in D. Method: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) } (11) return L = UkLk; (1) (2) (3) (4) (5) (6) L = find_frequent_1-itemsets(D); for (k =2; Lk-10; k++) { Ck apriori_gen(Lk-1); procedure apriori_gen(Lk-1: frequent (k-1)-itemsets) for each itemset / Lk-1 (1) (2) for each transaction t E D { // scan D for counts Ct = subset(Ck, 1); // get the subsets of t that are candidates for each candidate c Ct c.count++; (3) (4) } Lk={ce Clc.count > min_sup} for each itemset 12 Lk-1 if ( [1] =1[1])^(1/[2] = 1[2]) A... ^ (1[k-2] = 1[k-2]) ^ (1[k - 1] <1[k-1]) then { c=112; // join step: generate candidates if has_infrequent_subset(c, Lk-1) then } return Ck; procedure has_infrequent_subset(c: candidate k-itemset; delete c; // prune step: remove unfruitful candidate else add c to Ck; Lk 1: frequent (k-1)-itemsets); // use prior knowledge for each (k-1)-subsets of c ifs & Lk-1 then return TRUE; return FALSE;