Association Rule Mining & Frequent Pattern Mining: Algorithms, Trees & Applications

Core Concepts: Definitions and Motivation

1. Frequent Itemsets and Association Rules

• Frequent Itemset: A set of items that appear together in transactions with frequency ≥ a predefined minimum support threshold (e.g., 30% of transactions).
• Association Rule: An implication of the form X ⇒ Y, where:
  • Support(X ⇒ Y): Fraction of transactions containing both X and Y.
  • Confidence(X ⇒ Y): Fraction of transactions with X that also contain Y (i.e., P(Y|X)).
  • Lift(X ⇒ Y): Measures how much more often X and Y occur together than expected by chance. $$\text{Lift}(X\Rightarrow Y)=\frac{\text{Support}(X\cup Y)}{\text{Support}(X)\times \text{Support}(Y)}$$
  • A rule is strong if both confidence and lift exceed thresholds.

---

2. Why Frequent Pattern Mining Matters

In the Real World

• eSewa (Nepal): Uses association rules to recommend mobile top-ups + data bundles to users who frequently buy both. If 60% of users who buy a Rs. 500 top-up also buy 1GB data, eSewa pushes a bundle discount.
• Daraz (Nepal): Detects cross-selling patterns like "customers who buy a smartphone also buy a screen guard (80% confidence)" to auto-suggest add-ons at checkout.
• Khalti (Nepal): Fraud detection flags unusual transaction sequences (e.g., "user transfers Rs. 10,000 to an unknown merchant within 5 minutes of logging in") by mining frequent but suspicious patterns.

---

3. Algorithms: Apriori vs. FP-Growth

Apriori Algorithm

How it works:

1. Generate frequent 1-itemsets (items appearing ≥ min_support times).
2. Prune infrequent itemsets: If an itemset is infrequent, all its supersets are also pruned (Apriori principle).
3. Iteratively grow larger itemsets (2-items, 3-items, etc.) until no more frequent itemsets exist.
4. Generate rules: For each frequent itemset X, generate all non-empty subsets Y and compute confidence.

Worked Example: Apriori on Daraz Orders Dataset (5 transactions, min_support = 2):

T1: {Phone, Charger, Case}
T2: {Phone, Charger}
T3: {Laptop, Mouse}
T4: {Phone, Case, Mouse}
T5: {Phone, Charger, Mouse}

Step 1: Find frequent 1-itemsets (support ≥ 2):

• Phone: 4, Charger: 3, Case: 2, Mouse: 3, Laptop: 1 → Frequent: {Phone}, {Charger}, {Case}, {Mouse}

Step 2: Generate candidate 2-itemsets and prune:

• {Phone, Charger}: 3, {Phone, Case}: 2, {Phone, Mouse}: 3, {Charger, Case}: 1 (pruned), {Charger, Mouse}: 2, {Case, Mouse}: 1 (pruned) → Frequent: {Phone, Charger}, {Phone, Case}, {Phone, Mouse}, {Charger, Mouse}

Step 3: Generate rules (min_confidence = 60%):

• Rule: {Phone} ⇒ {Charger} Support = 3/5 = 60%, Confidence = 3/4 = 75%, Lift = (3/5)/(4/5×3/5) = 1.25 → Strong rule.
• Rule: {Case} ⇒ {Phone} Confidence = 2/2 = 100%, Lift = (2/5)/(2/5×4/5) = 1.25 → Strong rule.

Mermaid Diagram: Apriori Pruning Process

FP-Growth Algorithm (Frequent Pattern Growth)

Advantages over Apriori:

• Avoids repeated database scans (Apriori scans the dataset in every pass).
• Uses a compressed FP-tree to store frequent itemsets efficiently.

How FP-Trees Work:

1. Construct FP-tree:
   • Sort items by frequency (descending).
   • Insert transactions into the tree, updating counts.
2. Mine conditional patterns:
   • For each frequent item, generate a conditional FP-tree and recurse.

Worked Example: FP-Growth on eSewa Transactions Dataset (min_support = 2):

T1: {Topup, Data}
T2: {Topup, Data, Recharge}
T3: {Data, Recharge}
T4: {Topup, Recharge}
T5: {Topup, Data}

Step 1: Sort items by frequency (Topup:3, Data:3, Recharge:3). Step 2: Build FP-tree:

        null
       /   \
   Topup(3) Data(3)
     /      \
Recharge(2) Recharge(1)

Step 3: Mine patterns:

• Frequent 1-itemsets: {Topup}, {Data}, {Recharge}.
• Frequent 2-itemsets: {Topup, Data}, {Topup, Recharge}, {Data, Recharge}.
• Rule: {Topup} ⇒ {Data} (Confidence = 2/3 ≈ 66.7%).

Mermaid Diagram: FP-Tree Construction

---

4. Limitations of Apriori and FP-Growth

Key Drawbacks of Apriori:

1. Candidate Generation Overhead: Generates and tests many unnecessary candidate itemsets.
2. Multiple Database Scans: Requires scanning the dataset in every iteration.
3. Downward Closure Property: Must check all subsets, even if some are clearly infrequent.

Example of Inefficiency: For a dataset with 100 items, Apriori may generate millions of candidate 3-itemsets before pruning, while FP-Growth compresses the same data into a single tree.

---

5. Practical Applications Beyond E-Commerce

A. Fraud Detection (Ncell/Khalti)

• Pattern: "Users who top-up > Rs. 5000 in a single transaction and then immediately transfer to an unknown wallet."
• Rule: {High_Amount_Topup} ⇒ {Suspicious_Transfer} (Confidence = 90%).
• Action: Flag for manual review.

B. Healthcare (Nepal’s Hospitals)

• Pattern: "Patients with diabetes who also have high blood pressure."
• Rule: {Diabetes} ⇒ {Hypertension} (Lift = 3.2).
• Action: Targeted screening programs.

C. Traffic Prediction (Kathmandu Traffic Management)

• Pattern: "Traffic jams at Thapathali on Fridays between 5–7 PM."
• Rule: {Friday} ⇒ {Thapathali_Jam} (Confidence = 85%).
• Action: Dynamic route suggestions via apps like Pathao.

---

6. Advanced: Constraint-Based Mining

Real-world data often requires constraints to focus on meaningful patterns:

• Temporal Constraints: "Find rules where items are bought within 1 hour."
• Quantitative Constraints: "Only consider rules where the average transaction value > Rs. 2000."
• Taxonomic Constraints: "Only consider electronics items (e.g., exclude groceries)."

Example: For Daraz, a constraint might be: "Find rules where the lift > 1.5 AND the average order value > Rs. 5000."

---

Exam Tip

1. Memorize Key Formulas:

   • Support, confidence, and lift calculations are must-know. Always show all steps in exams.
   • Example: For a rule {A, B} ⇒ {C} with support(A∪B∪C)=4, support(A∪B)=6, support(C)=5: $$\text{Confidence}=\frac{4}{6}\approx 66.7\%,\text{Lift}=\frac{4/10}{(6/10\times 5/10)}=1.33$$

2. Algorithm Steps:

   • For Apriori: Always list the pruning step explicitly. Examiners check if you skip candidates like {Charger, Case} in the example above.
   • For FP-Growth: Draw the FP-tree (even a rough sketch) to show you understand the compression step.

3. Real-World Tie-Ins:

   • Questions often ask for applications in Nepalese contexts (e.g., "How would you use association rules in eSewa?"). Link rules to recommendations, fraud, or cross-selling.

4. Common Pitfalls:

   • Ignoring min_support: If min_support is 2 in a 5-transaction dataset, {Laptop} is not frequent (support=1).
   • Confidence ≠ Causation: High confidence doesn’t mean X causes Y (e.g., {Diapers} ⇒ {Beer} is a famous spurious correlation).

5. Diagram Expectations:

   • Apriori: Show the pruning table (candidates vs. actual support).
   • FP-Growth: Sketch the tree and highlight conditional patterns.
   • Association Rules: Draw a simple Venn diagram for support/confidence (even if not in the syllabus, it helps visualize).

---

Final Note: Association rule mining is not just about numbers—it’s about uncovering hidden stories in data. Whether it’s Daraz predicting what you’ll buy next or Khalti stopping fraud, these techniques turn raw transactions into actionable insights. Practice with real datasets (even small ones) to build intuition!