Apriori Algorithm
Apriori Algorithm is a basic method used in data analysis to find groups of items
that often appear together in large sets of data. It helps to discover useful patterns
or rules about how items are related which is particularly valuable in market basket
analysis.
How the Apriori Algorithm Works?
1. Identifying Frequent Item-Sets
2. Creating Possible Item Group
3. Removing Infrequent Item Groups
4. Generating Association Rules
Key Metrics of Apriori Algorithm
Support
Support measures how frequently an itemset appears in the dataset.
Confidence
Confidence measures how often items in Y appear in transactions that contain X.
Lift
Lift measures the strength of association between items.
Interpretation
Lift Value Meaning
Lift = 1 No relation
Lift > 1 Positive relation
Lift < 1 Negative relation
Example of Apriori Algorithm
Transaction ID Items Purchased
T1 Bread, Milk
T2 Bread, Diaper, Beer, Eggs
T3 Milk, Diaper, Beer, Cola
T4 Bread, Milk, Diaper, Beer
T5 Bread, Milk, Diaper, Cola
Assume:
Minimum Support = 2
Step 1: Generate 1-Itemsets (C1)
Count the frequency of each item.
Item Count
Bread 4
Milk 4
Diaper 4
Beer 3
Item Count
Eggs 1
Cola 2
Items with support ≥ 2 are frequent
Item Support
Bread 4
Milk 4
Diaper 4
Beer 3
Cola 2
Step 2: Generate Candidate 2-Itemsets (C2)
Possible combinations from L1:
Itemset Count
Bread, Milk 3
Bread, Diaper 3
Bread, Beer 2
Milk, Diaper 3
Milk, Beer 2
Diaper, Beer 3
Milk, Cola 2
Itemset Count
Diaper, Cola 2
All itemsets with support ≥ 2 remain.
Frequent 2-Itemsets (L2)
Itemset Support
Bread, Milk 3
Bread, Diaper 3
Bread, Beer 2
Milk, Diaper 3
Milk, Beer 2
Diaper, Beer 3
Milk, Cola 2
Diaper, Cola 2
Step 3: Generate Candidate 3-Itemsets (C3)
Combine frequent 2-itemsets.
Itemset Count
Bread, Milk, Diaper 2
Milk, Diaper, Beer 2
Bread, Diaper, Beer 2
Itemset Count
Milk, Diaper, Cola 2
Frequent 3-Itemsets (L3)
All itemsets with support ≥ 2 remain.
Step 4: Generate Association Rules
Example rule:
Bread→Milk
Support
Bread & Milk appear = 3
Total transactions = 5
Support=3/5=0.6
Confidence
Bread appears = 4
Confidence=3/4=0.75Confidence = 3/4 = 0.75Confidence=3/4=0.75
Meaning: 75% of customers who buy Bread also buy Milk.
Another Rule Example
Diaper→Beer
Diaper & Beer = 3
Diaper = 4
Confidence=3/4=0.75
Meaning: 75% of customers who buy Diapers also buy Beer.
Final Result of Apriori
Frequent Itemsets Found:
1-Itemsets:
Bread, Milk, Diaper, Beer, Cola
2-Itemsets:
Bread-Milk, Bread-Diaper, Milk-Diaper, Diaper-Beer, etc.
3-Itemsets:
Bread-Milk-Diaper, Milk-Diaper-Beer, etc.
Association rules generated from these itemsets show relationships between
products.
Association Rules
Association Rules are a data mining technique used to discover relationships or
patterns between variables in large datasets.
They are widely used in Market Basket Analysis to identify items that are
frequently purchased together.
Definition
An Association Rule is an implication of the form:
X→YX YX→Y
Where:
X = Antecedent (IF part / Left-hand side)
Y = Consequent (THEN part / Right-hand side)
Important Measures in Association Rules
[Link]
Support indicates how frequently an itemset appears in the dataset.
[Link]
Confidence measures how often Y appears when X appears.
Formula
Lift
Lift measures the strength of the relationship between items.
Example of Transaction Data
Transaction ID Items
T1 Bread, Milk
T2 Bread, Butter
T3 Milk, Butter
T4 Bread, Milk, Butter
T5 Bread, Milk
Possible association rule:
Bread→Milk
Step 1: Possible Association Rule
Bread→Milk
Meaning: Customers who buy Bread are likely to buy Milk.
Step 2: Calculate Support
Bread & Milk appear together in:
T1, T4, T5 → 3 transactions
Support =3 / 5=0.6
Support = 60%
Meaning 60% of transactions contain Bread and Milk together.
Step 3: Calculate Confidence
Bread appears in:
T1, T2, T4, T5 → 4 transactions
Confidence =3 / 4 = 0.75
Confidence = 75%
Meaning 75% of customers who buy Bread also buy Milk.
Step 4: Association Rule Interpretation
Rule:
Bread→Milk
Support = 60%
Confidence = 75%
Interpretation:
Most customers who purchase Bread also purchase Milk.