ASSOCIATION RULES IN DATA MINING :ASSOCIATION RULES IN DATA MINING SUSHIL KULKARNI


Mining Association Rules in Large Databases :Mining Association Rules in Large Databases Association rule mining Algorithms Apriori and FP-Growth


What Is Association Rule Mining? :What Is Association Rule Mining? Association rule mining: Finding frequent patterns, associations, correlations, or causal structures among sets of items or objects in transactional databases, relational databases, and other information repositories Motivation (market basket analysis): If customers are buying milk, how likely is that they also buy bread? Such rules help retailers to: plan the shelf space: by placing milk close to bread they may increase the sales provide advertisements/recommendation to customers that are likely to buy some products put items that are likely to be bought together on discount, in order to increase the sales


What Is Association Rule Mining? :What Is Association Rule Mining? Applications: Basket data analysis, cross-marketing, catalog design, loss-leader analysis, clustering, classification, etc. Rule form: “Body ® Head [support, confidence]”. Examples. buys(x, “Shirts”) ® buys(x, “beers”) [0.5%, 60%] major(x, “CS”) ^ takes(x, “DB”) ® grade(x, “A”) [1%, 75%]


Association Rules: Basic Concepts :Association Rules: Basic Concepts Given: (1) database of transactions, (2) each transaction is a list of items (purchased by a customer in a visit) Find: all rules that correlate the presence of one set of items with that of another set of items E.g., 98% of people who purchase tires and auto accessories also get automotive services done


What are the components of rules? :What are the components of rules? In data mining, a set of items is referred to as an itemset Let D be database of transactions e.g.: Let I be the set of items that appear in the database, e.g., I={A,B,C,D,E,F} A rule is defined by X  Y, where XI, YI, and XY= e.g.: {B,C}  {E} is a rule


Are all the rules interesting? :Are all the rules interesting? The number of potential rules is huge. We may not be interested in all of them. We are interesting in rules that: their items appear frequently in the database they hold with a high probability We use the following thresholds: the support of a rule indicates how frequently its items appear in the database the confidence of a rule indicates the probability that if the left hand side appears in a T, also the right hand side will.


Rule Measures: Support and Confidence :Rule Measures: Support and Confidence Find all the rules X  Y with minimum confidence and support support, s, probability that a transaction contains {X  Y} confidence, c, conditional probability that a transaction having X also contains Y Let minimum support 50%, and minimum confidence 50%, we have A  C (50%, 66.6%) C  A (50%, 100%) Customer buys shirts Customer buys both Customer buys beer


Example :TID date items_bought 100 10/10/99 {F,A,D,B} 200 15/10/99 {D,A,C,E,B} 300 19/10/99 {C,A,B,E} 400 20/10/99 {B,A,D} Example What is the support and confidence of the rule: {B,D}  {A} Support: percentage of tuples that contain {A,B,D} = Confidence: 75% 100%


Association Rule Mining :Association Rule Mining Boolean vs. quantitative associations (Based on the types of values handled) buys(x, “SQLServer”) ^ buys(x, “DMBook”) ® buys(x, “DBMiner”) [0.2%, 60%] age(x, “30..39”) ^ income(x, “42..48T”) ® buys(x, “PC”) [1%, 75%] Single dimension vs. multiple dimensional associations (see ex. Above) Single level vs. multiple-level analysis age(x, “30..39”) ® buys(x, “laptop”) age(x, “30..39”) ® buys(x, “computer”) Various extensions Correlation, causality analysis Association does not necessarily imply correlation or causality Maximal frequent itemsets: no frequent supersets frequent closed itemsets: no superset with the same support


Mining Association Rules :Mining Association Rules Two-step approach: Frequent Itemset Generation Generate all itemsets whose support  minsup Rule Generation Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemset Frequent itemset generation is still computationally expensive


Mining Association Rules Example :Mining Association Rules Example For rule A  C: support = support({A C}) = 50% confidence = support({A C})/support({A}) = 66.6% The Apriori principle: Any subset of a frequent itemset must be frequent! Min. support 50% Min. confidence 50%


Mining Frequent Item sets: Key Step :Mining Frequent Item sets: Key Step Find the frequent itemsets: the sets of items that have minimum support A subset of a frequent itemset must also be a frequent itemset i.e., if {AB} is a frequent itemset, both {A} and {B} should be a frequent itemset Iteratively find frequent itemsets with cardinality from 1 to m (m-itemset): Use frequent k-itemsets to explore (k+1)-itemsets. Use the frequent itemsets to generate association rules.


Visualization of the level-wise process :Visualization of the level-wise process Question: Can ADF be frequent? D is frequent but not AF so ADF is not frequent Assume that following are frequent item sets


Mining Association Rules in Large Databases :Mining Association Rules in Large Databases Association rule mining Algorithms Apriori and FP-Growth Max and closed patterns Mining various kinds of association/correlation rules


The Apriori Algorithm (the general idea) :The Apriori Algorithm (the general idea) Find frequent items and put them to Lk (k=1) Use Lk to generate a collection of candidate itemsets Ck+1 with size (k+1) Scan the database to find which itemsets in Ck+1 are frequent and put them into Lk+1 If Lk+1 is not empty k=k+1 GOTO 2


The Apriori Algorithm — Example: min sup>1 :The Apriori Algorithm — Example: min sup>1 Database D Scan D C1 L1 L2 C2 C2 Scan D C3 L3 Scan D min_sup=2=50%


How to Generate Candidates? :How to Generate Candidates? Suppose the items in Lk are listed in an order Step 1: self-joining Lk (IN SQL) insert into Ck+1 select p.item1, p.item2, …, p.itemk, q.itemk from Lk p, Lk q where p.item1=q.item1, …, p.itemk-1=q.itemk-1, p.itemk < q.itemk Step 2: pruning forall itemsets c in Ck+1 do forall k-subsets s of c do if (s is not in Lk) then delete c from Ck+1


Example of Candidates Generation :Example of Candidates Generation L3={abc, abd, acd, ace, bcd} Self-joining: L3*L3 abcd from abc and abd acde from acd and ace Pruning: acde is removed because ade is not in L3 C4={abcd} X


AprioriTid: Use D only for first pass :AprioriTid: Use D only for first pass The database is not used after the 1st pass. Instead, the set Ck’ is used for each step, Ck’ = : each Xk is a potentially frequent itemset in transaction with id=TID. At each step Ck’ is generated from Ck-1’ at the pruning step of constructing Ck and used to compute Lk. For small values of k, Ck’ could be larger than the database!


AprioriTid Example (min_sup=2) :AprioriTid Example (min_sup=2) Database D L1 L2 C2 C3’ C1’ C1’ C3 L3


Candidate Item sets for rule generation from given itemset :Candidate Item sets for rule generation from given itemset Consider the itemset {A,B,C,D,E} . There are 2 5 = 32 nodes in the following figure. Each of this node elements (item set) are possible candidate itemset for rule generation. See example below.


Frequent Itemset Generation :Frequent Itemset Generation


Illustrating Apriori Principle :Illustrating Apriori Principle


Rule Generation :Rule Generation Given a frequent itemset L, find all non-empty subsets F  L such that F  L – F satisfies the minimum confidence requirement If {A,B,C,D} is a frequent itemset, candidate rules: A BCD, B ACD, C ABD, D ABC AB CD, AC  BD, AD  BC, BC AD, BD AC, CD AB, ABC D, ABD C, ACD B, BCD A, If |L| = k, then there are 2k – 2 candidate association rules (ignoring L   and   L)


Rule Generation :Rule Generation How to efficiently generate rules from frequent itemsets? Low confidence Rule is to be removed.


Rule Generation for Apriori Algorithm :Rule Generation for Apriori Algorithm Lattice of rules Low Confidence Rule


Rule Generation for Apriori Algorithm :Rule Generation for Apriori Algorithm Candidate rule is generated by merging two rules that share the same prefixin the rule consequent join(CD=>AB,BD=>AC)would produce the candidaterule D => ABC Prune rule D=>ABC if itssubset AD=>BC does not havehigh confidence


Generating assoc. rules from frequent itemsets :Generating assoc. rules from frequent itemsets Assume that we have discovered the frequent itemsets and their support How do we generate association rules? Frequent itemsets: ? T is a set and S is a subset of T. l is the FI of T but not in S.. Generate rule T  S(T-l) if sup(T)/sup(T-l)min_conf   X {2,3,5}=> {2,3} , 2/2> 75% {2,3,5}=> {2,5} , 2/3 {3,5} , 2/2> 75%


Discovering Rules :Discovering Rules Naïve Algorithm for each frequent itemset l do for each subset c of l do if (support(l ) / support(l - c) >= minconf) then output the rule (l – c )  c, with confidence = support(l ) / support (l - c ) and support = support(l )


Discovering Rules :Discovering Rules Lemma. If consequent c generates a valid rule, so do all subsets of c. (e.g. X  YZ, then XY  Z and XZ  Y) Example: Consider a frequent itemset ABCDE If ACDE  B and ABCE  D are the only one-consequent rules with minimum support confidence, then ACE  BD is the only other rule that needs to be tested


FP-growth: Mining Frequent Patterns Without Candidate Generation :FP-growth: Mining Frequent Patterns Without Candidate Generation Compress a large database into a compact, Frequent-Pattern tree (FP-tree) structure highly condensed, but complete for frequent pattern mining avoid costly database scans Develop an efficient, FP-tree-based frequent pattern mining method A divide-and-conquer methodology: decompose mining tasks into smaller ones Avoid candidate generation: sub-database test only!


FP-tree Construction from a Transactional DB :FP-tree Construction from a Transactional DB Item frequency f 4 c 4 a 3 b 3 m 3 p 3 min_support = 3 TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} Steps: Scan DB once, find frequent 1-itemsets (single item patterns) Order frequent items in descending order of their frequency Scan DB again, construct FP-tree


FP-tree Construction :FP-tree Construction root TID freq. Items bought 100 {f, c, a, m, p} 200 {f, c, a, b, m} 300 {f, b} 400 {c, p, b} 500 {f, c, a, m, p} Item frequency f 4 c 4 a 3 b 3 m 3 p 3 min_support = 3


FP-tree Construction :FP-tree Construction root Item frequency f 4 c 4 a 3 b 3 m 3 p 3 min_support = 3 b:1 m:1 TID freq. Items bought 100 {f, c, a, m, p} 200 {f, c, a, b, m} 300 {f, b} 400 {c, p, b} 500 {f, c, a, m, p}


FP-tree Construction :FP-tree Construction root Item frequency f 4 c 4 a 3 b 3 m 3 p 3 min_support = 3 b:1 m:1 b:1 TID freq. Items bought 100 {f, c, a, m, p} 200 {f, c, a, b, m} 300 {f, b} 400 {c, p, b} 500 {f, c, a, m, p}


FP-tree Construction :FP-tree Construction root Item frequency f 4 c 4 a 3 b 3 m 3 p 3 min_support = 3 b:1 m:1 b:1 TID freq. Items bought 100 {f, c, a, m, p} 200 {f, c, a, b, m} 300 {f, b} 400 {c, p, b} 500 {f, c, a, m, p} c:1 b:1 p:1


Benefits of the FP-tree Structure :Benefits of the FP-tree Structure Completeness: never breaks a long pattern of any transaction preserves complete information for frequent pattern mining


Mining Frequent Patterns Using FP-tree :Mining Frequent Patterns Using FP-tree General idea (divide-and-conquer) Recursively grow frequent pattern path using the FP-tree Method For each item, construct its conditional pattern-base, and then its conditional FP-tree Repeat the process on each newly created conditional FP-tree Until the resulting FP-tree is empty, or it contains only one path (single path will generate all the combinations of its sub-paths, each of which is a frequent pattern)


Mining Frequent Patterns Using the FP-tree (cont’d) :Mining Frequent Patterns Using the FP-tree (cont’d) Start with last item in order (i.e., p). Follow node pointers and traverse only the paths containing p. Accumulate all of transformed prefix paths of that item to form a conditional pattern base Construct a new FP-tree based on this pattern, by merging all paths and keeping nodes that appear sup times. This leads to only one branch c:3 Thus we derive only one frequent pattern cont. p. Pattern cp


Mining Frequent Patterns Using the FP-tree (cont’d) :Mining Frequent Patterns Using the FP-tree (cont’d) Move to next least frequent item in order, i.e., m Follow node pointers and traverse only the paths containing m. Accumulate all of transformed prefix paths of that item to form a conditional pattern base f:4 c:3 a:3 m:2 m m:1 b:1 m-conditional pattern base: fca:2, fcab:1 All frequent patterns that include m m, fm, cm, am, fcm, fam, cam, fcam  


Slide 42:THANKS !


Slide 43:THANKS !