Apriori: a candidate Generation-and-Test approach Apriori pruning principle: If there is any itemset which is infrequent, its superset should not be generated /tested (Agrawal srikant @VLDB 94, Mannila, et al.@ KDD 94) Method Initially, scan DB once to get frequent 1-itemset Generate length( k+1)candidate itemsets from length k frequent itemsets Test the candidates against dB Terminate when no frequent or candidate set can be generated February 4, 2021 Data Mining: Concepts and Techniques 11February 4, 2021 Data Mining: Concepts and Techniques 11 Apriori: A Candidate Generation-and-Test Approach ◼ Apriori pruning principle: If there is any itemset which is infrequent, its superset should not be generated/tested! (Agrawal & Srikant @VLDB’94, Mannila, et al. @ KDD’ 94) ◼ Method: ◼ Initially, scan DB once to get frequent 1-itemset ◼ Generate length (k+1) candidate itemsets from length k frequent itemsets ◼ Test the candidates against DB ◼ Terminate when no frequent or candidate set can be generated