Association Rule Mining: Algorithms, Metrics & Applications

TAKEAWAYS:

• Association rules uncover hidden relationships like "customers who buy X also buy Y" using support, confidence, and lift metrics.
• The Apriori algorithm prunes candidate itemsets iteratively, while FP-Growth builds a compressed tree structure for efficiency.
• Market basket analysis (e.g., Daraz, Walmart) and cross-selling (e.g., Amazon "Frequently Bought Together") rely on association rules.
• Lift > 1 indicates a meaningful association beyond random chance, while confidence measures rule reliability.
• Real-world examples include bank loan approvals (checking co-occurring customer attributes) and disease diagnosis (finding symptom patterns).
• Exam focus: Be ready to calculate metrics, compare Apriori vs. FP-Growth, and apply rules to case studies (e.g., eSewa transaction patterns).

1. What Are Association Rules?

Association rule mining (ARM) discovers frequent patterns in transactional datasets, answering: "What items are frequently bought together?" "Which customer attributes co-occur in loan approvals?"

Key Definitions

• Itemset: A set of items (e.g., {Diapers, Beer}).
• Transaction: A single record (e.g., a customer’s shopping cart).
• Support: How often an itemset appears in transactions. $$\text{Support}(X)=\frac{\text{Number of transactions containing }X}{\text{Total transactions}}$$
• Confidence: How often the consequent follows the antecedent. $$\text{Confidence}(X\to Y)=\frac{\text{Support}(X\cup Y)}{\text{Support}(X)}$$
• Lift: Measures how much more likely $Y$ is when $X$ occurs (vs. random chance). $$\text{Lift}(X\to Y)=\frac{\text{Support}(X\cup Y)}{\text{Support}(X)\times \text{Support}(Y)}$$
  • Lift > 1: Positive association.
  • Lift = 1: Independent.
  • Lift < 1: Negative association.

Example: Daraz Market Basket Analysis

Suppose Daraz tracks 1000 transactions. Calculate metrics for the rule: "Customers who buy Laptops also buy Mouse" ({Laptop} → {Mouse}).

Step-by-Step Calculation:

1. Support({Laptop, Mouse}):
   • Transactions with both: T1, T2 → 2/1000 = 0.002 (0.2%).
2. Support({Laptop}):
   • Transactions with Laptop: T1, T2 → 2/1000 = 0.002 (0.2%).
3. Support({Mouse}):
   • Transactions with Mouse: T1, T2, T3 → 3/1000 = 0.003 (0.3%).
4. Confidence: $$\frac{0.002}{0.002}=1.0(100\%)$$
   • Interpretation: If a customer buys a Laptop, they always buy a Mouse in this dataset.
5. Lift: $$\frac{0.002}{0.002\times 0.003}=\frac{0.002}{0.000006}\approx 333.3$$
   • Interpretation: Customers buying Laptops are 333x more likely to buy Mice than random chance.

2. Algorithms for Association Rule Mining

Two dominant algorithms: Apriori and FP-Growth.

A. Apriori Algorithm

How it works:

1. Generate frequent itemsets (support ≥ threshold) iteratively.
2. Prune itemsets that cannot be frequent (if any subset is infrequent, the superset is also infrequent).
3. Generate rules from frequent itemsets using confidence and lift.

Example Trace: Finding Frequent Itemsets Dataset (5 transactions):

Step 1: Find Frequent 1-Itemsets (Support ≥ 2)

• Bread: 3/5 = 0.6
• Milk: 3/5 = 0.6
• Diaper: 4/5 = 0.8
• Beer: 1/5 = 0.2 → Pruned

Step 2: Find Frequent 2-Itemsets

• Check subsets first: {Bread, Milk} (both frequent).
  • Support: T1, T4 → 2/5 = 0.4
• {Bread, Diaper}: T1, T2 → 2/5 = 0.4
• {Milk, Diaper}: T1, T3 → 2/5 = 0.4
• {Bread, Beer}: Bread not in T5 → Pruned.

Step 3: Generate Rules From {Bread, Diaper} → {Milk}:

• Confidence = Support({Bread, Diaper, Milk}) / Support({Bread, Diaper}) = (1/5)/(2/5) = 0.5 (50%).
• Lift = (1/5) / (3/5 * 4/5) ≈ 0.625 → Weak association.

B. FP-Growth Algorithm

Problem with Apriori: Scans the dataset multiple times (inefficient for large datasets). FP-Growth solves this by building a compressed tree structure (FP-Tree) in one pass.

Example: FP-Tree Construction Same dataset as above, with min_support = 2:

1. First Pass: Count item frequencies → {Diaper:4, Bread:3, Milk:3}.
2. Sort items by frequency → Diaper, Bread, Milk.
3. Build FP-Tree:

   null
   ├── Diaper:2
   │   ├── Bread:1
   │   │   └── Milk:1
   │   └── Milk:1
   └── Bread:1
       └── Milk:1
   

How to Mine Rules from FP-Tree:

1. Conditional Pattern Base: For each item, generate sub-trees.
   • Example: For Diaper, the sub-tree is {Bread:1, Milk:1}.
2. Recursively mine frequent patterns.

Advantage over Apriori:

• No candidate generation (avoids exponential growth).
• Single database scan for tree construction.

3. Real-World Applications

A. E-Commerce: Cross-Selling and Recommendations

• Daraz/Walmart: "Customers who bought this also bought..." uses association rules to suggest products.
  • Example Rule: {Smartphone} → {Screen Protector} (Lift = 5.2).
• Amazon: "Frequently Bought Together" is built using ARM.

B. Banking: Loan Approval Patterns

• Nepal Bank Limited: Analyzes co-occurring customer attributes (e.g., {Age 30-40, Salary > 50k} → {Loan Approval}).
  • Example: If 80% of customers with {Income > 70k, Credit Score > 750} get loans, the bank can automate approvals.

C. Healthcare: Disease Diagnosis

• Kathmandu Medical College: Finds symptom patterns (e.g., {Fever, Cough} → {COVID-19} with Lift = 4.1).
  • Helps doctors identify less obvious correlations.

D. Telecommunications: Churn Prediction

• Ncell: Identifies usage patterns leading to customer churn (e.g., {Low Data Usage, High Calls} → {Churn}).
  • Enables targeted retention offers.

4. Comparison: Apriori vs. FP-Growth

5. Challenges and Limitations

• Curse of Dimensionality: Too many possible itemsets in large datasets.
• Threshold Sensitivity: Choosing min_support and min_confidence is subjective.
• Noise and Redundancy: Rules may be statistically significant but meaningless (e.g., {Bread} → {Milk} is obvious).
• Performance Bottleneck: FP-Growth still struggles with very high-dimensional data (e.g., social media interactions).

6. Worked Example: eSewa Transaction Patterns

Scenario: eSewa wants to find hidden patterns in 5000 transactions to suggest "Frequently Paid Together" services.

Dataset (Sample):

Step 1: Set Thresholds

• min_support = 5% (250 transactions).
• min_confidence = 60%.
• min_lift = 1.2.

Step 2: Find Frequent Itemsets

• {Electricity, Phone Recharge}: 150/5000 = 3% → Pruned (below 5%).
• {Electricity, Internet}: 200/5000 = 4% → Pruned.
• {Phone Recharge, Internet}: 180/5000 = 3.6% → Pruned.
• {Electricity}: 400/5000 = 8% → Frequent.
• {Phone Recharge}: 350/5000 = 7% → Frequent.

Step 3: Generate Rules From {Electricity} → {Phone Recharge}:

• Support = 150/5000 = 3%.
• Confidence = 150/400 = 37.5% → Below threshold (60%).
• Discard.

From {Phone Recharge} → {Internet}:

• Support = 180/5000 = 3.6%.
• Confidence = 180/350 ≈ 51.4% → Below threshold.
• Discard.

Step 4: Adjust Thresholds Lower min_support to 2% (100 transactions):

• {Electricity, Phone Recharge}: 150/5000 = 3% → Now frequent.
• Confidence = 150/400 = 37.5% → Still low.
• Conclusion: No strong rules found. eSewa might need to:
  1. Collect more data.
  2. Use a lower confidence threshold.
  3. Combine with other techniques (e.g., sequential pattern mining).

7. Advanced: Lift vs. Confidence vs. Conviction

Example:

• Rule: {Diaper} → {Beer} (Confidence = 75%, Lift = 2.0).
  • Interpretation: 75% of Diaper buyers also buy Beer, and Beer is twice as likely when Diapers are bought.

In the Real World

1. Daraz/Khalti: Uses association rules to recommend products/services after a purchase. For example, if you buy a laptop charger, Khalti might suggest a power bank (Lift = 3.5).
2. Ncell: Analyzes call patterns to predict churn. A rule like {Low Night Calls, High Roaming} → {Churn in 3 Months} (Confidence = 80%) helps target retention offers.
3. Nepal Stock Exchange (NEPSE): Mines investor behavior. A rule like {Buys Banking Stocks} → {Also Buys Insurance} (Lift = 1.8) guides portfolio recommendations.

Exam Tip

1. Memorize Formulas:
   • Support, Confidence, and Lift must be calculated correctly. Practice with small datasets (5–10 transactions).
2. Algorithm Comparison:
   • Apriori: Good for small datasets; FP-Growth: Better for large datasets (e.g., eSewa transactions).
3. Threshold Sensitivity:
   • Lowering min_support increases rules but may include noise. Higher min_confidence reduces false positives.
4. Real-World Scenarios:
   • Expect questions on market basket analysis (Daraz), banking (loan approvals), or telecom (churn).
5. Pitfalls:
   • Avoid rules with low lift (e.g., {Bread} → {Milk} is obvious).
   • Watch for redundant rules (e.g., {A,B} → {C} and {A} → {C} may overlap).

Visual Summary: FP-Tree Construction

graph TD
    A["FP-Tree Root (null)"] --> B["Diaper:2"]
    A --> C["Bread:1"]
    B --> D["Bread:1"]
    B --> E["Milk:1"]
    C --> F["Milk:1"]
    D --> F
    E --> F

Visual: Association Rule Metrics

Visual: Apriori Pruning Example

flowchart TD
    A["Step 1: Find Frequent 1-Itemsets"] --> B["{Bread}, {Milk}, {Diaper}"]
    B --> C["Step 2: Generate 2-Itemset Candidates"]
    C --> D["Check Subsets: {Bread, Milk} (both frequent)"]
    D --> E["Support({Bread, Milk}) = 2/5 = 0.4 ≥ min_support"]
    E --> F["Keep {Bread, Milk}"]
    D --> G["Check {Bread, Beer}: Bread not in T5 → Prune"]
    F --> H["Step 3: Generate Rules"]
    H --> I["{Bread} → {Milk}: Confidence = 0.5"]