Association Rule Mining: Algorithms, Metrics & Applications

What is Association Rule Mining?

Association Rule Mining (ARM) is a data mining technique that identifies frequent patterns, correlations, or associations among items in large datasets. These rules help businesses understand customer behavior, optimize product placements, and improve sales strategies.

Key Definitions

• Itemset: A collection of one or more items (e.g., {Milk, Bread}).
• Transaction: A single record of items purchased together (e.g., a customer’s shopping cart).
• Support: The frequency of an itemset in the dataset. $$\text{Support}(X)=\frac{\text{Number of transactions containing }X}{\text{Total number of transactions}}$$
• Confidence: The likelihood that if $X$ occurs, $Y$ will also occur. $$\text{Confidence}(X\to Y)=\frac{\text{Support}(X\cup Y)}{\text{Support}(X)}$$
• Lift: Measures how much more often $X$ and $Y$ occur together than expected by chance. $$\text{Lift}(X\to Y)=\frac{\text{Support}(X\cup Y)}{\text{Support}(X)\times \text{Support}(Y)}$$

In the Real World

1. eSewa & Khalti (Nepal):

   • These apps use association rules to recommend payment bundles (e.g., "Users who pay electricity bills also recharge mobile data").
   • Example: If a user frequently pays for electricity + internet, the app suggests a "Smart Bundle" with a discount.

2. Daraz (Nepal) & Amazon (Global):

   • "Customers who bought this also bought" is built using association rules.
   • Example: If 80% of users buying a phone case also buy screen protectors, Daraz displays a "Complete Your Accessory" banner.

3. NTC & Ncell (Nepal):

   • Telecom companies analyze subscription patterns (e.g., "Users with 4G plans also buy hotspot devices").
   • Example: Ncell sends promotions like "Buy a 4G plan + get a free hotspot" based on association rules.

Step-by-Step Worked Example: Market Basket Analysis

Scenario: A small grocery store in Kathmandu wants to find product associations using sales data from the last month.

Dataset (5 Transactions)

Step 1: Find Frequent Itemsets (Support ≥ 2/5 = 40%)

• Single Items:
  • Milk: 4/5 = 80% ✅
  • Bread: 4/5 = 80% ✅
  • Diapers: 5/5 = 100% ✅
  • Beer: 3/5 = 60% ✅
  • Eggs: 1/5 = 20% ❌
  • Coke: 2/5 = 40% ✅

• Two-Itemsets:
  • {Milk, Bread}: 3/5 = 60% ✅
  • {Milk, Diapers}: 4/5 = 80% ✅
  • {Bread, Diapers}: 4/5 = 80% ✅
  • {Diapers, Beer}: 3/5 = 60% ✅
  • {Milk, Beer}: 2/5 = 40% ✅

Step 2: Generate Association Rules (Confidence ≥ 70%)

Interpretation:

• "Beer → Diapers" has the highest lift (1.67), meaning beer buyers are 67% more likely to buy diapers than random chance.
• The store could place diapers near the beer section to increase sales.

Association Rule Mining Algorithms

Two widely used algorithms for ARM are Apriori and FP-Growth.

1. Apriori Algorithm

How it works:

• Uses a bottom-up approach to find frequent itemsets.
• Pruning: If an itemset is infrequent, all its supersets are also infrequent.
• Steps:
  1. Find all frequent 1-itemsets.
  2. Generate candidate 2-itemsets and prune infrequent ones.
  3. Repeat until no more frequent itemsets are found.

flowchart TD
    A["Start with frequent 1-itemsets"] --> B["Generate candidate k-itemsets"]
    B --> C["Prune infrequent candidates"]
    C --> D["Check support"]
    D -->|"Frequent"| E["Generate (k+1)-itemsets"]
    D -->|"Infrequent"| F["Stop"]
    E --> B

Advantages: ✔ Simple to understand. ✔ Works well for small to medium datasets.

Disadvantages: ✖ Inefficient for large datasets (scans database multiple times). ✖ Candidate generation overhead.

2. FP-Growth (Frequent Pattern Growth)

How it works:

• Avoids candidate generation by compressing transactions into a compact tree structure (FP-Tree).
• Steps:
  1. Scan the database to find frequent 1-itemsets.
  2. Construct an FP-Tree (Frequent Pattern Tree).
  3. Mine the FP-Tree to find frequent itemsets.

flowchart LR
    A["Scan Database"] --> B["Find Frequent 1-Itemsets"]
    B --> C["Construct FP-Tree"]
    C --> D["Mine FP-Tree for Frequent Patterns"]
    D --> E["Generate Association Rules"]

Advantages: ✔ Faster than Apriori (single database scan + tree traversal). ✔ Memory-efficient (no candidate generation).

Disadvantages: ✖ Complex implementation. ✖ Not suitable for very sparse datasets.

Comparison: Apriori vs. FP-Growth

Real-World Application: Daraz’s "Frequently Bought Together"

Scenario: Daraz wants to recommend products based on past purchases.

Step 1: Collect Transaction Data

• Example transactions from Daraz users:
  • T1: Laptop, Mouse, Keyboard
  • T2: Laptop, Monitor, Mouse
  • T3: Mouse, Keyboard, Headphones
  • T4: Laptop, Monitor, Keyboard

Step 2: Apply FP-Growth to Find Frequent Itemsets

• Frequent 2-itemsets (Support ≥ 2/4 = 50%):
  • {Laptop, Mouse} (3/4)
  • {Mouse, Keyboard} (3/4)
  • {Laptop, Monitor} (2/4)

Step 3: Generate Rules (Confidence ≥ 60%)

Daraz’s Action:

• Display "Frequently Bought Together" for:
  • Laptop + Mouse (High lift = 1.33).
  • Mouse + Keyboard (High lift = 1.33).
• Result: 15% increase in cross-selling revenue.

Challenges in Association Rule Mining

1. Scalability Issues:

   • Large datasets (e.g., Amazon’s transaction logs) make Apriori slow.
   • Solution: Use FP-Growth, parallel processing, or sampling.

2. Redundant Rules:

   • Many rules may be trivial (e.g., {Bread} → {Milk} and {Milk} → {Bread}).
   • Solution: Use constraint-based mining or rule pruning.

3. Interpretability:

   • Too many rules make it hard for businesses to act.
   • Solution: Focus on high-lift rules or use visualization tools.

4. Dynamic Data:

   • Customer preferences change over time.
   • Solution: Incremental mining (update rules without reprocessing full data).

Exam Tip

What to Expect in TU/PU Exams:

1. Definitions & Formulas:

   • Be ready to derive support, confidence, and lift from scratch.
   • Example question: "Given a dataset, calculate the confidence of the rule {Bread} → {Milk} if Support(Bread ∪ Milk) = 0.3 and Support(Bread) = 0.5."

2. Algorithm Steps:

   • Apriori: Explain candidate generation and pruning.
   • FP-Growth: Draw an FP-Tree from a given dataset.
   • Example question: "Construct an FP-Tree for the following transactions and find frequent itemsets with min_support = 2."

3. Worked Examples:

   • Always show step-by-step calculations for support, confidence, and lift.
   • Example question: "From the given market basket data, generate 3 association rules with confidence ≥ 70%."

4. Real-World Applications:

   • Relate ARM to e-commerce, telecom, or banking.
   • Example question: "How can Ncell use association rule mining to improve customer retention?"

5. Comparison Questions:

   • Compare Apriori vs. FP-Growth in terms of efficiency and use cases.

Final Checklist for Full Marks:

✅ Define support, confidence, and lift with formulas. ✅ Draw an FP-Tree for a given dataset. ✅ Calculate association rules from a small dataset. ✅ Explain how ARM is used in eSewa, Daraz, or NTC. ✅ Compare Apriori and FP-Growth in a table. ✅ Discuss challenges like scalability and redundancy.