Frequent Itemsets and Association rules Mining Massive Datasets Wu-Jun li Department of Computer Science and Engineering Shanghai Jiao Tong University Lecture 3: Frequent Itemsets and Association Rules
Frequent Itemsets and Association Rules 1 Wu-Jun Li Department of Computer Science and Engineering Shanghai Jiao Tong University Lecture 3: Frequent Itemsets and Association Rules Mining Massive Datasets
Frequent Itemsets and Association rules Outline ■ Association rules A-Priori algorithm Large-scale algorithms
Frequent Itemsets and Association Rules 2 Outline ▪ Association rules ▪ A-Priori algorithm ▪ Large-scale algorithms 2
Frequent Itemsets and Association rules Association Rules The market-Basket model A large set of items, e.g things sold in a supermarket A large set of baskets, each of which is a small set of the items, e.g the things one customer buys on one day WD Items Bread. Coke. Milk Beer bread Beer, Coke, Diaper, Milk Beer Bread, Diaper. Milk Coke, Diaper. Milk
Frequent Itemsets and Association Rules 3 The Market-Basket Model ▪ A large set of items, e.g., things sold in a supermarket. ▪ A large set of baskets, each of which is a small set of the items, e.g., the things one customer buys on one day. Association Rules
Frequent Itemsets and Association rules Association Rules Market-Baskets-(2) Really a general many-many mapping(association) between two kinds of things But we ask about connections among items not baskets The technology focuses on common events, not rare events(long tail 4
Frequent Itemsets and Association Rules 4 Market-Baskets – (2) ▪ Really a general many-many mapping (association) between two kinds of things. ▪ But we ask about connections among “items,” not “baskets.” ▪ The technology focuses on common events, not rare events (“long tail”). Association Rules
Frequent Itemsets and Association rules Association Rules Association Rule Discovery Goal: To identify items that are bought together by sufficiently many customers and find dependencies among items WDD ltems Bread, Coke, Milk Rules discovered Beer Bread IMilk-->(Coke] Beer, Coke, Diaper, Milk [Diaper, Milk-->(Beer] Beer, Bread, Diaper, Milk 5 Coke, Diaper. Milk
Frequent Itemsets and Association Rules 5 Association Rule Discovery ▪ Goal: To identify items that are bought together by sufficiently many customers, and find dependencies among items Association Rules