advertisement

5. Association Rules Market Basket Analysis and Itemsets APRIORI Efficient Association Rules Multilevel Association Rules Post-processing Spring 2005 CSE 572, CBS 598 by H. Liu 1 Transactional Data Market basket example: Basket1: {bread, cheese, milk} Basket2: {apple, eggs, salt, yogurt} … Basketn: {biscuit, eggs, milk} Definitions: – An item: an article in a basket, or an attribute-value pair – A transaction: items purchased in a basket; it may have TID (transaction ID) – A transactional dataset: A set of transactions Spring 2005 CSE 572, CBS 598 by H. Liu 2 Itemsets and Association Rules • An itemset is a set of items. – E.g., {milk, bread, cereal} is an itemset. • A k-itemset is an itemset with k items. • Given a dataset D, an itemset X has a (frequency) count in D • An association rule is about relationships between two disjoint itemsets X and Y XY • It presents the pattern when X occurs, Y also occurs Spring 2005 CSE 572, CBS 598 by H. Liu 3 Use of Association Rules • Association rules do not represent any sort of causality or correlation between the two itemsets. – X Y does not mean X causes Y, so no Causality – X Y can be different from Y X, unlike correlation • Association rules assist in marketing, targeted advertising, floor planning, inventory control, churning management, homeland security, … Spring 2005 CSE 572, CBS 598 by H. Liu 4 Support and Confidence • support of X in D is count(X)/|D| • For an association rule XY, we can calculate – support (XY) = support (XY) – confidence (XY) = support (XY)/support (X) • Relate Support (S) and Confidence (C) to Joint and Conditional probabilities • There could be exponentially many A-rules • Interesting association rules are (for now) those whose S and C are greater than minSup and minConf (some thresholds set by data miners) Spring 2005 CSE 572, CBS 598 by H. Liu 5 • How is it different from other algorithms – Classification (supervised learning -> classifiers) – Clustering (unsupervised learning -> clusters) • Major steps in association rule mining – Frequent itemsets generation – Rule derivation • Use of support and confidence in association mining – S for frequent itemsets – C for rule derivation Spring 2005 CSE 572, CBS 598 by H. Liu 6 Example • Data set D TID Itemsets T100 134 T200 235 T300 1235 T400 25 Count, Support, Confidence: Count(13)=2 |D| = 4 Support(13)=0.5 Support(32)=0.5 Confidence(32)=0.67 Spring 2005 CSE 572, CBS 598 by H. Liu 7 Frequent itemsets • A frequent (used to be called large) itemset is an itemset whose support (S) is ≥ minSup. • Apriori property (downward closure): any subsets of a frequent itemset are also frequent itemsets ABC AB A Spring 2005 ABD AC AD B ACD BC BD C BCD CD D CSE 572, CBS 598 by H. Liu 8 APRIORI • • Using the downward closure, we can prune unnecessary branches for further consideration APRIORI 1. 2. 3. 4. • k=1 Find frequent set Lk from Ck of all candidate itemsets Form Ck+1 from Lk; k = k + 1 Repeat 2-3 until Ck is empty Details about steps 2 and 3 – Step 2: scan D and count each itemset in Ck , if it’s greater than minSup, it is frequent – Step 3: next slide Spring 2005 CSE 572, CBS 598 by H. Liu 9 Apriori’s Candidate Generation • For k=1, C1 = all 1-itemsets. • For k>1, generate Ck from Lk-1 as follows: – The join step Ck = k-2 way join of Lk-1 with itself If both {a1, …,ak-2, ak-1} & {a1, …, ak-2, ak} are in Lk-1, then add {a1, …,ak-2, ak-1, ak} to Ck (We keep items sorted). – The prune step Remove {a1, …,ak-2, ak-1, ak} if it contains a nonfrequent (k-1) subset Spring 2005 CSE 572, CBS 598 by H. Liu 10 Example – Finding frequent itemsets Dataset D TID Items T100 a1 a3 a4 T200 a2 a3 a5 T300 a1 a2 a3 a5 T400 a2 a5 1. scan D C1: a1:2, a2:3, a3:3, a4:1, a5:3 L1: a1:2, a2:3, a3:3, C2: a1a2, a1a3, a1a5, a2a3, a2a5, a3a5 a5:3 2. scan D C2: a1a2:1, a1a3:2, a1a5:1, a2a3:2, a2a5:3, a3a5:2 L2: a1a3:2, a2a3:2, a2a5:3, a3a5:2 C3: a2a3a5 minSup=0.5 Pruned C3: a2a3a5 3. scan D L3: a2a3a5:2 Spring 2005 CSE 572, CBS 598 by H. Liu 11 Order of items can make difference in porcess Dataset D 1. scan D C1: 1:2, 2:3, 3:3, 4:1, 5:3 TID Items L1: 1:2, 2:3, 3:3, T100 134 C2: 12, 13, 15, 23, 25, 35 T200 235 T300 1235 T400 25 5:3 2. scan D C2: 12:1, 13:2, 15:1, 23:2, 25:3, 35:2 Suppose the order of items is: 5,4,3,2,1 L2: 31:2, 32:2, 52:3, 53:2 C3: 321, 532 minSup=0.5 Pruned C3: 532 3. scan D L3: 532:2 Spring 2005 CSE 572, CBS 598 by H. Liu 12 Derive rules from frequent itemsets • Frequent itemsets != association rules • One more step is required to find association rules • For each frequent itemset X, For each proper nonempty subset A of X, – Let B = X - A – A B is an association rule if • Confidence (A B) ≥ minConf, where support (A B) = support (AB), and confidence (A B) = support (AB) / support (A) Spring 2005 CSE 572, CBS 598 by H. Liu 13 Example – deriving rules from frequent itemses • Suppose 234 is frequent, with supp=50% – Proper nonempty subsets: 23, 24, 34, 2, 3, 4, with supp=50%, 50%, 75%, 75%, 75%, 75% respectively – These generate these association rules: • • • • • • • Spring 2005 23 => 4, confidence=100% 24 => 3, confidence=100% 34 => 2, confidence=67% 2 => 34, confidence=67% 3 => 24, confidence=67% 4 => 23, confidence=67% All rules have support = 50% CSE 572, CBS 598 by H. Liu 14 Deriving rules • To recap, in order to obtain A B, we need to have Support(AB) and Support(A) • This step is not as time-consuming as frequent itemsets generation – Why? • It’s also easy to speedup using techniques such as parallel processing. – How? • Do we really need candidate generation for deriving association rules? – Frequent-Pattern Growth (FP-Tree) Spring 2005 CSE 572, CBS 598 by H. Liu 15 Efficiency Improvement • Can we improve efficiency? – Pruning without checking all k - 1 subsets? – Joining and pruning without looping over entire Lk-1?. • Yes, one way is to use hash trees. • One hash tree is created for each pass k – Or one hash tree for k-itemset, k = 1, 2, … Spring 2005 CSE 572, CBS 598 by H. Liu 16 Hash Tree • Storing all candidate k-itemsets and their counts. • Internal node v at level m “contains” bucket pointers – Which branch next? Use hash of mth item to decide – Leaf nodes contain lists of itemsets and counts • E.g., C2: 12, 13, 15, 23, 25, 35; {} |2 /1 \3 /2 |3 \5 /3 \5 /5 [12:][13:] [15:] [23:] [25:] [35:] Spring 2005 use identity hash function ** root ** edge+label CSE 572, CBS 598 by H. Liu ** leaves 17 • How to join using hash tree? – Only try to join frequent k-1 itemsets with common parents in the hash tree • How to prune using hash tree? – To determine if a k-1 itemset is frequent with hash tree can avoid going through all itemsets of Lk-1. (The same idea as the previous item) • Added benefit: – No need to enumerate all k-subsets of transactions. Use traversal to limit consideration of such subsets. – Or enumeration is replaced by tree traversal. Spring 2005 CSE 572, CBS 598 by H. Liu 18 Further Improvement • Speed up searching and matching • Reduce number of transactions (a kind of instance selection) • Reduce number of passes over data on disk • Reduce number of subsets per transaction that must be considered • Reduce number of candidates Spring 2005 CSE 572, CBS 598 by H. Liu 19 Speed up searching and matching • Use hash counts to filter candidates (see example) • Method: When counting candidate k-1 itemsets, get counts of “hash-groups” of k-itemsets – Use a hash function h on k-itemsets – For each transaction t and k-subset s of t, add 1 to count of h(s) – Remove candidates q generated by Apriori if h(q)’s count <= minSupp – The idea is quite useful for k=2, but often not so useful elsewhere. (For sparse data, k=2 can be the most expensive for Apriori. Why?) Spring 2005 CSE 572, CBS 598 by H. Liu 20 1,3,4 Hash-based Example 2,3,5 1,2,3,5 2,5 • Suppose h2 is: – h2(x,y) = ((order of x) * 10 + (order of y)) mod 7 – E.g., h2(1,4) = 0, h2(1,5) = 1, … bucket0 14 35 counts 3 bucket1 bucket2 bucket3 bucket4 bucket5 bucket6 15 1 23 2 24 25 0 3 12 13 1 34 3 • Then 2-itemsets hashed to buckets 1, 5 cannot be frequent (e.g. 15, 12), so remove them from C2 Spring 2005 CSE 572, CBS 598 by H. Liu 21 Working on transactions • Remove transactions that do not contain any frequent k-itemsets in each scan • Remove from transactions those items that are not members of any candidate k-itemsets – e.g., if 12, 24, 14 are the only candidate itemsets contained in 1234, then remove item 3 – if 12, 24 are the only candidate itemsets contained in transaction 1234, then remove the transaction from next round of scan. • Reducing data size leads to less reading and processing time, but extra writing time Spring 2005 CSE 572, CBS 598 by H. Liu 22 Reducing Scans via Partitioning • Divide the dataset D into m portions, D1, D2,…, Dm, so that each portion can fit into memory. • Find frequent itemsets Fi in Di, with support ≥ minSup, for each i. – If it is frequent in D, it must be frequent in some Di. • The union of all Fi forms a candidate set of the frequent itemsets in D; get their counts. • Often this requires only two scans of D. Spring 2005 CSE 572, CBS 598 by H. Liu 23 Unique Features of Association Rules • vs. classification – Right hand side can have any number of items – It can find a classification like rule X c in a different way: such a rule is not about differentiating classes, but about what (X) describes class c • vs. clustering – It does not have to have class labels – For X Y, if Y is considered as a cluster, it can form different clusters sharing the same description (X). Spring 2005 CSE 572, CBS 598 by H. Liu 24 Other Association Rules • Multilevel Association Rules – Often there exist structures in data – E.g., yahoo hierarchy, food hierarchy – Adjusting minSup for each level • Constraint-based Association Rules – – – – – Knowledge constraints Data constraints Dimension/level constraints Interestingness constraints Rule constraints Spring 2005 CSE 572, CBS 598 by H. Liu 25 Measuring Interestingness - Discussion • What are interesting association rules – Novel and actionable • Association mining aims to look for “valid, novel, useful (= actionable) patterns.” Support and confidence are not sufficient for measuring interestingness. • Large support & confidence thresholds only a small number of association rules, and they are likely “folklores”, or known facts. • Small support & confidence thresholds too many association rules. Spring 2005 CSE 572, CBS 598 by H. Liu 26 Post-processing • Need some methods to help select the (likely) “interesting” ones from numerous rules • Independence test – A BC is perhaps interesting if p(BC|A) differs greatly from p(B|A) * p(C|A). – If p(BC|A) is approximately equal to p(B|A) * p(C|A), then the information of A BC is likely to have been captured by A B and A C already. Not interesting. – Often people are more familiar with simpler associations than more complex ones. Spring 2005 CSE 572, CBS 598 by H. Liu 27 Summary • Association rules are different from other data mining algorithms. • Apriori property can reduce search space. • Mining long association rules is a daunting task – Students are encouraged to mine long rules • Association rules can find many applications. • Frequent itemsets are a practically useful concept. Spring 2005 CSE 572, CBS 598 by H. Liu 28 Bibliography • J. Han and M. Kamber. Data Mining – Concepts and Techniques. 2001. Morgan Kaufmann. • M. Kantardzic. Data Mining – Concepts, Models, Methods, and Algorithms. 2003. IEEE. • M. H. Dunham. Data Mining – Introductory and Advanced Topics. • I.H. Witten and E. Frank. Data Mining – Practical Machine Learning Tools and Techniques with Java Implementations. 2000. Morgan Kaufmann. Spring 2005 CSE 572, CBS 598 by H. Liu 29