ML7331 Module 12

Association Rule Mining Study Guide

Overview of Association Analysis

Association analysis examines relationships between items in a dataset to determine patterns of co-occurrence. In association rule mining, these patterns are used to generate rules that predict when certain items will appear together.

For example, in a retail setting, this analysis might reveal that “if a customer buys bread and milk, they are likely to also buy eggs.”

Key Concepts

1. Association Rule Mining:
   • Definition: Given a set of transactions, association rule mining seeks to find patterns or rules that explain when items co-occur in transactions.
   • Applications: Common in recommendation systems (e.g., Amazon’s “Customers who bought this also bought”) and in healthcare data (e.g., high blood pressure often co-occurs with stress).

1. Association Rule Mining Recap

Association rule mining aims to uncover relationships between variables in transaction data. Each transaction is a collection of items, and the objective is to determine if certain items frequently co-occur. These relationships can be represented as association rules of the form \(X \rightarrow Y\), where \(X\) implies \(Y\) with a certain degree of confidence and support.

2. Frequent Itemsets:
   • Definition: Collections of one or more items that appear frequently together in the dataset. For example, {bread, milk} could be a frequent itemset.
   • Support Count: The frequency of occurrence of an itemset within the dataset.
   • Support: The proportion of transactions that contain the itemset, calculated as: \[ \text{Support} = \frac{\text{Support Count}}{\text{Total Transactions}} \]

2. Frequent Itemset Generation

Generating frequent itemsets involves identifying groups of items that often appear together in transactions. The candidate itemset lattice is used to systematically evaluate itemset combinations, starting from single items and progressing to larger groups. Key to reducing computational load is the Apriori principle, which helps to avoid evaluating all possible combinations by eliminating itemsets that do not meet the minimum support threshold.

Example: For items like {milk, bread, diapers}, frequent itemsets are those that appear in a sufficient number of transactions. Calculating support for itemsets and generating candidate lattices enables structured exploration of co-occurrence relationships.

3. Association Rules:
   • Definition: Expressed as \(X \rightarrow Y\), where \(X\) and \(Y\) are itemsets, meaning “If \(X\) occurs, \(Y\) is likely to occur.”
   • Support for a Rule: The fraction of transactions that contain both \(X\) and \(Y\).
   • Confidence for a Rule: Indicates how often \(Y\) appears in transactions that contain \(X\), given by: \[ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support of } X \cup Y}{\text{Support of } X} \]

Rule Evaluation Metrics

• Support: Helps in identifying the overall frequency of an itemset.
• Confidence: Measures the reliability of an inference; higher confidence indicates a stronger association.
• Lift (optional): Measures how much more likely \(Y\) is to occur when \(X\) is present compared to when \(X\) is absent.

3. Rule Generation

Once frequent itemsets are identified, the next step is creating association rules from these sets, ensuring each rule meets minimum support and confidence requirements. These rules are derived from itemsets by dividing them into antecedents (if-part) and consequents (then-part), with metrics calculated for each rule.

Rule Metrics: - Support: Measures how often \(X \cup Y\) appears in the dataset. - Confidence: Measures the likelihood of \(Y\) appearing when \(X\) is present, calculated as: \[ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support of } X \cup Y}{\text{Support of } X} \] - Lift: Evaluates the strength of an association rule relative to random chance, providing insight into the rule’s significance.

Steps in Association Rule Mining

1. Frequent Itemset Generation:
   • Generate all itemsets that meet a minimum support threshold, a process that is computationally intensive.
2. Rule Generation:
   • Use the frequent itemsets to create association rules, ensuring they meet both minimum support and confidence thresholds.
3. Optimizing Computation:
   • Candidate Lattice: Visualizes all potential itemsets for frequent set mining.
   • Apriori Principle: If an itemset is infrequent, all supersets are also infrequent, helping to reduce computation by pruning.

Example Calculations

Suppose a dataset has 5 transactions, and {milk, bread, diapers} appears in 2 of them: - Support Count for {milk, bread, diapers}: 2 - Support for {milk, bread, diapers}: \[ \text{Support} = \frac{2}{5} = 0.4 \]

If {milk, diapers} appears in 3 transactions, the confidence that {milk, diapers} \rightarrow beer is: \[ \text{Confidence} = \frac{\text{Support of } \{milk, diapers, beer\}}{\text{Support of } \{milk, diapers\}} \]

Python Code for Support and Confidence Calculation

from itertools import combinations

# Example transaction data
transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'diapers', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'bread', 'diapers', 'beer'},
    {'milk', 'bread'}
]

def support(itemset, transactions):
    count = sum(1 for transaction in transactions if itemset.issubset(transaction))
    return count / len(transactions)

def confidence(itemset_X, itemset_Y, transactions):
    return support(itemset_X | itemset_Y, transactions) / support(itemset_X, transactions)

# Calculate support and confidence for a rule
itemset_X = {'milk', 'diapers'}
itemset_Y = {'beer'}

rule_support = support(itemset_X | itemset_Y, transactions)
rule_confidence = confidence(itemset_X, itemset_Y, transactions)

print("Support:", rule_support)
print("Confidence:", rule_confidence)

Visualizing the Candidate Lattice

To visualize a candidate lattice and optimize computation: 1. List items in a hierarchy (e.g., single items, pairs, triples). 2. Use the Apriori Principle to prune infrequent itemsets.

import networkx as nx
import matplotlib.pyplot as plt

# Example of candidate lattice visualization
G = nx.DiGraph()
G.add_edges_from([
    ("A", "AB"), ("A", "AC"), ("B", "AB"), 
    ("B", "BC"), ("C", "AC"), ("C", "BC"),
    ("AB", "ABC"), ("AC", "ABC"), ("BC", "ABC")
])

plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_size=3000, node_color="lightblue", font_size=10, font_weight="bold")
plt.show()

Summary

• Association rule mining finds co-occurrence patterns in transaction data.
• Support and confidence help quantify how strongly items are associated.
• Apriori Principle and candidate lattice reduce computational load, enabling scalable analysis.

4. Efficient Computation with the Apriori Principle

The Apriori algorithm optimizes frequent itemset generation by eliminating non-frequent itemsets and their supersets early in the process. This reduces the search space and makes rule generation computationally feasible for large datasets, often visualized as a candidate lattice to track the hierarchical progression of item combinations.

5. Implementation Example in Python

To compute support and confidence for specific rules in Python:

from itertools import combinations

# Example transactions
transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'diapers', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'bread', 'diapers', 'beer'},
    {'milk', 'bread'}
]

# Function to calculate support
def support(itemset, transactions):
    count = sum(1 for transaction in transactions if itemset.issubset(transaction))
    return count / len(transactions)

# Function to calculate confidence
def confidence(itemset_X, itemset_Y, transactions):
    return support(itemset_X | itemset_Y, transactions) / support(itemset_X, transactions)

# Calculate support and confidence for a rule
itemset_X = {'milk', 'diapers'}
itemset_Y = {'beer'}

rule_support = support(itemset_X | itemset_Y, transactions)
rule_confidence = confidence(itemset_X, itemset_Y, transactions)

print("Support:", rule_support)
print("Confidence:", rule_confidence)

This code provides a structured way to calculate support and confidence for a rule such as {milk, diapers} → beer, helping identify meaningful associations in transaction data.

6. Visualizing Candidate Lattices

The candidate lattice organizes itemsets by their frequency, aiding in the application of the Apriori principle. Visualizing it with NetworkX:

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([
    ("A", "AB"), ("A", "AC"), ("B", "AB"), 
    ("B", "BC"), ("C", "AC"), ("C", "BC"),
    ("AB", "ABC"), ("AC", "ABC"), ("BC", "ABC")
])

plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_size=3000, font_size=10, font_weight="bold")
plt.show()

Recap

Association rule mining, supported by efficient itemset generation through the Apriori principle and candidate lattices, enables scalable analysis of transactional data, revealing patterns with practical applications across industries.

These concepts can be used to identify valuable patterns that can be applied in business, healthcare, and other domains requiring co-occurrence analysis.

Quiz 1:

The Apriori principle states that if an itemset is infrequent, any larger itemsets containing it as a subset must also be infrequent. Since we know that ACE is infrequent, only those itemsets that contain ACE as a subset can immediately be concluded to be infrequent.

Here’s how this reasoning applies to each option:

1. ABCE and ABCDE:
   • These contain ACE as a subset, but since we are considering infrequency, we are not focusing on sets that mix additional items beyond ACE with B and D unnecessarily.
2. ACDE:
   • This itemset contains ACE as a subset (with the addition of D) and thus directly follows from the Apriori principle. If ACE is infrequent, ACDE must also be infrequent because it includes all items of ACE plus an additional item, D.
3. BCDE only:
   • This itemset does not contain ACE as a subset, so we cannot conclude anything about its frequency based on the infrequency of ACE alone.

Therefore, the correct answer is ACDE only because it is the only itemset in the choices provided that includes ACE as a subset, making it directly inferrable as infrequent based on the Apriori principle.

Frequent Itemset Generation:

This diagram shows a candidate lattice for itemsets where AB has been found to be infrequent. According to the Apriori principle, any supersets of an infrequent itemset are also infrequent.

1. AB is infrequent, so all itemsets containing AB (like ABC, ABD, ABE, ABCD, ABCE, ABDE, and ABCDE) are pruned (marked with the pink dashed line) and considered infrequent without further checking.

2. The itemset ACDE (highlighted in yellow) does not include AB as a subset, so it is not affected by the infrequency of AB. This means ACDE is evaluated separately from AB and its supersets.

3. So, Only supersets containing AB are immediately pruned. - ACDE remains unaffected because it does not contain AB.

Continuing

Here’s an enhanced study guide for Association Rule Mining and Frequent Itemset Generation, including additional context from the latest file.

---

Study Guide: Association Rule Mining and Frequent Itemset Generation

---

1. Overview of Association Rule Mining

• Purpose: Identify patterns in large datasets to reveal relationships between items. Applications include market basket analysis and recommendation systems.
• Example: Retail transactions may show that buying milk and bread often correlates with purchasing eggs, aiding inventory management and marketing strategies.

Key Definitions:

• Association Rule: A rule showing when one item or itemset co-occurs with another.

• Frequent Itemset: A set of items that appears frequently together in a dataset.

• Support: Proportion of transactions containing an itemset. Formula: \[ \text{Support}(X) = \frac{\text{Frequency of } X}{\text{Total Transactions}} \]

• Confidence: Reliability of an association rule, showing how often \(Y\) appears in transactions containing \(X\). Formula: \[ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} \]

• Objective: Association analysis uncovers patterns in transaction data, often formulated as association rules \(X \rightarrow Y\), where the presence of \(X\) suggests the likelihood of \(Y\).

• Applications: Widely used in retail (e.g., market basket analysis), healthcare (co-occurrence of symptoms), and finance (transaction pattern analysis).

Key Metrics:

• Support: Frequency of an itemset’s occurrence in transactions. \[ \text{Support}(X) = \frac{\text{Transactions containing } X}{\text{Total Transactions}} \]
• Confidence: Likelihood that \(Y\) occurs given \(X\). \[ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} \]
• Lift: Strength of association, comparing observed to expected co-occurrence. \[ \text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)} \]

2. Frequent Itemset Generation Using the Apriori Algorithm

The Apriori Algorithm iteratively identifies frequent itemsets by leveraging smaller, frequent subsets.

1. Candidate Itemsets: Start with single frequent items, and combine them iteratively to generate larger itemsets.
2. Apriori Principle: If an itemset is infrequent, all supersets are also infrequent, reducing search space.
3. Support Count: Count occurrences of each candidate itemset, pruning those below the minimum support threshold.
4. Iterative Pruning: Repeat the process for k-itemsets until no further frequent itemsets remain.

3. Steps in Association Rule Mining

Step 1: Frequent Itemset Generation

• Objective: Identify itemsets meeting minimum support thresholds.
• Candidate Lattice: Structures possible itemsets in levels (individual items, pairs, triplets) to filter based on support.

Step 2: Rule Generation from Frequent Itemsets

• Use frequent itemsets to generate “If-Then” association rules, applying minimum confidence and support to retain significant rules.

4. Efficiency Improvements in Itemset Generation

A. Apriori Principle:

• Concept: If an itemset is infrequent, all its supersets are also infrequent.
• Application: If {ACE} is infrequent, then all supersets {ABCE}, {ACDE}, and {ABCDE} can be skipped.

B. FP-Growth (Frequent Pattern Growth):

• An efficient alternative to Apriori using an FP-tree structure.
• FP-tree organizes transactions in two passes, enabling frequent itemset mining without explicitly generating candidate sets.

5. Frequent Itemset Generation with Apriori

The Apriori Algorithm:

• Step-by-Step:
  1. Start with k = 1 for single items and find frequent itemsets.
  2. Generate itemsets of length \(k+1\) from frequent \(k\)-itemsets.
  3. Prune infrequent sets and repeat until no more frequent itemsets are found.
• Complexity: Each iteration over the dataset (especially for large datasets) increases computational costs, motivating the use of efficient data structures and pruning methods.

6. Reducing Complexity with Hash Trees

• Hash Tree: Used in Apriori to reduce comparison costs by organizing itemsets efficiently, checking only relevant candidates per transaction.
• Functionality: Divides items based on hash values to minimize comparison time.
• Example: Given three-item candidate sets, the hash tree filters based on the first item’s hash and splits nodes as needed to ensure optimal access time.

7. Complexity Reduction in Apriori

• Candidate Pruning: By applying the Apriori principle, avoid testing itemsets that include infrequent subsets.
• Hash Trees: Hash trees store candidate itemsets for efficient lookups, reducing the comparison load when calculating support.

Code Example for Support Calculation

from itertools import combinations

# Example transaction data
transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'diapers', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'bread', 'diapers', 'beer'},
    {'milk', 'bread'}
]

def support(itemset, transactions):
    count = sum(1 for transaction in transactions if itemset.issubset(transaction))
    return count / len(transactions)

# Calculating support for {milk, bread}
itemset = {'milk', 'bread'}
print("Support:", support(itemset, transactions))

8. FP-Growth Algorithm and Pattern Trees

• Overview: Unlike Apriori, FP-Growth only scans the database twice.
• Process:
  1. Count frequent 1-itemsets and filter by minimum support.
  2. Sort transactions by item frequency and build the FP-tree by adding transactions sequentially, incrementing counts at existing nodes.
• Divide-and-Conquer: Once constructed, the tree is recursively divided to find frequent itemsets without re-scanning the dataset.

9. FP-Growth Algorithm

The FP-Growth Algorithm offers a scalable alternative to Apriori by constructing a Frequent Pattern Tree (FP-Tree), eliminating the need for multiple database scans and candidate generation.

FP-Growth Process:

1. First Pass: Identify frequent 1-itemsets, sorting them by frequency.
2. FP-Tree Construction: Build a tree where transactions are hierarchically organized, reducing redundancy.
3. Divide and Conquer: Recursively generate conditional trees from the FP-Tree to mine frequent patterns.

Code Example for FP-Tree Construction

class TreeNode:
    def __init__(self, name, count):
        self.name = name
        self.count = count
        self.parent = None
        self.children = {}

# Adding transactions to the FP-tree
root = TreeNode("null", 1)
transactions = [["milk", "bread"], ["beer", "diapers"], ["milk", "diapers"]]

def add_transaction(node, transaction):
    for item in transaction:
        if item in node.children:
            node.children[item].count += 1
        else:
            child_node = TreeNode(item, 1)
            child_node.parent = node
            node.children[item] = child_node
        node = node.children[item]

for transaction in transactions:
    add_transaction(root, sorted(transaction))

# Visualization of FP-tree
import networkx as nx
import matplotlib.pyplot as plt

def visualize_tree(node, graph, parent=None):
    graph.add_node(node.name)
    if parent:
        graph.add_edge(parent, node.name)
    for child in node.children.values():
        visualize_tree(child, graph, node.name)

G = nx.DiGraph()
visualize_tree(root, G)
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_size=2000, font_size=10, font_weight="bold")
plt.show()

10. Comparison and Key Insights

• Support Threshold: Setting an appropriate minimum support level is critical; low thresholds generate excessive patterns, while high thresholds might miss useful patterns.
• Apriori vs. FP-Growth:
  • Apriori uses multiple database passes and explicit candidate generation.
  • FP-Growth organizes items into a tree, significantly reducing database access.
• Hash Trees in Apriori: Reduces the number of comparisons by grouping items based on hash values.
• Conditional Trees in FP-Growth: Splits the FP-Tree to allow targeted, recursive mining of itemsets, enhancing computational efficiency.

---

11. Practical Applications of Association Rule Mining

• Retail: Product recommendation and shelf arrangement based on item co-occurrence.
• Healthcare: Identifying relationships between symptoms or medical conditions.
• Finance: Pattern detection for fraud and unusual transaction behaviors.

---

12. Example Calculations

Calculating Support and Confidence

Given transactions, calculate support and confidence for {milk, bread} \rightarrow {eggs}.

# Example transactions
transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'milk', 'bread', 'eggs'},
    {'bread', 'diapers', 'eggs'},
    {'milk', 'bread'}
]

# Support function
def support(itemset, transactions):
    count = sum(1 for transaction in transactions if itemset.issubset(transaction))
    return count / len(transactions)

# Confidence function
def confidence(X, Y, transactions):
    return support(X | Y, transactions) / support(X, transactions)

# Calculate support and confidence
itemset_X = {'milk', 'bread'}
itemset_Y = {'eggs'}
print("Support:", support(itemset_X | itemset_Y, transactions))
print("Confidence:", confidence(itemset_X, itemset_Y, transactions))

---

13. Visualization: Candidate Lattice

import networkx as nx
import matplotlib.pyplot as plt

# Visualization of a candidate lattice
G = nx.DiGraph()
G.add_edges_from([
    ("A", "AB"), ("A", "AC"), ("B", "AB"), 
    ("B", "BC"), ("C", "AC"), ("C", "BC"),
    ("AB", "ABC"), ("AC", "ABC"), ("BC", "ABC")
])

plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_size=3000, node_color="skyblue", font_size=10, font_weight="bold")
plt.title("Candidate Lattice for Itemset Generation")
plt.show()

---

Recap

1. Association Rule Mining identifies co-occurrence patterns, critical in fields from e-commerce to healthcare.
2. Support and Confidence provide core evaluation metrics, with Lift further refining association strength.
3. Apriori Principle and FP-Growth enable scalable itemset generation by reducing dataset passes and simplifying comparisons.
4. FP-Tree offers a compact structure, facilitating recursive pattern discovery without additional database scans.

Part 3

Rules Generation

Study Guide: Association Analysis and Rule Mining (Module 12)

---

1. Overview

Association analysis focuses on identifying patterns in transactional data where the occurrence of certain items is associated with others. This type of analysis is foundational in fields such as retail for market basket analysis and healthcare for symptom-diagnosis relationships.

Key Concepts and Definitions

Association Rule Mining: - Objective: To uncover co-occurrence patterns within transaction data, such as in retail where buying one item suggests another purchase. - Association Rule Format: \(X \rightarrow Y\), meaning if \(X\) occurs, \(Y\) is likely to occur as well.

Key Metrics: 1. Support: Measures how frequently an item or itemset appears in the data. \[ \text{Support}(X) = \frac{\text{Transactions containing } X}{\text{Total Transactions}} \] 2. Confidence: Probability of \(Y\) occurring given that \(X\) has occurred. \[ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} \] 3. Lift: Evaluates association strength; a lift greater than 1 indicates positive association, while less than 1 indicates negative association. \[ \text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)} \] 4. Interest: Compares observed and expected frequency of co-occurrence. \[ \text{Interest}(X \rightarrow Y) = \text{Support}(X \cup Y) - \text{Support}(X) \times \text{Support}(Y) \]

1. Frequent Itemsets:
   • Definition: Sets of items frequently appearing together in transactions.
   • Support: Measures how often an itemset appears in the database: \[ \text{Support}(X) = \frac{\text{Frequency of } X \text{ in transactions}}{\text{Total transactions}} \]
   • Example Calculation: If itemset {A, B, C} appears in 3 out of 10 transactions, then: \[ \text{Support} = \frac{3}{10} = 0.3 \]
2. Association Rules:
   • Definition: Rules of the form \(X \rightarrow Y\) meaning “If \(X\), then \(Y\)”.
   • Confidence: The likelihood of \(Y\) given \(X\), calculated as: \[ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} \]
   • Lift: Measures the strength of a rule by comparing the observed support to that expected if \(X\) and \(Y\) were independent: \[ \text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)} \]
3. Maximal and Closed Itemsets:
   • Maximal Itemsets: An itemset with no frequent supersets.
   • Closed Itemsets: An itemset is closed if it has no superset with the same support. ————————————————————————

Step-by-Step Methodology

1. Identify Frequent Itemsets: Find sets of items that occur frequently based on a minimum support threshold.
2. Generate Association Rules: From frequent itemsets, generate rules that meet minimum confidence.

---

Algorithms for Association Rule Mining

1. Apriori Algorithm

• Purpose: Efficiently finds frequent itemsets by iteratively expanding smaller frequent itemsets.
• Apriori Principle: If an itemset is infrequent, all its supersets are also infrequent.
• Process:
  • Begin with frequent 1-itemsets.
  • Generate \(k\)-itemset candidates from frequent \(k-1\)-itemsets.
  • Count occurrences and prune non-frequent sets based on support threshold.

Example Code:

from itertools import combinations

transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'diapers', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'bread', 'diapers', 'beer'},
    {'milk', 'bread'}
]

def apriori(transactions, min_support):
    # Generate frequent itemsets and calculate support
    # Implementation would follow here
    pass

AGAIN for good measure

The Apriori algorithm generates frequent itemsets by iteratively expanding smaller itemsets (of size \(k\)) to larger ones (of size \(k+1\)) and pruning non-frequent candidates based on minimum support criteria. This reduces computational costs by eliminating unnecessary evaluations:

from itertools import combinations

def apriori(transactions, min_support):
    single_items = {item for t in transactions for item in t}
    current_itemsets = [{i} for i in single_items]
    
    def get_support(itemset):
        return sum(1 for t in transactions if itemset <= set(t)) / len(transactions)
    
    result = []
    while current_itemsets:
        frequent_itemsets = [s for s in current_itemsets if get_support(s) >= min_support]
        result.extend(frequent_itemsets)
        current_itemsets = [a | b for a in frequent_itemsets for b in frequent_itemsets if len(a | b) == len(a) + 1]
    return result

2. FP-Growth Algorithm

• Purpose: Avoids generating candidates by creating a Frequent Pattern Tree (FP-Tree), a compressed structure that retains item occurrence patterns.
• Process:
  • Create an FP-tree from transactions, sorted by frequency.
  • Extract patterns through recursive decomposition of conditional trees.

FP-Tree Code Example:

class TreeNode:
    def __init__(self, name, count):
        self.name = name
        self.count = count
        self.parent = None
        self.children = {}

# Example FP-tree construction
root = TreeNode("null", 1)
transactions = [["milk", "bread"], ["beer", "diapers"], ["milk", "diapers"]]

def add_transaction(node, transaction):
    # Constructing FP-tree logic here
    pass

---

Advanced Topics: Rule Generation and Lattice Structure

Rule Generation: - Generate rules by evaluating subsets of a frequent itemset. - Candidate Lattice for Rules: - For a frequent itemset, create rules by assigning each subset as antecedent or consequent. - Pruning: Use confidence threshold to prune low-confidence rules.

Visualization of Rule Lattice: A rule lattice represents various rule possibilities from a frequent itemset. It helps visualize how rules with lower confidence can be pruned based on the anti-monotonicity property of confidence.

Example: If \(\text{Confidence}(ABC \rightarrow D)\) is low, prune any rule from the lattice that would have lower confidence.

---

Compact Representation of Patterns

1. Maximal Itemsets: Largest itemsets that are frequent; no superset is frequent.
2. Closed Itemsets: Itemsets with no superset having the same support.
   • Purpose: Reduces redundancy by only tracking the most informative itemsets.

---

Practical Application: Evaluating Rule Interestingness

1. Objective Metrics:
   • Calculate support, confidence, lift, and interest using contingency tables.
2. Subjective Interestingness:
   • Incorporate domain knowledge to prioritize actionable or unexpected patterns.

---

Example Calculation

For the rule # Students <80% → Pop Quiz (based on the provided table): - Confidence: \(\frac{4}{12} = 0.33\) - Lift: \(\frac{0.33}{(5/25)} = 1.65\) - Interest: \(1.66\)

---

This guide summarizes core principles of association analysis, frequent itemset generation, and rule mining, highlighting practical metrics and algorithms used in the field. It combines theoretical insights with code examples to facilitate comprehension of complex topics.

Images:

image with answers

---

4. Rule Generation and Lattice Visualization

For a frequent itemset \(L\), generate rules by finding all subsets \(F\) and using \(F \rightarrow (L \setminus F)\) as candidate rules. Apply confidence to filter significant rules.

• Lattice Visualization: A lattice graph visualizes relationships between itemset levels. The anti-monotone property helps prune less-confident rules early in this structure.

---

5. Code Example for Rule Generation

The following example calculates support and confidence for candidate rules from a list of transactions.

transactions = [{'milk', 'bread', 'butter'}, {'milk', 'bread'}, {'bread', 'butter'}, {'milk', 'butter'}]

def support(itemset, transactions):
    return sum(1 for t in transactions if itemset <= t) / len(transactions)

def confidence(antecedent, consequent, transactions):
    return support(antecedent | consequent, transactions) / support(antecedent, transactions)

antecedent, consequent = {'milk'}, {'bread'}
print("Support:", support(antecedent | consequent, transactions))
print("Confidence:", confidence(antecedent, consequent, transactions))

---

6. Evaluation Metrics

1. Lift: Indicates the strength of association beyond random chance. \[ \text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)} \]

2. Interest: The difference between observed co-occurrence and expected independence.

7. Practical Example in Python

Visualize rules and relationships using a graph to highlight confidence levels and prune based on thresholds.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([("A", "AB"), ("B", "BC"), ("C", "ABC")])
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_size=3000, font_size=10)
plt.show()# Study Guide: Association Analysis and Rule Mining (Module 12)

---

### 1. Overview

**Association Analysis** focuses on identifying patterns in transactional data where the occurrence of certain items suggests the presence of others. This analysis is essential in fields such as **retail** (market basket analysis) and **healthcare** (symptom-diagnosis relationships).

### Key Concepts and Definitions

- **Association Rule Mining**:
   - **Objective**: To uncover co-occurrence patterns within transaction data, where buying one item might suggest purchasing another.
   - **Association Rule Format**: \( X \rightarrow Y \), meaning if \( X \) occurs, \( Y \) is likely to occur as well.

#### Key Metrics

1. **Support**: Measures how frequently an item or itemset appears in the data.
   \[
   \text{Support}(X) = \frac{\text{Transactions containing } X}{\text{Total Transactions}}
   \]

2. **Confidence**: Probability of \( Y \) occurring given that \( X \) has occurred.
   \[
   \text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)}
   \]

3. **Lift**: Evaluates association strength; a lift greater than 1 indicates a positive association, while less than 1 indicates a negative association.
   \[
   \text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)}
   \]

4. **Interest**: Compares observed and expected frequency of co-occurrence.
   \[
   \text{Interest}(X \rightarrow Y) = \text{Support}(X \cup Y) - \text{Support}(X) \times \text{Support}(Y)
   \]

---

### Methodology

1. **Identify Frequent Itemsets**: Find sets of items that occur frequently based on a minimum support threshold.
2. **Generate Association Rules**: From frequent itemsets, generate rules that meet minimum confidence.

---

### Algorithms for Association Rule Mining

#### 1. **Apriori Algorithm**

- **Purpose**: Efficiently finds frequent itemsets by expanding smaller itemsets iteratively.
- **Apriori Principle**: If an itemset is infrequent, all its supersets are also infrequent.
- **Process**:
   - Start with frequent 1-itemsets.
   - Generate \( k \)-itemset candidates from frequent \( k-1 \)-itemsets.
   - Count occurrences and prune non-frequent sets based on a support threshold.

**Example Code**:
```python
from itertools import combinations

transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'diapers', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'bread', 'diapers', 'beer'},
    {'milk', 'bread'}
]

def apriori(transactions, min_support):
    # Generate frequent itemsets and calculate support
    pass

- or- 

from itertools import combinations

transactions = [
    {'milk', 'bread', 'beer'},
    {'milk', 'diapers', 'beer'},
    {'milk', 'bread', 'diapers'},
    {'bread', 'diapers', 'beer'},
    {'milk', 'bread'}
]

def apriori(transactions, min_support):
    single_items = {item for t in transactions for item in t}
    current_itemsets = [{i} for i in single_items]
    
    def get_support(itemset):
        return sum(1 for t in transactions if itemset <= set(t)) / len(transactions)
    
    result = []
    while current_itemsets:
        frequent_itemsets = [s for s in current_itemsets if get_support(s) >= min_support]
        result.extend(frequent_itemsets)
        current_itemsets = [a | b for a in frequent_itemsets for b in frequent_itemsets if len(a | b) == len(a) + 1]
    return result

2. FP-Growth Algorithm

• Purpose: Avoids generating candidates by creating a Frequent Pattern Tree (FP-Tree), a compressed structure that retains item occurrence patterns.
• Process:
  • Build an FP-tree from transactions, sorted by frequency.
  • Extract patterns through recursive decomposition of conditional trees.

FP-Tree Code Example:

class TreeNode:
    def __init__(self, name, count):
        self.name = name
        self.count = count
        self.parent = None
        self.children = {}

# Example FP-tree construction
root = TreeNode("null", 1)
transactions = [["milk", "bread"], ["beer", "diapers"], ["milk", "diapers"]]

def add_transaction(node, transaction):
    # Constructing FP-tree logic here
    pass

---

Advanced Topics: Rule Generation and Lattice Structure

• Rule Generation:
  • Generate rules by evaluating subsets of a frequent itemset.
  • Candidate Lattice for Rules: Create rules by assigning subsets as antecedent or consequent, using confidence to prune low-confidence rules.

Visualization of Rule Lattice: A rule lattice helps visualize potential rules from a frequent itemset, allowing pruning of rules with lower confidence based on the anti-monotonicity property.

Example: If \(\text{Confidence}(ABC \rightarrow D)\) is low, prune any rule in the lattice with lower confidence.

---

Compact Representation of Patterns

1. Maximal Itemsets: Largest itemsets that are frequent; no superset is frequent.
2. Closed Itemsets: Itemsets with no superset having the same support.
   • Purpose: Reduces redundancy by only tracking the most informative itemsets.

---

Practical Application: Evaluating Rule Interestingness

1. Objective Metrics:
   • Calculate support, confidence, lift, and interest using contingency tables.
2. Subjective Interestingness:
   • Use domain knowledge to prioritize actionable or unexpected patterns.

---

Example Calculation

For the rule # Students <80% → Pop Quiz: - Confidence: \(\frac{4}{12} = 0.33\) - Lift: \(\frac{0.33}{(5/25)} = 1.65\) - Interest: 1.66

---

Practical Example in Python

Visualization:

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([("A", "AB"), ("B", "BC"), ("C", "ABC")])
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_size=3000, font_size=10)
plt.show()

---

This image represents a rule generation lattice for a frequent itemset, specifically {Male, 3rd, Not Survive}. In this lattice, each node corresponds to a rule derived by assigning subsets of the itemset as antecedents or consequents. The arrows illustrate the process of rule decomposition, showing how larger rules can be broken down into simpler rules. Here’s an analysis based on our previous discussion:

Structure of the Lattice

• Top Node: {Male, 3rd, Not Survive} => ∅
  • This node represents the entire frequent itemset with no specific rule created yet (i.e., no assignment of antecedent or consequent).
• Next Level Down: The lattice splits into rules with a single item as the consequent. Examples include:
  • {3rd, Not Survive} => {Male}
  • {Male, Not Survive} => {3rd}
  • {3rd, Male} => {Not Survive}
  • These represent rules with two-item antecedents implying the remaining item as the consequent.
• Further Levels: The lattice continues to split downwards, creating rules with fewer items in the antecedent and more items in the consequent.
  • For example, {Not Survive} => {Male, 3rd} implies that if someone did not survive, they are likely a male in 3rd class.
  • Each node lower in the lattice represents rules with simpler antecedents, leading to broader consequents.

Key Concepts Illustrated

1. Rule Generation: This lattice structure visually represents the process of generating association rules from a frequent itemset by evaluating all possible subset combinations for antecedents and consequents.

2. Anti-Monotonicity Property: Confidence typically follows an anti-monotonic property as we move down the lattice. This means that if a rule higher in the lattice (e.g., {3rd, Not Survive} => {Male}) has low confidence, then all rules derived from it by reducing the antecedent will have even lower confidence. This property allows us to prune lower confidence rules from consideration.

3. Pruning and Efficiency: By using the lattice structure, we can effectively prune rules that do not meet confidence or other evaluation thresholds, similar to how the Apriori principle works in frequent itemset generation. For example, if {Male, Not Survive} => {3rd} has low confidence, any further rules generated from this (with fewer antecedents and more items in the consequent) can be ignored.

4. Application of Rule Evaluation Metrics:

   • Confidence: For each rule, we would calculate the confidence by determining how often the antecedent appears with the consequent in the dataset.
   • Lift and Interest: These additional metrics could further evaluate the “interestingness” of each rule, especially for rules that seem statistically significant or actionable.

Summary

This lattice visualization is a valuable tool for rule generation and pruning. It systematically represents all possible rules derived from a frequent itemset and helps apply metrics (like confidence and lift) to keep only the most interesting and relevant rules. This technique is particularly helpful in complex datasets, enabling efficient rule mining and association analysis.