Fall 2019 Frequent Item Sets & Association Rules Vassilis Christophides christop@csd.uoc.gr http://www.csd.uoc.gr/~hy562 University of Crete, Fall 2019 1 Fall 2019 Some History  Bar code technology allowed retailers to collect massive volumes of sales data Basket data: transaction date, set of items bought Data is stored in tertiary storage  Leverage information for marketing How to design coupons? How to organize shelves?  The birth of data mining! Agrawal et al. (SIGMOD 1993) introduced the problem of mining a large collection of basket data to discover association rules Many papers followed… 2 1 1 Fall 2019 Example: Supermarket Shelf-Management  Goal: Identify items that are bought together by sufficiently many customers Supermarket shelf management Market-basket model:  Approach: theitems sales data with barcode scanners Goal:Process Identify thatcollected are bought together by to find dependencies among items sufficiently many customers Given a set of transactions (market‐basket model), findwith rules barcode that will Approach: Process the sales data collected predict the occurrence of an item based on the occurrences of other scanners to find dependencies among items items in the transactions A classic rule:  A classic rule: If one buys diaper and milk, then he is likely to buy beer If one buys diaper and milk, then he is likely to buy beer Don’t be surprised if you find six-packs next to diapers! Don’t be surprised if you find six-packs next to diapers! TI D I tems 1 2 3 4 5 Br ead, Coke, M ilk Beer , Br ead Beer , Coke, Diaper , M ilk Beer , Br ead, Diaper , M ilk Coke, Diaper , M ilk 1/10/2013 Rules Disco vered : Rules Discovered: {M ilk} --> {Coke} {Milk} > {Coke} {D iape r, Milk} > {Beer} {Diaper, Milk} --> {Beer} Jure Leskovec, Stanford CS246: Mining Massive Datasets, http://cs246.stanford.edu 2 3 Fall 2019 Application Examples of Association Rules  Items = products; baskets = sets of products someone bough