Unit 3: Mining frequent patterns - Subjective Questions

Association Rule Mining is a data mining technique used to discover interesting relationships, patterns, associations, or correlations among a set of items in large transactional or relational databases. It is widely used in market basket analysis.

An association rule is an implication of the form , where and are disjoint itemsets ().

Key Metrics:

• Support: Measures how frequently an itemset appears in the dataset.
  

• Confidence: Measures the reliability of the inference made by the rule.
  

• Lift: Measures how much more often and occur together than expected if they were statistically independent.
  

Interpretation of Lift:

• : and are independent.
• : and are positively correlated.
• : and are negatively correlated.

The Apriori Algorithm is a classic algorithm proposed by Agrawal and Srikant for mining frequent itemsets and generating association rules. It uses a level-wise, iterative (breadth-first) search approach.

Apriori Property (Anti-Monotone Property):

All non-empty subsets of a frequent itemset must also be frequent. Conversely, if an itemset is infrequent, all its supersets are also infrequent.

This property is used to prune the search space, reducing computation significantly.

Two Main Steps:

1. Join Step: To find frequent -itemsets (), a set of candidate -itemsets () is generated by joining with itself.

2. Prune Step: Candidates in whose -subsets are not in are removed. The support of remaining candidates is counted by scanning the database, and those meeting the minimum support threshold form .

Algorithm Flow:

• Find frequent 1-itemsets ().
• Iteratively generate from , prune, and count support to get .
• Repeat until no more frequent itemsets can be found.

Limitations:

• Requires multiple database scans.
• Generates a huge number of candidate sets.

Associations vs Correlations:

Why strong association rules can mislead:

A rule with high support and confidence may still be misleading because confidence ignores the base support of the consequent.

• Example: Consider a rule with 80% confidence. If 90% of all customers buy milk anyway, then buying coffee actually decreases the likelihood of buying milk.
• The Lift here would be , indicating a negative correlation.

Thus, correlation analysis (using measures like lift or ) is needed to filter out uninteresting or deceptive rules that pass the support-confidence framework.

Correlation Pattern Mining extends association rule mining by identifying itemsets that are statistically correlated, going beyond mere co-occurrence to determine whether items are positively, negatively, or independently related.

1. Lift:

• independent
• positively correlated
• negatively correlated

2. Chi-Square () Test:
Used to test statistical independence of two variables using a contingency table.

where the Expected count for a cell is:

Interpretation:

• If : variables are independent.
• A large value indicates correlation. Comparing observed vs expected shows whether the correlation is positive or negative.

Example: In a table of game vs video purchases, if the observed count of buying both is greater than the expected count, they are positively correlated; a significant value confirms the dependency.

Null Invariance: Measures like lift and are affected by null transactions (transactions containing neither item), whereas measures like cosine and all_confidence are null-invariant.

Classification is a supervised learning technique in data mining used to predict categorical (discrete, unordered) class labels for new data instances, based on a model built from a training dataset with known labels.

Two-Step Process:

Step 1 — Learning (Training/Model Construction):

• A classification algorithm analyzes a training set of tuples with known class labels.
• The algorithm learns a classifier/model, which may be expressed as classification rules, decision trees, or mathematical formulae.
• This is the learning phase.

Step 2 — Classification (Model Usage):

• The learned model is used to classify new, unseen data.
• First, the model's accuracy is estimated using a test set (data not used in training).
• If accuracy is acceptable, the model is applied to future unknown data tuples.

Diagram Description:

New Data --> [Classifier] --> Predicted Class Label

Examples of Classifiers: Decision Trees, Naive Bayes, Support Vector Machines, k-Nearest Neighbors, Neural Networks.

Classification vs Prediction (Regression):

Supervised vs Unsupervised Learning:

• Supervised Learning:

  • Training data includes labeled outcomes (known class labels).
  • Model learns the mapping from inputs to known outputs.
  • Examples: Classification, Regression.

• Unsupervised Learning:

  • Training data is unlabeled; class labels are unknown.
  • The algorithm discovers hidden structure/groupings on its own.
  • Examples: Clustering, Association Rule Mining.

Key Difference: Supervised learning requires a teacher (labeled data), while unsupervised learning finds patterns without predefined labels.

Frequent Pattern-Based Classification is an approach that uses frequent patterns (frequent itemsets or subsequences) as features to build a classification model. It bridges frequent pattern mining and classification.

Motivation:

• Single features may not be discriminative enough.
• Combinations of features (patterns) often carry more discriminative power for classification.

General Framework:

1. Feature Generation: Mine frequent patterns from the training data that satisfy a minimum support threshold.

2. Feature Selection: Select the most discriminative frequent patterns using measures like Information Gain, Fisher Score, or Gini Index. This removes redundant/non-discriminative patterns.

3. Model Learning: The selected frequent patterns are used as features to train a classifier (e.g., SVM, decision tree).

Popular Methods:

• Associative Classification (CBA - Classification Based on Associations): Generates class association rules (CARs) of form , then builds a classifier from high-confidence rules.
• CMAR (Classification based on Multiple Association Rules): Uses multiple rules and weighted for prediction.
• CPAR (Classification based on Predictive Association Rules): Uses a greedy approach for rule generation.

Advantages:

• Captures complex feature interactions.
• Often achieves higher accuracy than single-feature methods.

Disadvantage:

• Can generate a huge number of patterns; requires effective feature selection.

A Confusion Matrix is a table used to evaluate the performance of a classification model by comparing predicted labels against actual labels. For a binary classifier, it is a matrix.

Structure:

Terms:

• True Positive (TP): Instances that are actually positive and correctly predicted as positive.
• True Negative (TN): Instances that are actually negative and correctly predicted as negative.
• False Positive (FP): Instances that are actually negative but incorrectly predicted as positive (Type I error).
• False Negative (FN): Instances that are actually positive but incorrectly predicted as negative (Type II error).

Usage:
The confusion matrix forms the basis for computing evaluation metrics such as:

It provides more insight than accuracy alone, especially for imbalanced datasets.

These are key evaluation metrics for classification, derived from the confusion matrix.

1. Precision (Positive Predictive Value):
Measures the proportion of predicted positives that are actually correct.

• Important when: the cost of a false positive is high (e.g., spam detection — marking a valid email as spam is costly).

2. Recall (Sensitivity / True Positive Rate):
Measures the proportion of actual positives that are correctly identified.

• Important when: the cost of a false negative is high (e.g., disease detection — missing a sick patient is dangerous).

3. F1-Score:
The harmonic mean of precision and recall, balancing both.

• The harmonic mean is used because it penalizes extreme values; F1 is high only when both precision and recall are high.
• Important when: you need a balance between precision and recall, especially with imbalanced classes.

Trade-off: Increasing precision often reduces recall and vice versa. The F1-score helps find the optimal balance.

Given values:

• , , ,

1. Accuracy:

Accuracy = 85%

2. Precision:

Precision = 80%

3. Recall:

Recall ≈ 88.9%

4. F1-Score:


F1-Score ≈ 84.2%

Summary: The model performs well overall with balanced precision and recall, reflected in a strong F1-score.

The FP-Growth (Frequent Pattern Growth) algorithm mines frequent itemsets without candidate generation, addressing the main bottleneck of Apriori. It uses a compact data structure called the FP-Tree.

Steps:

1. First DB Scan: Count the support of each item and discard infrequent items. Sort frequent items in descending order of support (F-list).

2. Second DB Scan — Build FP-Tree:

   • Each transaction's frequent items (in F-list order) are inserted as a path in the tree.
   • Shared prefixes are merged, and node counts are incremented.
   • A header table links all occurrences of each item.

3. Mining via FP-Growth:

   • For each frequent item (bottom-up), construct its conditional pattern base (prefix paths).
   • Build a conditional FP-Tree and recursively mine it to generate frequent patterns.

Improvements over Apriori:

Advantages:

• Compresses the database into a compact tree.
• Avoids costly candidate generation and repeated scans.

Disadvantage:

• FP-Tree may not fit in memory for very large, sparse datasets.

1. Frequent Itemset:
An itemset whose support is greater than or equal to a specified minimum support threshold.

2. Closed Frequent Itemset:
A frequent itemset is closed if there exists no proper superset (with ) that has the same support as .

• Closed itemsets provide a lossless compact representation (support of all itemsets is recoverable).

3. Maximal Frequent Itemset:
A frequent itemset is maximal if none of its proper supersets are frequent.

• Maximal itemsets provide the most compact but lossy representation (exact support of sub-itemsets is lost).

Relationship:

Example: Suppose min support = 2. Consider itemsets:

• with support 4
• with support 4
• with support 2

Here:

• is not closed because superset has same support (4).
• is closed (support 4 differs from 's support 2).
• is maximal (no frequent superset exists).

Benefit: Closed and maximal itemsets drastically reduce the number of patterns to store while retaining useful information.

Associative Classification integrates association rule mining with classification. It mines a special subset of association rules called Class Association Rules (CARs), whose consequent is restricted to a class label.

A CAR has the form:

CBA (Classification Based on Associations):

Proposed by Liu et al., CBA has two main parts:

1. CBA-RG (Rule Generator):

• Uses an Apriori-like approach to find all ruleitems (itemset + class label) that satisfy minimum support.
• From frequent ruleitems, generate CARs meeting a minimum confidence threshold.

2. CBA-CB (Classifier Builder):

• Rank the CARs by (a) confidence, (b) support, (c) generation order.
• Select a subset of high-ranked rules that together cover the training data (following a greedy covering strategy).
• Include a default class for tuples matching no rule.

Classification of a New Tuple:

• The first rule (highest priority) whose antecedent matches the tuple is fired, assigning its class label.
• If no rule matches, the default class is assigned.

Advantages:

• Rules are human-interpretable.
• Often more accurate than traditional classifiers like C4.5.

Limitations:

• Generates large numbers of rules.
• Sensitive to support/confidence thresholds.

Support and confidence alone can produce misleading rules. Additional interestingness measures help evaluate the strength of correlation. Many are null-invariant (unaffected by transactions containing neither item).

1. All-Confidence:

Represents the minimum confidence of the two rules and .

2. Cosine:

Geometric mean of the two conditional probabilities; ranges between 0 and 1.

3. Kulczynski (Kulc):

Average of the two conditional probabilities and .

Null-Invariance: All-confidence, cosine, Kulczynski, and max-confidence are null-invariant — their values do not change with the number of null transactions. In contrast, lift and are not null-invariant.

Imbalance Ratio (IR): Often used with Kulczynski to assess whether a pattern's items are balanced:

Recommendation: Kulczynski combined with Imbalance Ratio gives a robust view of pattern interestingness.

Class Imbalance Problem:
Occurs when the classes in a dataset are not represented equally — one class (the majority) has far more instances than another (the minority). Common in fraud detection, disease diagnosis, and rare-event prediction.

Why Accuracy is Unreliable:

Consider a dataset with 95% negative and 5% positive instances.

• A naive classifier that always predicts negative achieves 95% accuracy but never identifies any positive case.
• High accuracy masks poor performance on the important minority class.
  
  Accuracy is dominated by the majority class and hides errors on the minority class.

Preferred Metrics:

• Precision & Recall: Focus on the positive (minority) class.
• F1-Score: Harmonic mean balancing precision and recall.
• Sensitivity & Specificity:
  
• ROC Curve & AUC: Evaluate performance across thresholds.

Techniques to Handle Imbalance:

• Oversampling the minority class (e.g., SMOTE).
• Undersampling the majority class.
• Cost-sensitive learning (assign higher misclassification cost to minority class).

Conclusion: For imbalanced datasets, use precision, recall, F1-score, and AUC rather than raw accuracy.

Market Basket Analysis (MBA) is a key application of association rule mining that analyzes customer purchasing behavior by discovering associations between items that are frequently bought together in transactions.

How it Works:

• Each customer transaction is a basket of items.
• Association rule mining discovers rules like:
  
  meaning 70% of customers who buy bread and butter also buy milk.

Classic Example:
The well-known (often cited) rule suggested that customers buying diapers often also bought beer, prompting stores to place these items strategically.

Benefits for Retailers:

• Product Placement: Place associated items near each other to boost sales.
• Cross-Selling & Promotions: Recommend complementary products.
• Inventory Management: Stock frequently co-purchased items together.
• Catalog Design & Store Layout: Organize based on buying patterns.
• Targeted Marketing: Offer bundle discounts on associated items.
• Recommendation Systems: Suggest "Customers who bought X also bought Y."

Conclusion: MBA transforms raw transaction data into actionable business intelligence, improving sales and customer satisfaction.

1. Single-Dimensional Association Rules:

• Involve a single predicate/dimension, repeated multiple times.
• Typically used in market basket analysis where all items belong to one attribute (buys).
• Example:
  

2. Multi-Dimensional Association Rules:

• Involve two or more different predicates/dimensions (attributes).
• Common in relational databases with multiple attributes.
• Example:
  
• Types: Inter-dimensional (no repeated predicate) and Hybrid-dimensional (repeated predicates allowed).

3. Multi-Level (Multiple-Level) Association Rules:

• Involve items at different levels of abstraction within a concept hierarchy.
• Rules can be mined at higher and lower levels.
• Example: Using hierarchy: food → dairy → milk → skim milk
  
  

Support Strategies for Multi-Level Rules:

• Uniform support: Same minimum support at all levels.
• Reduced support: Lower minimum support at lower (more specific) levels.

These classifications allow flexible and richer pattern discovery across dimensions and abstraction levels.

Cross-Validation is a resampling technique used to evaluate a classification model's generalization performance on unseen data, reducing dependence on a single train-test split.

k-Fold Cross-Validation:

1. The dataset is randomly partitioned into equal-sized subsets (folds).
2. The model is trained and tested times.
3. In each iteration :
   • Fold is used as the test set.
   • The remaining folds form the training set.
4. The performance metric (e.g., accuracy) is computed for each fold.
5. The overall estimate is the average over all folds:
   

Common Choice: (10-fold cross-validation) is widely used.

Variants:

• Stratified k-fold: Maintains class proportions in each fold (good for imbalanced data).
• Leave-One-Out (LOOCV): (number of instances); each instance is a test set once.

Advantages:

• Uses all data for both training and testing, giving a more reliable estimate.
• Reduces variance compared to a single holdout split.
• Helps detect overfitting.

Disadvantage:

• Computationally expensive (model trained times).

Discriminative Frequent Pattern-Based Classification selects only those frequent patterns that best discriminate between classes, using them as features to build an accurate classifier. Not all frequent patterns are useful — many are redundant or non-discriminative.

Framework:

1. Mine frequent patterns satisfying minimum support.
2. Evaluate discriminative power of each pattern using a selection measure.
3. Select top discriminative patterns as features.
4. Train a classifier (e.g., SVM) using the selected features.

Feature Selection Measures:

1. Information Gain (IG):
Measures the reduction in entropy (uncertainty) about the class label after knowing the presence of a pattern.

where is the entropy of the class distribution.

• Higher IG ⇒ more discriminative pattern.

2. Fisher Score:
Measures how well a feature separates classes based on the ratio of between-class variance to within-class variance.

where are the mean and variance of the feature in class , is the overall mean, and is the class size.

• Higher Fisher score ⇒ better class separation.

Benefits:

• Reduces the huge number of frequent patterns to a compact, discriminative set.
• Improves classification accuracy and efficiency.

Example Method: DDPMine efficiently mines discriminative patterns directly, avoiding generation of the complete pattern set.

Given: 4 transactions, minimum support = 50% (i.e., item must appear in at least transactions).

Step 1 — Count support of 1-itemsets:

Frequent 1-itemsets (): (D is pruned).

Step 2 — Count support of candidate 2-itemsets:

Frequent 2-itemsets (): .

Step 3 — Candidate 3-itemsets:
requires to be frequent, but it is not ⇒ pruned. No frequent 3-itemsets.

All Frequent Itemsets:

Step 4 — Confidence of rule :

Confidence() ≈ 66.7%

Interpretation: 66.7% of transactions containing also contain .