Formal Statement of the Association Rule Finding Problem
An association rule is an implication of the form:
X→Y
Where:
X and Y are itemsets (subsets of a set of items, I).
X, Y ⊆ I, where I is the set of all items in the dataset.
X and Y are disjoint itemsets, meaning X ∩ Y = ∅.
Objective
The goal of association rule mining is to find all such rules that satisfy two user-defined
thresholds:
1. Support (supp):
The fraction of transactions in the dataset that contain X ∪ Y.
supp(X→Y) = Count(X ∪ Y) / Total Transactions.
Measures how frequently X and Y occur together in the dataset.
2. Confidence (conf):
The probability of Y occurring in transactions that already contain X.
conf(X→Y) = Count(X ∪ Y) / Count(X).
Measures the strength of the implication X → Y.
Problem Statement
Given:
- A dataset D consisting of a set of transactions, where each transaction T is a subset of I.
- Two thresholds: minimum support (min_supp) and minimum confidence (min_conf).
Find:
All association rules X → Y that satisfy:
1. supp(X ∪ Y) ≥ min_supp.
2. conf(X→Y) ≥ min_conf.
Examples
Example 1: Grocery Store Transactions
Dataset:
Transaction ID Items Purchased
T1 {Bread, Milk, Eggs}
T2 {Bread, Diaper, Milk, Beer}
T3 {Milk, Diaper, Beer, Eggs}
T4 {Bread, Milk, Diaper, Beer}
T5 {Bread, Milk, Diaper, Eggs}
Rule: {Milk} → {Diaper}
Support:
Count(Milk ∪ Diaper) = 3 (appears in T2, T3, T4, T5).
Total Transactions = 5.
supp({Milk}→{Diaper}) = 3/5 = 0.6.
Confidence:
Count(Milk) = 4 (appears in T1, T2, T3, T4, T5).
conf({Milk}→{Diaper}) = 3/4 = 0.75.
If min_supp = 0.5 and min_conf = 0.7, this rule is valid because both support and confidence
meet the thresholds.
Example 2: Online Store Purchases
Dataset:
Transaction ID Items Purchased
T1 {Laptop, Mouse, Keyboard}
T2 {Laptop, Mouse, Monitor}
T3 {Mouse, Monitor, Keyboard}
T4 {Laptop, Mouse, Keyboard, Monitor}
Rule: {Laptop, Mouse} → {Monitor}
Support:
Count(Laptop ∪ Mouse ∪ Monitor) = 2 (appears in T2, T4).
Total Transactions = 4.
supp({Laptop, Mouse}→{Monitor}) = 2/4 = 0.5.
Confidence:
Count(Laptop ∪ Mouse) = 3 (appears in T1, T2, T4).
conf({Laptop, Mouse}→{Monitor}) = 2/3 = 0.67.
If min_supp = 0.4 and min_conf = 0.6, this rule is valid because both support and confidence
meet the thresholds.
Example 3: Movie Recommendations
Dataset:
Transaction ID Movies Watched
T1 {Inception, Interstellar, Dunkirk}
T2 {Inception, The Dark Knight, Dunkirk}
T3 {Interstellar, The Dark Knight}
T4 {Inception, Dunkirk}
Rule: {Inception} → {Dunkirk}
Support:
Count(Inception ∪ Dunkirk) = 3 (appears in T1, T2, T4).
Total Transactions = 4.
supp({Inception}→{Dunkirk}) = 3/4 = 0.75.
Confidence:
Count(Inception) = 3 (appears in T1, T2, T4).
conf({Inception}→{Dunkirk}) = 3/3 = 1.0.
If min_supp = 0.5 and min_conf = 0.8, this rule is valid because both support and confidence
meet the thresholds.