Page 1
Fall 2019 Frequent Item Sets & Association Rules Vassilis Christophides christop@csd.uoc.gr http://www.csd.uoc.gr/~hy562 University of Crete, Fall 2019 11 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
Page 2
Fall 2019 Example: Supermarket Shelf-Management GoalSupermarket shelf management: Identify items that are bought together by sufficiently many customers– Market-basket model: ApproachGoal:: Process the sales data collected with barcode scanners to findIdentify items that are bought together by dependencies among itemssufficiently many customers Given a set of transactions (marketApproach: Process the sales data collected with barcode‐basket model), find rules that will predict the occurrence of an item based onscanners to find dependencies among itemsthe occurrences of other itemsA classic rule:in the transactions A classic ruleIf one buys diaper and milk, then he is likely to buy beer: If one buys diaper and milk, then he is likely to buy beerDon’t be surprised if you find six-packs next to diapers! Don’t be surprised if you find six-packs next to diapers! TID I tems 1 Br ead, Coke, M ilk Rules Discovered: Rules Discovered:{Milk} --> {Coke} 2 Beer , Br ead {Milk} --> {Coke}{Diaper, Milk} --> {Beer} 3 Beer , Coke, Diaper , M ilk {Diaper, Milk} --> {Beer} 4 Beer , Br ead, Diaper , M ilk 5 Coke, Diaper , M ilk 1/10/2013 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 bought in one visit to the store Reveals typical buying behaviour of customers Marketing and sales promotion (suggests tie-in “tricks”) a product p appearing as rules’ consequent can be used to determine what should be done to boost p sales a product p’ appearing as rules’ antecedent can be used to see which other products would be affected if the store discontinues selling p’ a rule p’ -> p an be used to see what products p’ should be sold to promote sale of p, e.g., run sale on diapers and raise beer’ price Shelf management: position certain items strategically Recommendation, e.g., Amazon’s people who bought X also bought Y High support needed, or no €€’s Only useful if many buy diapers & beer 4 2 2
Page 3
Supermarket shelf management – Market-ba Goal: Identify items that are bought togeth sufficiently many customers Approach: Process the sales data collected The Market-Basket Modelscanners to find dependencies among itemFall 2019 A classic rule: If one buys diaper and milk, then he is likely A large set of items, e.g., things sold in a supermarketDon’t be surprised if you find six-packs next I = {i1, i2, …, im} TID I tems A large set of baskets/transactions, 1 Br ead, Coke, M ilk Rules Disco e.g., the things one customer buys 2 Beer , Br ead on {Milk} --> { 3 Beer , Coke, Diaper , M ilk {Diaper, Mil in one visit to the store 4 Beer , Br ead, Diaper , M ilk Bi a set of items, and Bi I 5 Coke, Diaper , M ilk 1/10/2013 Jure Leskovec, Stanford CS246: Mining Massive Datasets, http://cs246.stanford.edu Transaction Database T: a set of transactions B = {B1, B2, …, Bn} Our interests: Identify associations among “items”, not “baskets” E.g., People who bought Diaper tend to buy Beer 6 Market-Baskets and Associations Fall 2019 ermarket shelf management A many-many mapping (– Market-basket model:association) between two kinds of things Goal: Identify items that are bought together byE.g., 90% of transactions that purchase diaper&milk also purchase beer sufficiently many customers Approach: Process the sales data collected with barcode Given a set of baskets, discover association rules scanners to find dependencies among itemsThe technology focuses on common events, not rare events (“long tail”) A classic rule: If one buys diaper and milk, then he is likely to buy beer2-step approach Don’t be surprised if you find six-packs next to diapers!Find frequent itemsets D I tems Generate association rules Br ead, Coke, M ilk Rules Discovered: Beer , Br ead {Milk} --> {Coke} Beer , Coke, Diaper , M ilk {Diaper, Milk} --> {Beer} Beer , Br ead, Diaper , M ilk Coke, Diaper , M ilk Jure Leskovec, Stanford CS246: Mining Massive Datasets, http://cs246.stanford.edu 2 7 3 3
Page 4
Causation vs. Association Fall 2019 Z X Y X Y In machine learning, X Y usually implies a causal relationship “a change in X (seen as cause) forces a change in Y (seen as effect)” causation is complex and difficult to prove relationship In rule mining, X Y is an association relationship “X is associated with Y ” Much easier to calculate and prove of less interest for medical research than for market research Association rules indicate only the existence of a statistical relationship between X and Y They do not specify the nature of the relationship 8 Fall 2019 Frequent Itemsets Simplest question: find sets of items, called itemsets, that appear “frequently” in the baskets E.g., {milk, diaper, beer} is an itemset Simplest question: Find sets of items that appear together Support for itemset“frequentlyA = the number of baskets containing all items in” in baskets A Often expressed as a fraction of the total number of baskets Support for itemset I: Number of baskets containing all items in Given a support thresholdIs, sets of items that appear in at least s baskets are called frequent itemsets TID I tems Often expressed as a fraction 1 Bread, Coke, M ilk Support of {Milk, Diaper} = 3 2 Beer, Bread of the total number of baskets 3 Beer, Coke, Diaper, M ilk Support of {Milk, Diaper, Beer} = 2 4 Beer, Bread, Diaper, M ilk Given a support threshold s, 5 Coke, Diaper, M ilk then sets of items that appear Support of {Beer, Bread} = 2 9 in at least sbaskets are called frequent itemsets 4 1/10/2013 Jure Leskovec, Stanford CS246: Mining Massive Datasets, http://cs246.stanford.edu 9 4
Page 5
Example: Frequent Itemsets Fall 2019 Items = {milk, cereal, diaper, beer, juice} Support = 3 baskets B1 = {m, c, b} B2 = {m, d, j} B3 = {m, b} B4 = {c, j} B5 = {m, d, b} B6 = {m, c, b, j} B7 = {c, b, j} B8 = {b, c} Frequent itemsets: {m}, {c}, {b}, {j}, {m,b}, {b,c}, {c,j} 10 The Market-Basket Model Fall 2019 A k-itemset is an itemset with k items E.g., A = {milk, diaper} is a 2-itemset E.g., A’ = {milk, bear, diaper} is a 3-itemset A transaction Bi contains an itemset A = {i1, i2,…,ik}, if A Bi E.g., basket B6= {milk, cereal, bear, diaper} contains the 3-itemset A’ An association rule is an implication of the form: {i1,i2,…,ik} → {j1,j2,…,jl}, where {i1,i2,…,ik}, {j1,j2,…,jl}, I, and {i1,i2,…,ik} {j1,j2,…,jl} = 11 5 5
Page 6
Association Rules Fall 2019 If-then rules about the contents of baskets {i1, i2,…,ik} → j means: “if a basket contains all of i1,…,ik then it is likely to contain j” A general form of an association rule is Body→Head[Support,Confidence] Antecedent, left-hand side (LHS), body Consequent, right-hand side (RHS), head Support, frequency Confidence, strength Example: diapers beer [50%, 60%] "IF buys diapers, THEN buys beer in 60% of the cases in 50% of the transactions“ 12 Support and Confidence Fall 2019 Customer buys both Customer Customer buys beer buys diaper Support for the rule A B: denotes the frequency of the rule within all transactions in the database T, i.e., the probability that a transaction contains the union of A and B support(A B [s,c]) = p(A B) = support({A,B}) Confidence of the rule A B: denotes the percentage of transactions in the database T, containing A which also contain B, i.e., the conditional probability that a transaction containing A also contains B confidence(A B [s,c]) = p(B|A) = p(A B) / p(A) = support({A,B}) / support({A}) 13 6 6
Page 7
Example: Confidence Fall 2019 B1 = {m, c, b} B2 = {m, d, j} B3 = {m, b} B4 = {c, j} B5 = {m, d, b} B6 = {m, c, b, j} B7 = {c, b, j} B8 = {b, c} An association rule: {m, b} → c Support ( {m, b} ) = 4, Support ( {m, b, c} ) = 2 Confidence ( {m, b} → c ) = 2/4 = 50% support(I j) conf(I j) support(I) 14 Finding Association Rules Fall 2019 Goal: Find all rules that satisfy the user-specified minimum support (minsup) and minimum confidence (minconf) support >= s and confidence >=c Key Features Completeness: find all rules Mining with data on disk (not in memory) Hard part: Finding the frequent itemsets If A → B has high support and confidence, then both A and B will be frequent 17 7 7
Page 8
How to Set the Appropriate MinSup? Fall 2019 Many real data sets have skewed support distribution If minsup is too high, we could miss itemsets involving interesting rare items (e.g., expensive products) If minsup is too low, it is computationally expensive and the number of itemsets is very large A single minsup threshold may not be always effective 18 Association Rule Mining Task Fall 2019 Brute‐force approach: List all possible association rules Given d unique items: Total number of itemsets = 2d Total number of ARs = R Compute the support and confidence for each rule Prune rules that fail the minsup and minconf thresholds Computationally prohibitive! 19 8 8
Page 9
Fall 2019 Counting Frequent Itemsets in One pass Each itemset is a candidate frequent itemset Count the support of each candidate by scanning the database Transactions List of Candidates TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs N 3 Milk, Diaper, Beer, Coke M 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke w Match each basket against every candidate Complexity ~ O(NMw) => Expensive since M = 2d !! Need a lot of memory space else swapping counts in/out is very “expensive” 20 Fall 2019 Frequent Itemset Generation Strategies Reduce the number of candidates (M) Complete search: M = 2d Use pruning techniques to reduce M Reduce the number of transactions (N) Reduce N as the size of itemset increases Reduce the number of comparisons (NM) Use efficient data structures to store the candidates or transactions No need to match every candidate against every transaction 21 9 9
Page 10
Reducing the Number of Candidates: Fall 2019 The Apriori algorithm Rules originating from the same itemset have identical support but can have different confidence Thus, we may decouple the support and confidence requirements Two steps: Frequent Itemsets: Find all itemsets I that have minimum support usually a computationally expensive phase! Key idea: (anti‐)monotonicity property of the support measure If an itemset is frequent, then all of its subsets must also be frequent If an itemset is not frequent, then all of its supersets cannot be frequent A,B: (AB) s(A) s(B) The support of an itemset never exceeds the support of its subsets This is known as the anti-monotone property of support 22 The Apriori algorithm Fall 2019 Rule generation: Use frequent itemsets I to generate rules For every subset A of I, generate rule A I \ A Since I is frequent, A is also frequent Variant 1: Perform a single pass to compute the rule confidence conf(A,BC,D) = supp(A,B,C,D)/supp(A,B) Variant 2: Filter out bigger rules from smaller ones Observation: If A,B,CD is below confidence, so is A,BC,D Output rules above confidence threshold In general, confidence does not have an anti‐monotone property conf(ABC D) can be larger or smaller than conf(AB D) But confidence of rules generated from the same itemset has an anti‐monotone property e.g., I = {A,B,C,D}: conf(ABCD)conf(ABCD)conf(ABCD) Confidence is anti‐monotone w.r.t. number of items on the RHS of the rule 23 10 10
Page 11
Example Fall 2019 B1 = {m, c, b} B2 = {m, d, j} B3 = {m, c, b, n} B4= {c, j} B5 = {m, d, b} B6 = {m, c, b, j} B7 = {c, b, j} B8 = {b, c} Support threshold s = 3, confidence c = 0.75 1) Frequent itemsets: {b,m} {b,c} {c,m} {c,j} {m,c,b} 2) Generate rules: b→m: c=4/6 b→c: c=5/6 b,c→m: c=3/5 m→b: c=4/5 … b,m→c: c=3/4 b→c,m: c=3/6 conf( AB ) = supp(A,B)/supp(A) 24 Frequent Itemset Generation Fall 2019 null A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE Given d items, there are 2d possible candidate itemsets ABCDE 26 11 11
Page 12
Illustrating the A-Priori Principle Fall 2019 null A B C D E AB AC AD AE BC BD BE CD CE DE Found to be Infrequent ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE Pruned ABCDE supersets 27 Rule Generation Example Fall 2019 28 12 12
Page 13
Fall 2019 How to Improve A-priori Efficiency? Dynamic itemset counting Add new candidate itemsets only when all of the subsets are estimated to be frequent Transaction Reduction A transaction that does not contain any frequent k-itemset is useless in subsequent scans Hash-based itemset counting A k-itemset whose corresponding hashing bucked count is below the threshold cannot be frequent Partitioning Any itemset that is potentially frequent in DB must be frequent in at least one of the partitions of the DB Sampling Mining on a subset of given data, lower support threshold and consider a method to determine completeness 29 Compacting Output Rules: Fall 2019 Classes of Itemsets To reduce the number of rules we can post-process and only output: Maximal Frequent itemsets: no immediate superset is frequent Can generate all frequent Maximal frequent Frequent itemsets (without support) free Closed itemsets: no immediate itemsets itemsets superset has the same count (>0) Can generate all frequent Frequent itemsets and their support closed Alternately: itemsets Free itemset: no immediate subset Frequent has the same count (>0) itemsets 30 13 13
Page 14
Fall 2019 Example: Maximal/Closed Frequent, but Count Maximal (s=3) Closed superset BC A 4 No No also frequent B 5 No Yes Frequent, and C 3 No No its only superset, ABC, not freq AB 4 Yes Yes AC 2 No No Superset BC BC 3 Yes Yes has same count ABC 2 No Yes Its only super- set, ABC, has smaller count 31 Fall 2019 Finding Frequent Itemsets 3838 14 14
Page 15
Fall 2019 Computing Itemsets Back to finding frequent itemsets Item Item Typically, data is kept in flat files rather than in a database Item system: Item Item Stored on disk, basket-by-basket Item Item Baskets are small but we have many baskets and many Item items Item Item Expand baskets into pairs, triples, etc. as you read Item Item baskets Use k nested loops to generate all itemsets of size k Etc. Note: To find frequent itemsets, we have to count them To count them, we have to generate them Items are positive integers, and boundaries between baskets are –1 39 Computation Model Fall 2019 In practice, association-rule algorithms read data in passes We measure the cost by the number of passes over the data => Cost of mining is the number of disk I/Os The approach: We always need to generate all the itemsets But we would only like to count/keep track of those itemsets that in the end turn out to be frequent For many frequent-itemset algorithms main-memory is the critical resource The number of different things we can count as we read baskets is limited by main memory 40 15 15
Page 16
Finding Frequent Pairs Fall 2019 The hardest turns out to be finding the frequent pairs of items {i1, i2} Often, frequent pairs are common, frequent triples are rare The probability of being frequent drops exponentially with the itemset size; number of itemsets grows more slowly with size Naïve Algorithm: Read file one, counting in main memory the occurrences of each pair From each basket of n items, generate its n(n-1)/2 pairs using two nested loops Problem: fails if n2 exceeds main memory Suppose 105 items, counts are 4-byte integers Number of pairs of items: 105(105-1)/2 = 5*109 Therefore, 2*1010 (20 gigabytes) of memory needed 41 Counting Pairs in Memory Fall 2019 Method (1) Two approaches: Approach 1: Count all pairs using a matrix keeping only the counts c Approach 2: Keep a table of triples [i,j,c]= “the count of the pair of items {i,j} is c” 4 per pair If integers and item ids are 4 bytes, we need approximately12 bytes for pairs with count>0 Plus some additional overhead to organize Method (2) the table for efficient search (“hashtable”) Note: Approach 1 only requires 4 bytes per pair Approach 2 uses 12 bytes per pair (but only for 12 per pairs with count > 0) occurring pair 42 16 16
Page 17
Triangular Matrix Fall 2019 Approach 1: Triangular Matrix n = total number of items a11 a12 a13 a14 a15 … Count pair of items {i,j} only if i<j a21 a22 a23 a24 a25 … So use only half of the two-dimensional a31 a32 a33 a34 a35 … array a41 a42 a43 a44 a45 … A more space-efficient way is to use a … … … … … … one-dimensional triangular array Keep pair counts in lexicographic order: {1,2},{1,3},…,{1,n},{2,3}, {2,4},…,{2,n},{3,4},… Every time you see a pair Pair {i,j} is at position: {i,j} from a basket, (i –1)(n – i /2) + j – i increment the count at the Total number of pairs n(n–1)/2; total corresponding position in triangular matrix bytes= 2n2 Triangular Matrix requires 4 bytes per pair 43 Comparing the two Approaches Fall 2019 Approach 2 uses 12 bytes per occurring pair (but only pairs with count > 0) Total bytes used is about 12p, where p is the number of pairs that actually occur Beats Approach 1 if less than 1/3 of possible pairs actually occur May require extra space for retrieval structure, e.g., a hash table Problem is if we have too many items so the pairs do not fit into memory. Can we do better? 44 17 17
Page 18
Fall 2019 A-Priori Algorithm 4545 Fall 2019 Example Market-Basket transactions TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke Item Count Items (1-itemsets) 4 Bread, Milk, Diaper, Beer Bread 4 5 Bread, Milk, Diaper, Coke Coke 2 Milk 4 Itemset Count Pairs (2-itemsets) Beer 3 {Bread,Milk} 3 Diaper 4 {Bread,Beer} 2 Eggs 1 (no need to generate {Bread,Diaper} 3 candidates involving Coke {Milk,Beer} 2 {Milk,Diaper} 3 or Eggs) {Beer,Diaper} 3 Minimum Support = 3 Triplets (3-itemsets) If every subset is considered, 6C + 6C + 6C = 41 Itemset Count 1 2 3 {Bread,Milk,Diaper} 2 With support-based pruning, 6 + 6 + 1 = 13 46 18 18
Page 19
Candidate Generation Fall 2019 Contrapositive for pairs: if item i does not appear in s baskets, then no pair including i can appear in s baskets A two-pass Basic principle (approach calledApriori): An itemset of size k+1 is candidate to be a-priorifrequent only iflimits the need forall of its subsets of size k are known to be frequent main memory Main idea: Key idea:Construct amonotonicitycandidate of size k+1 by combining two frequent itemsets of size k If a set of itemsPrune the generatedI appears atk+1-itemsets that do not have all k-subsets to be frequent leastSo, how does Astimes, so does every-Priori find frequent pairssubset? J of I. Contrapositive for pairs:A two-pass approach limiting the need for If itemmain memoryi does not appear incounts sbaskets, then no pair including i can appear in sbaskets 47 1/10/2013 Jure Leskovec, Stanford CS246: Mining Massive Datasets, http://cs246.stanford.edu 30 A-Priori Algorithm Fall 2019 Pass 1: Read baskets and count in main memory the occurrences of each item item counts frequent items Requires only memory proportional to #items Items that appear at least s times (minsup) are the frequent items counts of pairs Pass 2: Read baskets again and count of frequent items in main memory only those pairs where both elements were found in Pass 1 to Main Memory be frequent Requires memory proportional to square Pass 1 Pass 2 of frequent items only (for counts) Plus a list of the frequent items (so you know what must be counted) 48 19 19
Page 20
Details for A-Priori Fall 2019 You can use the triangular matrix method with m = number of frequent item counts frequent old items items items May save space compared with storing triples counts of pairs Trick: re-number frequent items of frequent items 1,2,…,m and keep a table relating new numbers to original item numbers Main Memory Pass 1 Pass 2 self-joining pruning 49 Frequent Triples, Etc. Fall 2019 For each k, we construct two sets of k –tuples (sets of size k): Ck = candidate k -sets = those that might be frequent sets (support > s) based on information from the pass for k –1 Lk = the set of truly frequent k-tuples Count All pairs Count All of items To be the items the pairs explained items from L 1 C Filter L Construct C Filter L Construct C 1 1 2 2 3 First Second pass Frequent pass Frequent items pairs 50 20 20
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !