Association Rules: Basic Concepts �and Algorithms

Dr. Jamolbek Mattiev

​

Urgench State University, Uzbekistan

Chennai, 2025

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

{Diaper} → {Beer},�{Milk, Bread} → {Eggs,Coke},�{Beer, Bread} → {Milk},

Implication means co-occurrence, not causality!

Definition: Frequent Itemset

• Itemset
• A collection of one or more items
• Example: {Milk, Bread, Diaper}
• k-itemset
• An itemset that contains k items
• Support count (σ)
• Frequency of occurrence of an itemset
• E.g. σ({Milk, Bread,Diaper}) = 2
• 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

Definition: Association Rule

• Association Rule
• An implication expression of the form X → Y, where X and Y are itemsets
• Example:� {Milk, Diaper} → {Beer}

​

• Rule Evaluation Metrics
• Support (s)
• Fraction of transactions that contain both X and Y
• Confidence (c)
• Measures how often items in Y �appear in transactions that�contain X

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!

Mining Association Rules

Example of Rules:�

{Milk,Diaper} → {Beer} (s=0.4, c=0.67)�{Milk,Beer} → {Diaper} (s=0.4, c=1.0)

{Diaper,Beer} → {Milk} (s=0.4, c=0.67)

{Beer} → {Milk,Diaper} (s=0.4, c=0.67) �{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

Mining Association Rules

• Two-step approach:
1. 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

​

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:

​

​

• Support of an itemset never exceeds the support of its subsets
• This is known as the anti-monotone property of support

Illustrating Apriori Principle

Illustrating Apriori Principle

Items (1-itemsets)

Pairs (2-itemsets)

​

(No need to generate�candidates involving Coke�or Eggs)

Triplets (3-itemsets)

Minimum Support = 3

If every subset is considered,

⁶C₁ + ⁶C₂ + ⁶C₃ = 41

With support-based pruning,

6 + 6 + 1 = 13

Apriori Algorithm

• Method:

​

• Let k=1
• Generate frequent itemsets of length 1
• Repeat until no new frequent itemsets are identified
• Generate length (k+1) candidate itemsets from length k frequent itemsets
• Prune candidate itemsets containing subsets of length k that are infrequent
• Count the support of each candidate by scanning the DB
• Eliminate candidates that are infrequent, leaving only those that are frequent

FP-growth Algorithm

• Use a compressed representation of the database using an FP-tree

​

• Once an FP-tree has been constructed, it uses a recursive divide-and-conquer approach to mine the frequent itemsets

FP-tree construction

null

A:1

B:1

null

A:1

B:1

B:1

C:1

D:1

After reading TID=1:

After reading TID=2:

FP-Tree Construction

null

A:7

B:5

B:3

C:3

D:1

C:1

D:1

C:3

D:1

D:1

E:1

E:1

Pointers are used to assist frequent itemset generation

D:1

E:1

Transaction Database

Header table

FP-growth

null

A:7

B:5

B:1

C:1

D:1

C:1

D:1

C:3

D:1

D:1

Conditional Pattern base for D: � P = {(A:1,B:1,C:1),� (A:1,B:1), � (A:1,C:1),� (A:1), � (B:1,C:1)}

Recursively apply FP-growth on P

Frequent Itemsets found (with sup > 1):� AD, BD, CD, ACD, BCD

D:1

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:

ABC →D, ABD →C, ACD →B, BCD →A, �A →BCD, B →ACD, C →ABD, D →ABC�AB →CD, AC → BD, AD → BC, BC →AD, �BD →AC, CD →AB, �

• If |L| = k, then there are 2^k – 2 candidate association rules (ignoring L → ∅ and ∅ → L)

Effect of Support Distribution

• How to set the appropriate minsup threshold?
• If minsup is set too high, we could miss itemsets involving interesting rare items (e.g., expensive products)

​

• If minsup is set too low, it is computationally expensive and the number of itemsets is very large

​

• Using a single minimum support threshold may not be effective

Multiple Minimum Support (Liu 1999)

• Order the items according to their minimum support (in ascending order)
• e.g.: MS(Milk)=5%, MS(Coke) = 3%,� MS(Broccoli)=0.1%, MS(Salmon)=0.5%
• Ordering: Broccoli, Salmon, Coke, Milk

​

• Need to modify Apriori such that:
• L₁ : set of frequent items
• F₁ : set of items whose support is ≥ MS(1)� where MS(1) is min_i( MS(i) )
• C₂ : candidate itemsets of size 2 is generated from F_1� instead of L₁

​

Multiple Minimum Support (Liu 1999)

• Modifications to Apriori:
• In traditional Apriori,
• A candidate (k+1)-itemset is generated by merging two� frequent itemsets of size k
• The candidate is pruned if it contains any infrequent subsets� of size k
• Pruning step has to be modified:
• Prune only if subset contains the first item
• e.g.: Candidate={Broccoli, Coke, Milk} (ordered according to� minimum support)
• {Broccoli, Coke} and {Broccoli, Milk} are frequent but � {Coke, Milk} is infrequent
• Candidate is not pruned because {Coke,Milk} does not contain� the first item, i.e., Broccoli.