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 XI, YI, and XY=
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’ = <TID, {Xk}> : 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< 75% {2,3,5}=> {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 !