Data Mining Concepts, Association Rules & Apriori Algorithm
Idea in plain words
Data Mining: Knowledge Discovery in Databases (KDD) process discovering valid, novel, potentially useful, and understandable patterns in massive data.
Exam tip
High-yield exam topic (Very High).
Explanation
Market basket analysis discovers customer purchasing patterns to optimize shelf arrangements, cross-selling campaigns, and catalogue bundling. The naive approach of evaluating every possible item combination exhibits exponential complexity O(2^d). The Apriori algorithm prunes the search space by iteratively generating candidate k-itemsets solely from frequent (k-1)-itemsets. If any itemset {X, Y} is infrequent, any larger superset containing it (e.g., {X, Y, Z}) is immediately pruned without database scanning.
Key points
- Association Rule Mining (Market Basket Analysis): Identifies relationships between items bought together: {Antecedent} -> {Consequent}.
- Support: Fraction of total transactions containing both itemsets: Support(A -> B) = P(A union B).
- Confidence: Conditional probability that item B is purchased given that item A is purchased: Confidence(A -> B) = Support(A union B) / Support(A).
- Lift: Ratio of observed support to expected support if A and B were independent: Lift(A -> B) = Confidence(A -> B) / Support(B); Lift > 1 indicates positive association.
- Apriori Algorithm: Employs the Apriori property (all non-empty subsets of a frequent itemset must also be frequent) to prune candidate itemsets.
Example
Example
The classic retail discovery where diaper purchases on Friday evenings strongly correlated with beer purchases, prompting stores to place them adjacent to each other.
Code examples
/*
Apriori Step-by-Step Calculation:
Database D of 5 transactions:
T1: {Bread, Milk}
T2: {Bread, Diaper, Beer, Eggs}
T3: {Milk, Diaper, Beer, Cola}
T4: {Bread, Milk, Diaper, Beer}
T5: {Bread, Milk, Diaper, Cola}
Minimum Support = 60% (3/5), Minimum Confidence = 80%
1. Candidate 1-itemsets (C1):
{Bread}: 4/5, {Milk}: 4/5, {Diaper}: 4/5, {Beer}: 3/5, {Cola}: 2/5, {Eggs}: 1/5
Prune Cola and Eggs -> Frequent L1 = {Bread, Milk, Diaper, Beer}
2. Candidate 2-itemsets (C2):
{Bread, Diaper}: 3/5, {Bread, Beer}: 2/5 (pruned), {Milk, Diaper}: 3/5, {Diaper, Beer}: 3/5
Evaluate Association Rule: {Diaper} -> {Beer}
Support = 3/5 = 60%
Confidence = Support({Diaper, Beer}) / Support({Diaper}) = (3/5) / (4/5) = 75% (< 80%, pruned!)
*/
Exam questions
- [10 Marks] State the Apriori property. Given a transaction database, generate frequent itemsets and strong association rules with detailed calculation steps.
- [6 Marks] Define Support, Confidence, and Lift in association rule mining. Explain why Lift > 1 is critical for validating genuine commercial associations.