Scalable methods for Mining frequent patterns The downward closure property of frequent patterns a Any subset of a frequent itemset must be frequent If ibeer, diaper, nuts is frequent, so is ibeer diaper i. e, every transaction having beer, diaper, nuts also contains (beer, diaper Scalable mining methods: Three major approaches Apriori (agrawal srikant@VLDB94 Freq. pattern growth(ePgrowth-Han, Pei yin @SIGMOD00) Vertical data format approach(Charm-Zaki Hsiao @SDM02) February 4, 2021 Data Mining: Concepts and Techniques 10February 4, 2021 Data Mining: Concepts and Techniques 10 Scalable Methods for Mining Frequent Patterns ◼ The downward closure property of frequent patterns ◼ Any subset of a frequent itemset must be frequent ◼ If {beer, diaper, nuts} is frequent, so is {beer, diaper} ◼ i.e., every transaction having {beer, diaper, nuts} also contains {beer, diaper} ◼ Scalable mining methods: Three major approaches ◼ Apriori (Agrawal & Srikant@VLDB’94) ◼ Freq. pattern growth (FPgrowth—Han, Pei & Yin @SIGMOD’00) ◼ Vertical data format approach (Charm—Zaki & Hsiao @SDM’02)