Data Engineering: Mining Intelligent Data Patterns and Association Rules and Algorithms

Introduction to Frequent Pattern Analysis

• Definition of Frequent Pattern: A frequent pattern is a set of items, subsequences, or substructures that occurs with a frequency no less than a user-specified threshold within a dataset.
• Historical Context: The concept was first proposed by Agrawal, Imielinski, and Swami (AIS93) in 1993, specifically focusing on frequent itemsets and association rule mining.
• Core Motivation: The primary goal is to find inherent regularities in data to answer business and scientific questions:
  • Which products are often purchased together (e.g., bread and butter)?
  • What are the subsequent purchases a customer makes after buying a PC?
  • Which DNA sequences are sensitive to a specific new drug?
  • Can web documents be automatically classified based on common patterns?
• Application Areas:
  • Market Basket Analysis: Understanding customer purchasing patterns.
  • Cross-marketing and Catalog Design: Optimizing product placement and promotions.
  • Sales Campaign Analysis: Tracking the effectiveness of marketing efforts.
  • Web Log (Clickstream) Analysis: Understanding user navigation on websites.
  • DNA Sequence Analysis: Identifying biological patterns.

Market Basket Analysis (Association Analysis)

• General Concept: This is a mathematical modeling technique based on the theory that purchasing a certain group of items makes a customer more likely to buy another specific group of items.
• Objectives:
  • Analyze customer purchasing behavior.
  • Increase sales by focusing on point-of-sale (POS) transaction data.
  • Maintain optimal inventory levels.
• Key Questions Answered:
  • Who is making the purchases?
  • What items do customers buy together?
  • In what specific order do customers purchase items?

Definitions and Key Terminology

• Transaction: A set of items, often referred to as an itemset.
• Itemset: A collection of one or more items (e.g., $\{\text{Milk, Bread, Diaper}\}$).
• k-itemset: An itemset containing exactly $k$ items.
• Support Count ($\sigma$): The frequency of occurrence of an itemset within the database. (e.g., $\sigma(\{\text{Milk, Bread, Diaper}\}) = 2$).
• Support ($s$): The fraction of total transactions that contain the itemset. It represents the probability that a transaction contains the collection of items.
  • $\text{Support} = \frac{\text{Number of transactions containing the item combination}}{\text{Total number of records}}$
  • Example: If 2 out of 5 transactions contain both Cola and Frozen Pizza, the support is $40\%$.
• Confidence ($c$): A measure of the trustworthiness of the rule or the uncertainty associated with the discovered pattern. It measures how often the consequent is true when the antecedent is true.
  • $\text{Confidence}(X \rightarrow Y) = P(Y|X) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)}$
  • Example: For the rule "If Milk, then Potato Chips," if the support for the combination is $20\%$ and the support for Milk alone is $60\%$, the confidence is $\frac{20\%}{60\%} = 33.3\%$.
• Frequent Itemset: An itemset that satisfies a user-defined minimum support threshold ($\text{min\_sup}$).
• Strong Association Rules: Rules that satisfy both a minimum support threshold and a minimum confidence threshold.

Closed Itemsets

• Definition: A frequent itemset is "closed" if it has no proper superset with the same support value. It is the largest itemset in a set of itemsets sharing the same support.
• Example Case:
  • Database transactions result in frequent itemsets: $\text{\{A\}, \{B\}, \{C\}, \{D\}, \{A, B\}, \{A, C\}, \{A, D\}, \{B, C\}, \{B, D\}, \{C, D\}, \{A, B, C\}, \{A, B, D\}, \{A, C, D\}, \{B, C, D\}}$.
  • Minimum support ($\text{minsup}$) = 3.
  • Only $\text{\{A\}, \{B\}, \{C\}, \{D\}, \{A, B\}, \{A, C\}, \{A, D\}, \{B, C\},\text{ and } \{B, D\}}$ are closed if their supersets have lower support.
• Utility: Closed itemsets provide a concise representation of the data and can be used to generate all frequent itemsets and their supports efficiently.
• Industrial Examples:
  • Retail: $\text{\{bread, milk\}, \{shirt, jeans\}, \{laptop, printer\}}$.
  • Healthcare: $\text{\{fever, cough\}, \{diabetes, heart disease\}, \{cancer, chemotherapy\}}$.

The Association Rule Mining Task

• Objective: Given a set of transactions $T$, find all rules having support $\ge \text{minsup}$ and confidence $\ge \text{minconf}$.
• Brute-Force Approach:
  • List all possible association rules.
  • Compute support and confidence for every rule.
  • Prune those failing the thresholds.
  • Problem: This is computationally expensive. For $d$ items, there are $2^d$ possible candidate itemsets.
• The Two-Step Approach:
  1. Frequent Itemset Generation: Generate all itemsets with support $\ge \text{minsup}$. This is the more computationally expensive step.
  2. Rule Generation: Generate high-confidence rules from the frequent itemsets. Each rule is a binary partitioning of a frequent itemset (e.g., for frequent itemset $\text{\{A, B, C\}}$, possible rules include $A, B \rightarrow C$, $A, C \rightarrow B$, etc.).

The Apriori Algorithm

• Basic Principle: The Apriori property states that any subset of a frequent itemset must also be frequent.
• Anti-Monotone Property: The support of an itemset never exceeds the support of its subsets. If an itemset is infrequent, all of its supersets are also infrequent and can be pruned immediately.
• Algorithm Steps:
  1. k=1: Generate frequent 1-itemsets ($L_1$).
  2. Join Step: To find $L_k$, a set of candidate k-itemsets ($C_k$) is generated by joining $L_{k-1}$ with itself.
     • Hint: Merge two frequent itemsets of size $n$ if their first $n-1$ items are identical.
  3. Prune Step: Any candidate $(k)$-itemset which has an infrequent $(k-1)$-subset is eliminated.
  4. Support Counting: Scan the database to count the support of the remaining candidates in $C_k$.
  5. Iteration: Repeat until no more frequent itemsets can be found.

Detailed Apriori Numerical Example

• Dataset (Transactions T100-T900):
  • T100: I1, I2, I5
  • T200: I2, I4
  • T300: I2, I3
  • T400: I1, I2, I4
  • T500: I1, I3
  • T600: I2, I3
  • T700: I1, I3
  • T800: I1, I2, I3, I5
  • T900: I1, I2, I3
• Parameters: Minimum support count = 2 ($22\%$); Minimum confidence = $70\%$.
• Iteration 1:
  • $C_1$: $\text{\{I1\}:6, \{I2\}:7, \{I3\}:6, \{I4\}:2, \{I5\}:2}$.
  • $L_1$: All satisfy count $\ge 2$.
• Iteration 2:
  • $C_2$ results from joining $L_1$: $\text{\{I1, I2\}, \{I1, I3\}, \{I1, I4\}, \{I1, I5\}, \text{ etc.}}$
  • Counts: $\text{\{I1, I2\}:4, \{I1, I3\}:4, \{I1, I4\}:1 (Pruned), \{I1, I5\}:2, \{I2, I3\}:4, \{I2, I4\}:2, \{I2, I5\}:2, \{I3, I4\}:0, \{I3, I5\}:1, \{I4, I5\}:0}$.
  • $L_2$: $\text{\{I1, I2\}, \{I1, I3\}, \{I1, I5\}, \{I2, I3\}, \{I2, I4\}, \{I2, I5\}}$.
• Iteration 3:
  • $C_3$ candidates: $\text{\{I1, I2, I3\}}, \text{\{I1, I2, I5\}}$.
  • Note: $\text{\{I1, I3, I5\}}$ is pruned because its subset $\text{\{I3, I5\}}$ is not in $L_2$.
  • $L_3$: $\text{\{I1, I2, I3\}:2, \{I1, I2, I5\}:2}$.
• Iteration 4:
  • Candidate $\text{\{I1, I2, I3, I5\}}$ is pruned because its subset $\text{\{I2, I3, I5\}}$ is not in $L_3$.

Improving the Efficiency of Apriori

• Hash-Based Technique: Uses a hash table to generate k-itemsets and their counts, reducing the need to search the entire itemset space.
• Transaction Reduction: Mark or remove transactions that do not contain frequent items to reduce scanning time in later iterations.
• Partitioning: Divides the database into partitions. An itemset must be frequent in at least one partition to be potentially frequent in the entire database. Requires only two database scans.
• Sampling: Searches for patterns in a random sample $S$ of the database $D$. Lowering $\text{min\_sup}$ helps avoid losing global frequent itemsets.
• Dynamic Itemset Counting: Adds new candidate itemsets at different points during a single database scan.

Frequent Pattern (FP) Growth Algorithm

• Core Concept: A divide-and-conquer strategy that avoids candidate generation. It compresses the database into a frequent-pattern tree (FP-tree) to store association information.
• The Two-Step Process:
  1. Build the FP-tree: Requires only two database passes.
  2. Extract Itemsets: Mine the tree recursively to find frequent patterns.
• Building the Tree:
  • Scan 1: Find support counts for individual items. Discard infrequent ones and sort frequent items in descending order of support.
  • Scan 2: Process each transaction by sorting its items according to the global frequency order and inserting them as a path in the FP-tree.
• FP-Tree Structure:
  • Root: Labeled as "null".
  • Nodes: Contain item-name, count (number of transactions reaching that point), and node-link (link to the next node of the same name).
  • Header Table: Lists frequent items and the head of their node-link chains.

Mining the FP-Tree

• Process:
  1. Conditional Pattern Base: For each item in the header table (starting from the bottom), traverse its node-links to find all prefix paths leading to it.
  2. Conditional FP-tree: Build a smaller FP-tree using the items in the conditional pattern base that meet the support threshold.
  3. Recursion: Repeat the process until the resulting tree is empty or contains only a single path.
• Single Path Property: If an FP-tree has one single path, all combinations of items in that path are frequent patterns.
• Example (m-conditional FP-tree): If the path is $\text{f:3, c:3, a:3}$ for item $m$, patterns generated include $\text{\{m\}, \{fm\}, \{cm\}, \{am\}, \{fcm\}, \{fam\}, \{cam\}, \{fcam\}}$.

Comparison: Apriori vs. FP Growth

Association Rule Generation & Strength Metrics

• Rule Format: If-then statements (e.g., $\text{\{Diaper\}} \rightarrow \text{\{Beer\}}$). Note: Implication means co-occurrence, not causality.
• Algorithm Step for Rules:
  • For each frequent itemset $I$, generate all non-empty subsets $s$.
  • Output rule $s \rightarrow (I - s)$ if $\frac{\text{support\_count}(I)}{\text{support\_count}(s)} \ge \text{min\_conf}$.
• Evaluation Metrics:
  • Lift: Measures how much more likely the consequent is to occur when the antecedent is present, compared to when it is not.
  • Conviction: Measures the extent to which the antecedent rules out the possibility of the consequent not occurring.

Questions & Discussion

• Q: What happens if an FP-tree contains a single path?
  • A: You can simply enumerate all combinations of its sub-paths to get all frequent patterns.
• Q: Why is descending order of frequency important in FP-trees?
  • A: It ensures that more frequent items are higher in the tree, allowing for more branch sharing and a more compact representation. If items are sorted in ascending order, the tree becomes significantly larger.
• Q: What is the complexity of rule generation?
  • A: If a frequent itemset has size $|L| = k$, there are $2^k - 2$ candidate association rules (excluding the empty set and the full set).