Basic Concepts of Association Rule

Mining
 Association Rule Mining
Finding frequent patterns, associations,
correlations, or causal structures among sets of items
or objects in transaction databases, relational
databases, and other information repositories.
 Applications
Basket data analysis, cross-marketing, catalog
design, loss-leader analysis, clustering, classification,
etc.
 Examples
 Rule form: “Body  Head [support, confidence]”.
 buys(x, “diapers”)  buys(x, “beers”) [0.5%, 60%]
 major(x, “CS”) ^ takes(x, “DB”)  grade(x, “A”) [1%,
75%] 1
 I ={i1, i2, ...., in} a set of items

 J = P(I ) set of all subsets of the set of items, elements

of J are called itemsets

 Transaction T: T is subset of I

 Data Base: set of transactions

 An association rule is an implication of the form : X->

Y, where X, Y are disjoint subsets of I (elements of J )

 Problem: Find rules that have support and confidence

greater that user-specified minimum support and
minimun confidence

2
 Rule Measures: Support &
Confidence
 Simple Formulas:
 Confidence (AB) = #tuples containing both A & B /
#tuples containing A = P(B|A) = P(A U B ) / P (A)
 Support (AB) = #tuples containing both A & B/ total
number of tuples = P(A U B)
 What do they actually mean ?
Find all the rules X & Y  Z with minimum confidence
and support
 support, s, probability that a transaction contains
{X, Y, Z}
 confidence, c, conditional probability that a
transaction having {X, Y} also contains Z
3
Support & Confidence : An
Example
TransactionID ItemsBought
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F

Let minimum support 50%, and minimum

confidence 50%, then we have,
A  C (50%, 66.6%)
C  A (50%, 100%)

4
 Overview
Basic Concepts of Association Rule Mining
The Apriori Algorithm (Mining single
dimensional boolean association rules)
Methods to Improve Apriori’s Efficiency
Frequent-Pattern Growth (FP-Growth)
Method
From Association Analysis to Correlation
Analysis
Summary
5
 The Apriori Algorithm: Basics
The Apriori Algorithm is an influential algorithm
for mining frequent itemsets for boolean
association rules.

Key Concepts :
• Frequent Itemsets: The sets of item which has
minimum support (denoted by Li for ith-Itemset).
• Apriori Property: Any subset of frequent itemset
must be frequent.
• Join Operation: To find Lk , a set of candidate k-
itemsets is generated by joining Lk-1 with itself.
6
 The Apriori Algorithm in a
Nutshell
 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 k (k-itemset)
 Use the frequent itemsets to generate association
rules.
7
 The Apriori Algorithm : Pseudo
code
 Join Step: Ck is generated by joining Lk-1with itself
 Prune Step: Any (k-1)-itemset that is not frequent cannot be
a subset of a frequent k-itemset
Pseudo-code:
Ck: Candidate itemset of size k
Lk : frequent itemset of size k

L1 = {frequent items};
for (k = 1; Lk !=; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database do
increment the count of all candidates in Ck+1
that are contained in t
Lk+1 = candidates in Ck+1 with min_support
end
return k Lk;
8
The Apriori Algorithm: Example
 Consider a database, D ,
TID List of
Items consisting of 9 transactions.
T100 I1, I2, I5  Suppose min. support count
T200 I2, I4
required is 2 (i.e. min_sup =
2/9 = 22 % )
T300 I2, I3
 Let minimum confidence
T400 I1, I2, I4 required is 70%.
T500 I1, I3  We have to first find out the
T600 I2, I3 frequent itemset using Apriori
T700 I1, I3
algorithm.
 Then, Association rules will be
T800 I1, I2 ,I3, I5
generated using min. support
T900 I1, I2, I3 & min. confidence.

9
Step 1: Generating 1-itemset Frequent
Pattern
Itemse Sup.Count Compare candidate Itemse Sup.Count
Scan D for t support count with t
count of minimum support
{I1} 6 {I1} 6
each count
candidate {I2} 7 {I2} 7
{I3} 6 {I3} 6
{I4} 2 {I4} 2
{I5} 2 {I5} 2
C1 L1

• In the first iteration of the algorithm, each item is a member

of the set of candidate.
• The set of frequent 1-itemsets, L1 , consists of the candidate
1-itemsets satisfying minimum support.

10
 Step 2: Generating 2-itemset Frequent
Pattern
Itemset Itemse Sup. Items Sup
Generate Compare
t Count et Count
C2 {I1, I2} Scan D candidate
candidat for count {I1, 4 support {I1, 4
es from
{I1, I3} of each count with
I2} I2}
L1 {I1, I4} candidat minimum
e {I1, 4 support {I1, 4
{I1, I5} I3} count I3}
{I2, I3} {I1, 1 {I1, 2
{I2, I4} I4} I5}
{I2, I5} {I1, 2 {I2, 4
I5} I3}
{I3, I4} L2
{I2, 4 {I2, 2
{I3, I5}
I3} I4}
{I4, I5}
{I2, 2 {I2, 2
C2 I4} I5}
{I2, 2
I5} C2
11
{I3, 0
I4}
Step 2: Generating 2-itemset Frequent Pattern
[Cont.]

 To discover the set of frequent 2-itemsets, L2 , the

algorithm uses L1 Join L1 to generate a candidate
set of 2-itemsets, C2.
 Next, the transactions in D are scanned and the
support count for each candidate itemset in C2 is
accumulated (as shown in the middle table).
 The set of frequent 2-itemsets, L2 , is then
determined, consisting of those candidate 2-
itemsets in C2 having minimum support.
 Note: We haven’t used Apriori Property yet.

12
 Step 3: Generating 3-itemset Frequent
Pattern
Compare
Scan D Scan D Itemset Sup. candidate Itemset Sup
for count Itemset for count support
Count count with
Coun
of each of each
{I1, I2, I3} min t
candidat candidat {I1, I2, 2
e {I1, I2, I5} e I3} support {I1, I2, 2
count
{I1, I2, 2 I3}
C3 I5} C3
L
{I1, I2,3 2
I5}
• The generation of the set of candidate 3-itemsets, C3 ,
involves use of the Apriori Property.
• In order to find C3, we compute L2 Join L2.
• C3 = L2 Join L2 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3,
I4}, {I2, I3, I5}, {I2, I4, I5}}.
• Now, Join step is complete and Prune step will be used to
reduce the size of C3. Prune step helps to avoid heavy 13
computation due to large Ck.
Step 3: Generating 3-itemset Frequent Pattern
[Cont.]

 Based on the Apriori property that all subsets of a frequent itemset

must also be frequent, we can determine that four latter candidates
cannot possibly be frequent. How ?
 For example , lets take {I1, I2, I3}. The 2-item subsets of it are {I1, I2},
{I1, I3} & {I2, I3}. Since all 2-item subsets of {I1, I2, I3} are members
of L2, We will keep {I1, I2, I3} in C3.
 Lets take another example of {I2, I3, I5} which shows how the pruning
is performed. The 2-item subsets are {I2, I3}, {I2, I5} & {I3,I5}.
 BUT, {I3, I5} is not a member of L2 and hence it is not frequent violating
Apriori Property. Thus We will have to remove {I2, I3, I5} from C3.
 Therefore, C3 = {{I1, I2, I3}, {I1, I2, I5}} after checking for all members
of result of Join operation for Pruning.
 Now, the transactions in D are scanned in order to determine L3,
consisting of those candidates 3-itemsets in C3 having minimum
support.

14
 Step 4: Generating 4-itemset Frequent
Pattern
 The algorithm uses L3 Join L3 to generate a
candidate set of 4-itemsets, C4. Although the join
results in {{I1, I2, I3, I5}}, this itemset is pruned
since its subset {{I2, I3, I5}} is not frequent.
 Thus, C = φ , and algorithm terminates, having
4
found all of the frequent items. This completes
our Apriori Algorithm.
 What’s Next ?
These frequent itemsets will be used to generate
strong association rules ( where strong
association rules satisfy both minimum support &
minimum confidence).
15
 Step 5: Generating Association Rules from
Frequent Itemsets

 Procedure:
• For each frequent itemset “l”, generate all nonempty subsets
of l.
• For every nonempty subset s of l, output the rule “s  (l-s)” if
support_count(l) / support_count(s) >= min_conf where
min_conf is minimum confidence threshold.

 Back To Example:
We had L = {{I1}, {I2}, {I3}, {I4}, {I5}, {I1,I2}, {I1,I3}, {I1,I5},
{I2,I3}, {I2,I4}, {I2,I5}, {I1,I2,I3}, {I1,I2,I5}}.
 Lets take l = {I1,I2,I5}.
 Its all nonempty subsets are {I1,I2}, {I1,I5}, {I2,I5}, {I1}, {I2}, {I5}.

16
 Step 5: Generating Association Rules from
Frequent Itemsets [Cont.]

Let minimum confidence threshold is , say

70%.
The resulting association rules are shown
below, each listed with its confidence.
 R1: I1 ^ I2  I5
• Confidence = sc{I1,I2,I5}/sc{I1,I2} = 2/4 = 50%
• R1 is Rejected.
R2: I1 ^ I5  I2
• Confidence = sc{I1,I2,I5}/sc{I1,I5} = 2/2 = 100%
• R2 is Selected.
 R3: I2 ^ I5  I1
• Confidence = sc{I1,I2,I5}/sc{I2,I5} = 2/2 = 100%
• R3 is Selected.
17
Step 5: Generating Association Rules
from Frequent Itemsets [Cont.]
 R4: I1  I2 ^ I5
• Confidence = sc{I1,I2,I5}/sc{I1} = 2/6 = 33%
• R4 is Rejected.
 R5: I2  I1 ^ I5
• Confidence = sc{I1,I2,I5}/{I2} = 2/7 = 29%
• R5 is Rejected.
 R6: I5  I1 ^ I2
• Confidence = sc{I1,I2,I5}/ {I5} = 2/2 = 100%
• R6 is Selected.
In this way, We have found three strong
association rules.

18
 Overview
Basic Concepts of Association Rule Mining
The Apriori Algorithm (Mining single
dimensional boolean association rules)
Methods to Improve Apriori’s Efficiency
Frequent-Pattern Growth (FP-Growth)
Method
From Association Analysis to Correlation
Analysis
Summary
19
 Methods to Improve Apriori’s
Efficiency
 Hash-based itemset counting: A k-itemset whose corresponding
hashing bucket count is below the threshold cannot be frequent.
 Transaction reduction: A transaction that does not contain any
frequent k-itemset is useless in subsequent scans.
 Partitioning: Any itemset that is potentially frequent in DB must
be frequent in at least one of the partitions of DB.
 Sampling: mining on a subset of given data, lower support
threshold + a method to determine the completeness.
 Dynamic itemset counting: add new candidate itemsets only
when all of their subsets are estimated to be frequent.

20
 Overview
Basic Concepts of Association Rule Mining
The Apriori Algorithm (Mining single
dimensional boolean association rules)
Methods to Improve Apriori’s Efficiency
Frequent-Pattern Growth (FP-Growth)
Method
From Association Analysis to Correlation
Analysis
Summary
21
 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!
22
FP-Growth Method : An Example
TID List of Items  Consider the same previous
T100 I1, I2, I5 example of a database, D ,
consisting of 9 transactions.
T100 I2, I4  Suppose min. support count
required is 2 (i.e. min_sup =
T100 I2, I3 2/9 = 22 % )
T100 I1, I2, I4  The first scan of database is
same as Apriori, which
T100 I1, I3 derives the set of 1-itemsets
& their support counts.
T100 I2, I3  The set of frequent items is
T100 I1, I3 sorted in the order of
descending support count.
T100 I1, I2 ,I3, I5  The resulting set is denoted
as L = {I2:7, I1:6, I3:6, I4:2,
T100 I1, I2, I3
I5:2}
23
 FP-Growth Method: Construction of FP-
Tree
 First, create the root of the tree, labeled with “null”.
 Scan the database D a second time. (First time we scanned it to
create 1-itemset and then L).
 The items in each transaction are processed in L order (i.e.
sorted order).
 A branch is created for each transaction with items having their
support count separated by colon.
 Whenever the same node is encountered in another transaction,
we just increment the support count of the common node or
Prefix.
 To facilitate tree traversal, an item header table is built so that
each item points to its occurrences in the tree via a chain of
node-links.
 Now, The problem of mining frequent patterns in database is
transformed to that of mining the FP-Tree.
24
 FP-Growth Method: Construction of FP-
Tree
null{}
Ite Sup Node
m Coun -link I2: I1:
Id t 7 2
I2 7 I1:
I3: I4:
I1 6 4
2 1
I3 6 I3:
I4 2 2
I5 2 I3: I4:
I5: 2 1
1 I5:
1
An FP-Tree that registers compressed, frequent pattern information

25
 Mining the FP-Tree by Creating
Conditional (sub) pattern bases
Steps:
1. Start from each frequent length-1 pattern (as an
initial suffix pattern).
2. Construct its conditional pattern base which consists
of the set of prefix paths in the FP-Tree co-occurring
with suffix pattern.
3. Then, Construct its conditional FP-Tree & perform
mining on such a tree.
4. The pattern growth is achieved by concatenation of
the suffix pattern with the frequent patterns
generated from a conditional FP-Tree.
5. The union of all frequent patterns (generated by
step 4) gives the required frequent itemset.
26
 FP-Tree Example Continued
Item Conditional pattern Conditional Frequent pattern
base FP-Tree generated
I5 {(I2 I1: 1),(I2 I1 I3: <I2:2 , I1:2> I2 I5:2, I1 I5:2, I2 I1
1)} I5: 2
I4 {(I2 I1: 1),(I2: 1)} <I2: 2> I2 I4: 2
I3 {(I2 I1: 1),(I2: 2), (I1: <I2: 4, I1: I2 I3:4, I1, I3: 2 , I2 I1
2)} 2>,<I1:2> I3: 2
I2 {(I2: 4)} <I2: 4> I2 I1: 4
Mining the FP-Tree by creating conditional (sub) pattern
bases
Now, Following the above mentioned steps:
• Lets start from I5. The I5 is involved in 2 branches namely {I2 I1 I5: 1}
and {I2 I1 I3 I5: 1}.
• Therefore considering I5 as suffix, its 2 corresponding prefix paths would
be {I2 I1: 1} and {I2 I1 I3: 1}, which forms its conditional pattern base.

27
 FP-Tree Example Continued
 Out of these, Only I1 & I2 is selected in the conditional FP-Tree
because I3 is not satisfying the minimum support count.
For I1 , support count in conditional pattern base = 1 + 1 = 2
For I2 , support count in conditional pattern base = 1 + 1 = 2
For I3, support count in conditional pattern base = 1
Thus support count for I3 is less than required min_sup which is
2 here.
 Now , We have conditional FP-Tree with us.
 All frequent pattern corresponding to suffix I5 are generated by
considering all possible combinations of I5 and conditional FP-
Tree.
 The same procedure is applied to suffixes I4, I3 and I1.
 Note: I2 is not taken into consideration for suffix because it
doesn’t have any prefix at all.
28
 Why Frequent Pattern Growth
Fast ?
 Performance study shows
 FP-growth is an order of magnitude faster than
Apriori, and is also faster than tree-projection
 Reasoning
 No candidate generation, no candidate test
 Use compact data structure
 Eliminate repeated database scan
 Basic operation is counting and FP-tree building

29
 Overview
Basic Concepts of Association Rule Mining
The Apriori Algorithm (Mining single
dimensional boolean association rules)
Methods to Improve Apriori’s Efficiency
Frequent-Pattern Growth (FP-Growth)
Method
From Association Analysis to Correlation
Analysis
Summary
30
 Association & Correlation
 As we can see support-confidence framework
can be misleading; it can identify a rule
(A=>B) as interesting (strong) when, in fact
the occurrence of A might not imply the
occurrence of B.

 Correlation Analysis provides an alternative

framework for finding interesting
relationships, or to improve understanding of
meaning of some association rules (a lift of an
association rule).
31
 Correlation Concepts
 Two item sets A and B are independent (the
occurrence of A is independent of the
occurrence of item set B) iff
P(A  B) = P(A)  P(B)
 Otherwise A and B are dependent and
correlated

 The measure of correlation, or correlation

between A and B is given by the formula:
Corr(A,B)= P(A U B ) / P(A) . P(B)

32
 Correlation Concepts [Cont.]
 corr(A,B) >1 means that A and B are positively
correlated i.e. the occurrence of one implies the
occurrence of the other.

 corr(A,B) < 1 means that the occurrence of A is

negatively correlated with ( or discourages) the
occurrence of B.

 corr(A,B) =1 means that A and B are

independent and there is no correlation between
them.
33
 Association & Correlation
 The correlation formula can be re-written as
 Corr(A,B) = P(B|A) / P(B)

 We already know that

 Support(A B)= P(AUB)
 Confidence(A  B)= P(B|A)
 That means that, Confidence(A B)= corr(A,B) P(B)

 So correlation, support and confidence are all different, but

the correlation provides an extra information about the
association rule (A B).

 We say that the correlation corr(A,B) provides the LIFT of

the association rule (A=>B), i.e. A is said to increase (or
LIFT) the likelihood of B by the factor of the value returned
by the formula for corr(A,B).
34
 Correlation Rules
 A correlation rule is a set of items {i1, i2 , ….in},
where the items occurrences are correlated.

 The correlation value is given by the correlation

formula and we use Χ square test to determine if
correlation is statistically significant. The Χ square
test can also determine the negative correlation.
We can also form minimal correlated item sets,
etc…

 Limitations: Χ square test is less accurate on the

data tables that are sparse and can be misleading
for the contingency tables larger then 2x2
35
 Summary
 Association Rule Mining
 Finding interesting association or correlation relationships.
 Association rules are generated from frequent itemsets.
 Frequent itemsets are mined using Apriori algorithm or
Frequent-Pattern Growth method.
 Apriori property states that all the subsets of frequent
itemsets must also be frequent.
 Apriori algorithm uses frequent itemsets, join & prune
methods and Apriori property to derive strong association
rules.
 Frequent-Pattern Growth method avoids repeated database
scanning of Apriori algorithm.
 FP-Growth method is faster than Apriori algorithm.
 Correlation concepts & rules can be used to further support
our derived association rules.
36
 Questions ?

Thank You !!!

37