Association Rule Learning (Apriori, FP-Growth & Eclat)

šŸ“– Introduction

Association Rule Learning is an unsupervised machine learning technique used to discover interesting relationships, patterns, and associations among items in large transactional datasets. Instead of predicting labels, it identifies rules that describe how items frequently occur together.

The three most widely used association rule mining algorithms are Apriori, FP-Growth (Frequent Pattern Growth), and Eclat (Equivalence Class Clustering and Bottom-up Lattice Traversal).

Information

Association Rule Learning is commonly used in Market Basket Analysis, recommendation systems, inventory management, web usage mining, and fraud detection.

šŸŽÆ Learning Objectives

  • Understand Association Rule Learning.
  • Learn the concepts of support, confidence, and lift.
  • Understand Apriori, FP-Growth, and Eclat algorithms.
  • Compare the three algorithms and their applications.

šŸŒŸ What is Association Rule Learning?

Association Rule Learning discovers relationships of the form:

Which means:

  • If itemset A occurs, itemset B is likely to occur as well.

For example:

Customers purchasing bread often purchase butter.

CharacteristicAssociation Rule Learning
Learning TypeUnsupervised
Main GoalDiscover Item Relationships
Requires LabelsNo
Typical DatasetTransactional Data

šŸ“ Key Concepts

ConceptDescription
ItemSingle product or object.
ItemsetCollection of multiple items.
TransactionCollection of purchased items.
Frequent ItemsetItemset appearing frequently in transactions.
Association RuleRelationship between two itemsets.

šŸ“Š Support

Support measures how frequently an itemset appears in the dataset.

Remember

Higher support indicates that an itemset occurs more frequently in the dataset.

šŸ“Š Confidence

Confidence measures how often itemset B appears when A appears.

šŸ“Š Lift

Lift measures the strength of an association compared to random chance.

Lift ValueInterpretation
> 1Positive association.
= 1No association.
< 1Negative association.

šŸŒ Apriori Algorithm

Apriori identifies frequent itemsets using the Apriori Principle:

Remember

If an itemset is frequent, then all of its subsets must also be frequent.

How Apriori Works

šŸŒ² FP-Growth Algorithm

FP-Growth avoids generating candidate itemsets by compressing transactions into a compact Frequent Pattern Tree (FP-Tree).

Tip

FP-Growth is generally much faster than Apriori because it avoids repeated candidate generation and multiple database scans.

šŸŒ Eclat Algorithm

Eclat uses a vertical database format, storing transaction identifiers (TIDs) for each item instead of transaction records.

šŸŒ³ Association Rule Learning Workflow

Transaction Dataset
Find Frequent Itemsets
Compute Support
Generate Rules
Compute Confidence & Lift
Interesting Association Rules

šŸ“Š Apriori vs FP-Growth vs Eclat

FeatureAprioriFP-GrowthEclat
Candidate GenerationYesNoNo
Database ScansMultipleTwoOne Vertical Format
Main Data StructureCandidate ItemsetsFP-TreeTransaction ID Sets
SpeedSlowFastVery Fast
Large DatasetsModerateExcellentExcellent

šŸŽ›ļø Important Hyperparameters

HyperparameterDescription
min_supportMinimum support threshold.
min_confidenceMinimum confidence for association rules.
min_liftMinimum lift value.
max_lengthMaximum size of generated itemsets.

šŸ“Š Rule Evaluation Metrics

MetricPurpose
SupportFrequency of occurrence.
ConfidenceReliability of a rule.
LiftStrength beyond random chance.
LeverageDifference from independence.
ConvictionMeasures rule implication.

āš–ļø Advantages and Limitations

  • Discovers hidden purchasing patterns.
  • No labeled data required.
  • Easy to interpret association rules.
  • Widely used in recommendation systems.
  • Supports business decision-making.
  • Can generate a very large number of rules.
  • Apriori becomes slow for dense datasets.
  • Choosing appropriate thresholds is challenging.
  • Association does not imply causation.

šŸŒ Real-World Applications

ApplicationPurpose
šŸ›’ Market Basket AnalysisIdentify products frequently purchased together.
šŸŽ¬ Recommendation SystemsRecommend related products or content.
šŸŖ Retail Inventory PlanningOptimize product placement and stocking.
šŸŒ Web Usage MiningAnalyze navigation patterns.
šŸ’³ Fraud DetectionDiscover unusual transaction combinations.
šŸ„ Healthcare AnalyticsIdentify frequently co-occurring diseases and treatments.

šŸ’» Practical Example

Apriori Association Rule Mining Using mlxtend

import pandas as pd
from mlxtend.frequent_patterns import apriori, association_rules

# Sample one-hot encoded transaction dataset
data = pd.DataFrame({
    "Bread":  [1,1,1,0,1],
    "Milk":   [1,1,0,1,1],
    "Butter": [1,0,1,1,1],
    "Eggs":   [0,1,1,1,0]
})

# Find frequent itemsets
frequent_itemsets = apriori(
    data,
    min_support=0.4,
    use_colnames=True
)

# Generate association rules
rules = association_rules(
    frequent_itemsets,
    metric="confidence",
    min_threshold=0.7
)

print(frequent_itemsets)
print(rules[["antecedents","consequents","support","confidence","lift"]])

āš ļø Common Mistakes

  • Confusing correlation with causation.
  • Using a minimum support threshold that is too high or too low.
  • Interpreting rules based only on confidence while ignoring lift.
  • Generating excessive numbers of insignificant rules.
  • Applying Apriori to very large datasets where FP-Growth or Eclat would be more efficient.

Best Practice

Begin by selecting meaningful values for min_support and min_confidence, evaluate rules using multiple metrics such as support, confidence, and lift, prefer FP-Growth or Eclat for large transactional datasets due to their efficiency, and always validate discovered rules using domain knowledge before making business decisions.

šŸ“š Summary

Summary

Association Rule Learning discovers meaningful relationships among items in transactional datasets without requiring labeled data. Apriori generates frequent itemsets using candidate generation and pruning, FP-Growth improves efficiency through an FP-Tree, and Eclat uses a vertical transaction format for fast support computation. Together, these algorithms form the foundation of market basket analysis, recommendation systems, inventory optimization, fraud detection, and many other data mining applications where uncovering hidden associations is valuable.

šŸ”— Further Reading