Frequent Itemset Generation Brute-force approach Each itemset in the lattice is a candidate frequent itemset Count the support of each candidate by scanning the database Transactions List of Candidates TID tems Bread. milk Bread, Diaper, Beer, Eggs 2345 Milk, Diaper, Beer, Coke Bread, Milk, Diaper, beer Bread, Milk, Diaper, Coke W atch each transaction against every candidate Complexity -O(NMw)=> Expensive since M=2d! ! O Tan, Steinbach, Kumar Introduction to Data Mining 4/18/2004© Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 ‹#› Frequent Itemset Generation Brute-force approach: – Each itemset in the lattice is a candidate frequent itemset – Count the support of each candidate by scanning the database – Match each transaction against every candidate – Complexity ~ O(NMw) => Expensive since M = 2d !!! TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke N Transactions List of Candidates M w