Data Mining
Chapter 5
Association Analysis: Basic Concepts
Introduction to Data Mining, 2nd Edition
by
Tan, Steinbach, Karpatne, Kumar
3/8/2021 Introduction to Data Mining, 2 nd Edition 1
Introduction
Data mining is the discovery of knowledge and
useful information from the large amounts of
data stored in databases.
Association Rules: describing association
relationships among the attributes in the set of
relevant data.
3/8/2021 Introduction to Data Mining, 2 nd Edition 22
Rules
Body ==> Consequent [ Support , Confidence ]
Body: represents the examined data.
Consequent: represents a discovered property
for the examined data.
Support: represents the percentage of the
records satisfying the body or the consequent.
Confidence: represents the percentage of the
records satisfying both the body and the
consequent to those satisfying only the body.
3/8/2021 Introduction to Data Mining, 2 nd Edition 33
Association Rules Examples
Basket Data
Tea ^ Milk ==> Sugar [0.3 , 0.9]
Relational Data
[Link] = Heart ^ [Link] = Male ==> [Link] > 50 [0.4 , 0.7]
Object-Oriented Data
[Link] = { sport , art } ==> [Link]() = Young [0.5 , 0.8]
3/8/2021 Introduction to Data Mining, 2 nd Edition 44
Apriori Algorithm - Association Rules
Data Mining
3/8/2021 Introduction to Data Mining, 2 nd Edition 5
Association Rule Mining Task
Given a set of transactions T, the goal of
association rule mining is to find all rules having
– support ≥ minsup threshold
– confidence ≥ minconf threshold
Brute-force approach:
– List all possible association rules
– Compute the support and confidence for each rule
– Prune rules that fail the minsup and minconf
thresholds
Computationally prohibitive!
3/8/2021 Introduction to Data Mining, 2 nd Edition 6
• For the given dataset, apply Apriory
algorithm to discover association rules
among image tags.
• Assume that:
o min_support =40%
o min_confidence =70%.
• Generate association rules from the
frequent itemsets. Calculate the
confidence of each rule and identify all
strong association rules.
3/8/2021 Introduction to Data Mining, 2 nd Edition 7
• Generate candidates itemsets (Ck) and
qualified frequent itemsets (Lk) step by
step until the largest frequent itemset is
generated.
3/8/2021 Introduction to Data Mining, 2 nd Edition 8
Bread, Butter, Milk, Diapers, Beer
Min_support = 40%,
Min_support_count = min_support ×itemset_count
=40% ×5
=2
3/8/2021 Introduction to Data Mining, 2 nd Edition 9
Bread, Butter, Milk, Diapers, Beer
3/8/2021 Introduction to Data Mining, 2 nd Edition 10
Bread, Butter, Milk, Diapers, Beer
3/8/2021 Introduction to Data Mining, 2 nd Edition 11
• Min_confidence= 70%
• Confidence (XY) = P(PY I X) = P(X U Y)/P(X)
• We have 5 frequent itemsets:
{Bread, Butter}, {Bread. Milk}, {Butter. Milk},
{Diapers, Beer} and {Bread, Butter, Butter, Milk}.
• Therefore, candidate rules are:
• For {Bread, Butter}:
Bread Butter =3/3 =100% (Strong)
Butter Bread =3/3 =100% (Strong)
• For {Bread, Milk}:
Bread Milk =2/3=67% X
Milk Bread = 2/2= 100% (Strong)
3/8/2021 Introduction to Data Mining, 2 nd Edition 12
• Min_confidence= 70%
• Confidence (XY) = P(PY I X) = P(X U Y)/P(X)
• We have 5 frequent itemsets:
{Bread, Butter}, {Bread. Milk}, {Butter. Milk},
{Diapers, Beer} and {Bread, Butter, Butter, Milk}.
• Therefore, candidate rules are:
• For {Butter, Milk}:
Butter Milk =2/3 =67% X
Milk Butter =2/2 =100% (Strong)
• For {Diapers, Beer}:
Diapers Beer =2/3=67% X
Beer Diapers = 2/2= 100% (Strong)
3/8/2021 Introduction to Data Mining, 2 nd Edition 13
• Min_confidence= 70%
• Confidence (XY) = P(PY I X) = P(X U Y)/P(X)
• We have 5 frequent itemsets:
• {Bread, Butter}, {Bread. Milk}, {Butter. Milk},
{Diapers, Beer} and {Bread, Butter, Butter, Milk}.
• Therefore, candidate rules are:
• For {Bread, Butter, Milk}:
Bread, Butter Milk =2/3 =67% X
Bread, Milk Butter =2/2 =100% (Strong)
Milk, Butter Bread =2/2 =100% (Strong)
Bread Butter, Milk =2/3 =67% X
Butter Bread, Milk =2/3 =67% X
Milk Bread, Butter =2/2 =100% (Strong)
3/8/2021 Introduction to Data Mining, 2 nd Edition 14
Frequent Itemset Generation
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
ABCDE candidate itemsets
3/8/2021 Introduction to Data Mining, 2 nd Edition 15
Reducing Number of Candidates
Apriori principle:
– If an itemset is frequent, then all of its subsets must also
be frequent
Apriori principle holds due to the following property
of the support measure:
X , Y : ( X Y ) s( X ) s(Y )
– Support of an itemset never exceeds the support of its
subsets
– This is known as the anti-monotone property of support
3/8/2021 Introduction to Data Mining, 2 nd Edition 16
Illustrating Apriori Principle
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
3/8/2021 Introduction to Data Mining, 2 nd Edition 17
Factors Affecting Complexity of
Apriori
Choice of minimum support threshold
– lowering support threshold results in more frequent itemsets
– this may increase number of candidates and max length of
frequent itemsets
Dimensionality (number of items) of the data set
– More space is needed to store support count of itemsets
– if number of frequent itemsets also increases, both computation
and I/O costs may also increase
Size of database
– run time of algorithm increases with number of transactions
Average transaction width
– transaction width increases the max length of frequent itemsets
– number of subsets in a transaction increases with its width,
increasing computation time for support counting
3/8/2021 Introduction to Data Mining, 2 nd Edition 18