Unit 5: Association Rule Mining

5.1 Introduction to Association Rule Mining

Association Rule Mining (also called Market Basket Analysis) discovers interesting relationships, patterns, and co-occurrences among items in large transactional databases. It answers the question: "What items are frequently bought together?"

Transactional Database

A transactional database is a collection of transactions, where each transaction is a set of items (an itemset). For example:

• Transaction T1: {Milk, Bread, Eggs}
• Transaction T2: {Bread, Diapers, Beer, Lettuce}
• Transaction T3: {Milk, Diapers, Beer, Coke}
• Transaction T4: {Bread, Milk, Diapers, Beer}
• Transaction T5: {Bread, Milk, Diapers, Coke}

Key Terminology

• Itemset: A collection of one or more items. An itemset with k items is a k-itemset.
• Support Count (σ): The frequency of occurrence of an itemset in the database.
• Minimum Support (min_sup): A threshold — only itemsets occurring at least this frequently are considered frequent.
• Frequent Itemset: An itemset whose support count ≥ min_sup.
• Association Rule: An expression of the form A → B, where A and B are disjoint itemsets.

5.2 Key Metrics

Association rules are evaluated using four key metrics that measure the strength, quality, and usefulness of discovered relationships.

Support

Support measures how frequently the itemset appears in the database. It indicates the statistical significance of a rule.

where N is the total number of transactions. Low support means the rule may be accidental — it captures too few transactions to be actionable.

Confidence

Confidence measures the reliability of the rule. It tells us: given that A is purchased, what is the probability B is also purchased?

High confidence means the rule is strong — A and B co-occur consistently. However, confidence alone can be misleading if B is very popular.

Lift

Lift corrects confidence by accounting for the baseline popularity of B. It measures how much more likely B is when A is present, compared to B's overall frequency.

• Lift > 1: A and B are positively correlated — A increases the likelihood of B.
• Lift = 1: A and B are independent — no association.
• Lift < 1: A and B are negatively correlated — A decreases the likelihood of B.

Conviction

Conviction measures the degree to which the antecedent (A) and consequent (B) are associated. It captures how wrong the rule would be if the relationship were random.

• Conviction = ∞: The rule is always correct (confidence = 1).
• Conviction > 1: The rule is better than random.
• Conviction = 1: A and B are independent.

5.3 Apriori Algorithm

The Apriori algorithm (Agrawal & Srikant, 1994) is the foundational algorithm for frequent itemset mining. It uses a level-wise, breadth-first approach with the anti-monotonicity (Apriori) property for pruning.

Anti-Monotonicity Property

If an itemset is infrequent, all its supersets must also be infrequent. This is the core insight that makes Apriori efficient. Once an itemset is found to be below min_sup, we can eliminate all larger itemsets containing it without counting them.

Algorithm Steps

1. Scan 1: Count support of all 1-itemsets. Remove those below min_sup to get L₁.
2. Generate Candidates (Cₖ): Join Lₖ₋₁ with itself to produce candidate k-itemsets.
3. Prune: Remove candidates containing any infrequent (k-1)-subset.
4. Scan k: Count support of remaining candidates. Keep those above min_sup → Lₖ.
5. Repeat steps 2-4 until no more frequent itemsets can be found.
6. Generate Rules: From all frequent itemsets, generate rules meeting min_conf.

Example Walkthrough

Given min_sup = 2 (itemset must appear in at least 2 of 5 transactions):

• Step 1: {Beer}:3, {Bread}:4, {Coke}:2, {Diapers}:4, {Eggs}:1, {Lettuce}:1, {Milk}:4 — Remove {Eggs} and {Lettuce} (below min_sup).
• Step 2: Join to form 2-itemsets: {Beer,Diapers}:3, {Bread,Milk}:3, {Diapers,Milk}:3, etc.
• Step 3: Continue until no more frequent itemsets found.
• Step 4: Generate rules: {Diapers} → {Beer} (conf=3/4=75%), {Beer} → {Diapers} (conf=3/3=100%).

Strengths and Weaknesses

• Strengths: Simple to understand and implement. Correctness guaranteed. Works well for dense datasets with small itemsets.
• Weaknesses: Generates many candidates (especially with long frequent itemsets). Requires multiple database scans (one per k). Can be slow for large, sparse datasets.

5.4 FP-Growth Algorithm

The FP-Growth algorithm (Han, Pei & Yin, 2000) mines frequent patterns without candidate generation. It compresses the database into a compact tree structure called the FP-tree, then extracts frequent patterns directly.

FP-Tree Construction

1. Scan 1: Count support of all 1-itemsets. Sort items in descending order of support.
2. Scan 2: For each transaction, insert items into the FP-tree in sorted order. Shared prefixes are merged.
3. Header Table: Maintain a linked list for each item pointing to its occurrences in the tree for traversal.

Frequent Pattern Mining

1. Start from the least frequent item in the header table.
2. Follow the header links to find all paths containing that item.
3. Construct a conditional FP-tree for that item by accumulating path counts and removing infrequent items.
4. Recursively mine the conditional FP-tree to extract all frequent patterns ending with that item.

Apriori vs FP-Growth Comparison

• Scans: Apriori requires k scans (one per level); FP-Growth requires exactly 2 scans.
• Candidates: Apriori generates and tests candidates; FP-Growth avoids candidates entirely.
• Data Structure: Apriori uses hash trees or vertical formats; FP-Growth uses a compact FP-tree.
• Performance: FP-Growth is typically 1-2 orders of magnitude faster on large, sparse datasets.
• Memory: FP-Growth may use more memory for very dense datasets due to tree overhead.

5.5 Applications

Association rule mining powers a wide range of real-world applications across industries:

Retail Cross-Selling

Supermarkets and e-commerce platforms use association rules to identify products that are frequently purchased together. Rules like {bread} → {butter} drive cross-selling strategies, store layout optimization, and promotional pricing. Amazon attributes over 35% of its revenue to association-based recommendations.

Recommendation Engines

Streaming platforms (Netflix, Spotify) and e-commerce sites use association rules combined with collaborative filtering to suggest items. "Users who liked X also liked Y" is a direct application of association rule mining. Spotify uses 40+ audio features alongside association rules to build its recommendation system.

Bioinformatics

Association rules are used to discover relationships between genes, proteins, and diseases. Gene co-expression patterns, protein-protein interactions, and drug side-effect correlations are all mined using association rule techniques.

Web Usage Mining

Web servers log user navigation paths. Association rules reveal common browsing patterns (e.g., users who visit the product page then the reviews page are likely to purchase). This informs website redesign, ad placement, and session prediction.