Apriori Algorithm

By
zahra’a yahya zakaryia
SUPERVISED BY
Prof Dr. Abdulbasit ALAZZAWI

3/8/2021 Introduction to Data Mining, 2 nd Edition 1

Association Rule Mining

 Given a set of transactions, find rules that will predict the

occurrence of an item based on the occurrences of other
items in the transaction

Market-Basket transactions
Example of Association Rules
TID Items
{Diaper}  {Beer},
1 Bread, Milk {Milk, Bread}  {Eggs,Coke},
2 Bread, Diaper, Beer, Eggs {Beer, Bread}  {Milk},
3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer Implication means co-occurrence,
5 Bread, Milk, Diaper, Coke not causality!

3/8/2021 Introduction to Data Mining, 2 nd Edition 2

Definition: Frequent Itemset
 Itemset
– A collection of one or more items
 Example: {Milk, Bread, Diaper}
– k-itemset TID Items
 An itemset that contains k items 1 Bread, Milk
 Support count () 2 Bread, Diaper, Beer, Eggs
– Frequency of occurrence of an itemset 3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer
– E.g. ({Milk, Bread,Diaper}) = 2
5 Bread, Milk, Diaper, Coke
 Support
– Fraction of transactions that contain an
itemset
– E.g. s({Milk, Bread, Diaper}) = 2/5
 Frequent Itemset
– An itemset whose support is greater
than or equal to a minsup threshold

3/8/2021 Introduction to Data Mining, 2 nd Edition 3

Definition: Association Rule
 Association Rule
TID Items
– An implication expression of the form
X  Y, where X and Y are itemsets 1 Bread, Milk
2 Bread, Diaper, Beer, Eggs
– Example:
{Milk, Diaper}  {Beer} 3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer
 5 Bread, Milk, Diaper, Coke
Rule Evaluation Metrics
– Support (s)
 Fraction of transactions that contain Example:
both X and Y
{Milk , Diaper}  {Beer}
– Confidence (c)
 Measures how often items in Y  (Milk , Diaper, Beer ) 2
appear in transactions that s  0.4
contain X
|T| 5
 (Milk, Diaper, Beer ) 2
c  0.67
 (Milk , Diaper ) 3
3/8/2021 Introduction to Data Mining, 2 nd Edition 4
3/8/2021 Introduction to Data Mining, 2 nd Edition 5
Mining Association Rules

TID Items Example of Rules:

1 Bread, Milk {Milk,Diaper}  {Beer} (s=0.4, c=0.67)
2 Bread, Diaper, Beer, Eggs {Milk,Beer}  {Diaper} (s=0.4, c=1.0)
3 Milk, Diaper, Beer, Coke {Diaper,Beer}  {Milk} (s=0.4, c=0.67)
4 Bread, Milk, Diaper, Beer {Beer}  {Milk,Diaper} (s=0.4, c=0.67)
5 Bread, Milk, Diaper, Coke {Diaper}  {Milk,Beer} (s=0.4, c=0.5)
{Milk}  {Diaper,Beer} (s=0.4, c=0.5)

Observations:
• All the above rules are binary partitions of the same itemset:
{Milk, Diaper, Beer}
• Rules originating from the same itemset have identical support but
can have different confidence
• Thus, we may decouple the support and confidence requirements

3/8/2021 Introduction to Data Mining, 2 nd Edition 6

Mining Association Rules

 Two-step approach:
1. Frequent Itemset Generation
– Generate all itemsets whose support  minsup

2. 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

3/8/2021 Introduction to Data Mining, 2 nd Edition 7

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 8
Frequent Itemset Generation
Strategies
 Reduce the number of candidates (M)
– Complete search: M=2d
– Use pruning techniques to reduce M

 Reduce the number of transactions (N)

– Reduce size of N as the size of itemset increases

 Reduce the number of comparisons (NM)

– Use efficient data structures to store the candidates or
transactions
– No need to match every candidate against every transaction

3/8/2021 Introduction to Data Mining, 2 nd Edition 9

Reducing Number of Candidates

 Apriori principle:
– The Apriori algorithm is Unsupervised Learning does not
require labeled data, which is a significant advantage
given the prevalence of unlabeled data.
– technique discovers frequent itemsets and generates association
rules by exploiting the principle that all subsets of a frequent
itemset must also be frequent.

X , Y : ( X  Y )  s ( X ) s (Y )
 Apriori principle holds due to the following property of the
support measure:
– 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 10
 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 11
 Illustrating Apriori Algorithm

TID Items
Items (1-itemsets)
1 Bread, Milk
Item Count
2 Beer, Bread,
B read, Diaper, Eggs
Bread 4
3 Beer, Coke, Diaper, Milk Coke 2
4 Beer, Bread,
B read, Diaper, Milk Milk 4
Beer 3
5 Bread, Coke, Diaper, Milk
Diaper 4
Eggs 1

Minimum Support = 3
Item Count
Itemset Bread 4
{Bread,Milk} Coke 2
{Bread, Beer } Milk 4
{Bread,Diaper} Beer 3
{Beer, Milk} Diaper 4
{Diaper, Milk} Eggs 1
{Beer,Diaper}

3/8/2021 Introduction to Data Mining, 2 nd Edition 12

 Illustrating Apriori Principle TID Items
1 Bread, Milk
2 Beer, B read, Diaper, Eggs
3 Beer, Coke, Diaper, Milk
Item Count Items (1-itemsets) 4 Beer, B read, Diaper, Milk
5 Bread, Coke, Diaper, Milk
Bread 4
Coke 2
Milk 4 Itemset Count Pairs (2-itemsets)
Beer 3 {Bread,Milk} 3
Diaper 4 {Bread,Beer} 2 (No need to generate
Eggs 1
{Bread,Diaper} 3 candidates involving Coke
{Milk,Beer} 2 or Eggs)
{Milk,Diaper} 3
{Beer,Diaper} 3
Minimum Support = 3
Triplets (3-itemsets)
Itemset
{ Beer, Diaper, Milk}
{ Beer,Bread,Diaper}
{Bread,Diaper,Milk}
{ Beer, Bread, Milk}

3/8/2021 Introduction to Data Mining, 2 nd Edition 13

 Illustrating Apriori Principle TID
1
Items
Bread, Milk
2 Beer, B read, Diaper, Eggs
3 Beer, Coke, Diaper, Milk
4 Beer, B read, Diaper, Milk
Item Count Items (1-itemsets) 5 Bread, Coke, Diaper, Milk
Bread 4
Coke 2
Milk 4 Itemset Count Pairs (2-itemsets)
Beer 3 {Bread,Milk} 3
Diaper 4 {Bread,Beer} 2 (No need to generate
Eggs 1
{Bread,Diaper} 3 candidates involving Coke
{Milk,Beer} 2 or Eggs)
{Milk,Diaper} 3
{Beer,Diaper} 3
Minimum Support = 3
Triplets (3-itemsets)

Itemset Count
{ Beer, Diaper, Milk} 2
{ Beer,Bread, Diaper} 2
{Bread, Diaper, Milk} 2
{Beer, Bread, Milk} 1

3/8/2021 Introduction to Data Mining, 2 nd Edition 14

 Illustrating Apriori Principle TID
1
Items
Bread, Milk
2 Beer, Bread, Diaper, Eggs
3 Beer, Coke, Diaper, Milk
4 Beer, Bread, Diaper, Milk
Item Count Items (1-itemsets) 5 Bread, Coke, Diaper, Milk
Bread 4
Coke 2
Milk 4 Itemset Count Pairs (2-itemsets)
Beer 3 {Bread,Milk} 3
Diaper 4 {Bread,Beer} 2 (No need to generate
Eggs 1
{Bread,Diaper} 3 candidates involving Coke
{Milk,Beer} 2 or Eggs)
{Milk,Diaper} 3
{Beer,Diaper} 3
Minimum Support = 3
Triplets (3-itemsets)

Itemset Count
{ Beer, Diaper, Milk} 2
{ Beer,Bread, Diaper} 2
{Bread, Diaper, Milk} 2
{Beer, Bread, Milk} 1

3/8/2021 Introduction to Data Mining, 2 nd Edition 15

Factors Affecting Complexity of
Apriori

 Choice of minimum support threshold

 Dimensionality (number of items) of the data set

 Size of database

 Average transaction width

–

3/8/2021 Introduction to Data Mining, 2 nd Edition 16

Advantages and Disadvantages of A

Advantages Disadvantages
• Computational Complexity: Can be
• Simplicity and Ease of
extremely expensive, especially
Implementation: Highly intuitive
with large datasets, extensive
and accessible, even for those new
itemsets, or low support thresholds.
to data mining.

• Efficient Pruning: Reduces • Multiple Dataset Scans: Time-

computational load by narrowing consuming due to requiring multiple
down plausible items, accelerating full scans of the dataset to generate
the process. frequent itemsets.
• Unsupervised Learning: Does not • Numerous Rules: Can generate a
require labeled data, which is a vast number of association rules,
significant advantage given the making it challenging to review and
prevalence of unlabeled data. identify truly relevant ones.

• Widespread Support: Supported by

most major data mining tools and
widely used for association rule
mining.
• Scalability: Can handle large
datasets and run on distributed
systems, making it suitable for
large-scale operations.
3/8/2021 Introduction to Data Mining, 2 nd Edition 17
Applications of the Apriori Algorithm

The Apriori algorithm's ability to uncover hidden patterns has led to its application across various domains.

E-Commerce & Retail Web Usage

Analyzes customer purchase patterns for product Uncovers user navigation patterns to design more
bundling, inventory optimization, and cross- user-friendly websites and improve user
selling strategies. experience.

Medical Recommendation Systems

Identifies drug combinations, patient factors for Powers content recommendations on platforms
adverse reactions, and symptom co-occurrence like Netflix, YouTube, and Spotify, and auto-
for disease diagnosis. completion features.

Network Traffic Analysis Forestry

Establishes normal web traffic patterns to detect Analyzes forest fire data to estimate frequency
unusual behavior or cyber threats. and intensity, aiding in prevention and
management.

3/8/2021 Introduction to Data Mining, 2 nd Edition 18

 Thank You

3/8/2021 Introduction to Data Mining, 2 nd Edition 19