Unit 3: Mining frequent patterns

Frequent pattern mining discovers itemsets, subsequences and substructures that appear in a dataset at least as often as a user-set threshold, and it is the foundation on which association rules, correlation analysis and pattern-based classifiers are built. The techniques below all rest on counting how often things co-occur in a set of transactions and reasoning about what those counts mean.

Defining terms and conventions used throughout:

• Itemset: a set of one or more items, e.g. {milk, bread}; a k-itemset contains k items.
• Transaction database (D): a set of transactions, each a subset of the item universe I; |D| is the transaction count.
• Support count (σ): number of transactions containing an itemset X.
• Support: support(X) = σ(X) / |D| — the fraction of transactions holding X.
• Frequent itemset: an itemset whose support ≥ min_sup (minimum support threshold).
• Apriori property: every non-empty subset of a frequent itemset is itself frequent; equivalently, any superset of an infrequent itemset is infrequent (used for pruning).

II. Association Rule Mining

Finding "if–then" regularities among items.

An association rule is an implication X ⇒ Y where X, Y ⊆ I and X ∩ Y = ∅; mining seeks rules that are both frequent and reliable.

A. Introduction to Association Rule Mining

The task is to extract all rules exceeding a minimum support and confidence from a transaction database.

• Two-step process: first find all frequent itemsets (support ≥ min_sup), then generate strong rules from them (confidence ≥ min_conf). Step one dominates the cost.
• Confidence: conditional probability the rule holds.
  
  TEXT

    confidence(X ⇒ Y) = support(X ∪ Y) / support(X) = P(Y | X)

• The Apriori algorithm: iteratively builds candidate k-itemsets by joining frequent (k−1)-itemsets, then prunes any candidate with an infrequent subset, then scans D to count support.
  • Join step: L{k-1} ⋈ L{k-1} produces candidate set C_k.
  • Prune step: discard candidates using the Apriori property before the costly database scan.
• FP-Growth alternative: compresses D into an FP-tree and mines patterns by recursive conditional trees, avoiding candidate generation and repeated scans.
• Worked example: with |D| = 5, suppose {milk, bread} appears in 3 transactions and {milk} in 4. Then support = 3/5 = 0.6 and confidence(milk ⇒ bread) = 0.6 / 0.8 = 0.75.

B. associations and correlations

Support–confidence alone can flag misleading rules, so correlation measures test whether the antecedent and consequent are genuinely dependent.

• The trap of confidence: a rule can have high confidence merely because Y is very common, not because X influences Y.
• Lift: compares observed co-occurrence with what independence predicts.
  
  TEXT

    lift(X ⇒ Y) = confidence(X ⇒ Y) / support(Y) = P(X ∪ Y) / (P(X)·P(Y))

  • lift = 1: X and Y independent — no real association.
  • lift > 1: positively correlated (occur together more than by chance).
  • lift < 1: negatively correlated.
• Interpretation example: if confidence(coffee ⇒ tea) = 0.20 but support(tea) = 0.25, then lift = 0.8 < 1, meaning buying coffee actually lowers the chance of buying tea despite a plausible-looking rule.

C. Mining Correlation Patterns

Correlation mining generalises rule mining by ranking patterns on statistical dependence rather than frequency alone.

• χ² (chi-square) test: measures deviation of observed counts from expected counts under independence in a contingency table.
  
  TEXT

    χ² = Σ (observed − expected)² / expected

  
  A large χ² with an appropriate degrees-of-freedom threshold rejects independence.
• all_confidence: a downward-closed measure robust to skew.
  
  TEXT

    all_conf(X) = support(X) / max(support(item) for item in X)

• cosine measure: cosine(A,B) = support(A∪B) / √(support(A)·support(B)), ranging 0–1 and unaffected by the number of null (co-absence) transactions.
• Null-invariance: cosine and all_confidence are null-invariant — their value does not change with transactions containing neither item — making them preferable to lift and χ² for sparse, large databases where co-absences dominate.

III. Classification

Predicting a discrete class label from labelled training data.

Classification is a supervised learning task: a model is learned from training tuples with known labels, then applied to assign labels to unseen data.

A. Introduction to Classification

The goal is to build a function mapping attribute vectors to one of a finite set of predefined classes.

• Two phases:
  • Learning (training): a classifier is induced from a labelled dataset — attributes (a1…an) plus class label y.
  • Prediction (testing): the model labels new tuples; accuracy is estimated on a held-out test set.
• Common model families: decision trees (recursive attribute splits using information gain), Bayesian classifiers (P(class | data) ∝ P(data | class)·P(class)), rule-based classifiers, and support vector machines.
• Classification vs. numeric prediction: classification outputs categorical labels; regression outputs continuous values.
• Overfitting: a model that memorises training noise generalises poorly — controlled by pruning, regularisation and validation.

B. classification

Classification differs sharply from association mining even though both find patterns.

1. Association mining (unsupervised): discovers all co-occurrence patterns among items with no target attribute; output is a set of rules ranked by support/confidence.
2. Classification (supervised): targets one designated class attribute and optimises predictive accuracy on it; output is a single model.

• Shared machinery: frequent patterns useful in association mining can serve as high-quality features for a classifier, which motivates the next section.
• Descriptive vs. predictive: association is descriptive (summarising data), classification is predictive (generalising to new tuples).

C. Frequent Pattern-Based Classification Methods

These methods use frequent itemsets as features or rules, exploiting the fact that combinations of attributes are often more discriminative than single attributes.

• Rationale: individual low-level features may be weak, but a frequent conjunction of them can strongly indicate a class.
• Associative classification: mines class association rules (CARs) of the form pattern ⇒ class_label, then classifies using them.
  • CBA (Classification Based on Associations): mines CARs meeting min_sup and min_conf, sorts them by confidence then support, and builds an ordered rule list; a new tuple is labelled by the first matching rule.
  • CMAR (Classification based on Multiple Association Rules): uses multiple matching rules and a weighted χ² to decide the label, improving robustness over single-rule voting.
  • CPAR (Classification based on Predictive Association Rules): generates rules greedily in a FOIL-like manner, reducing the huge rule set of CBA/CMAR.
• Discriminative frequent pattern approach: select frequent patterns with high information gain or Fisher score, transform each tuple into a feature vector over these patterns, and feed it to a standard classifier (e.g. SVM).
• Trade-off: frequent patterns boost accuracy on complex data but explode combinatorially; feature selection on discriminative power (not raw frequency) is essential.

D. Pattern Evaluation in Classification (Evaluation Metrics: Precision, Recall, F1-Score)

Because accuracy alone is misleading on imbalanced classes, precision, recall and their harmonic mean quantify a classifier's quality per class.

• Confusion matrix: the basis of all three metrics, counting outcomes for a positive class.
  • TP (true positive): positive tuples correctly labelled positive.
  • FP (false positive): negative tuples wrongly labelled positive.
  • FN (false negative): positive tuples wrongly labelled negative.
  • TN (true negative): negative tuples correctly labelled negative.
• Precision: exactness — of all predicted positives, how many are correct.
  
  TEXT

    Precision = TP / (TP + FP)

• Recall (sensitivity): completeness — of all actual positives, how many were found.
  
  TEXT

    Recall = TP / (TP + FN)

• F1-Score: harmonic mean balancing precision and recall; penalises a low value in either.
  
  TEXT

    F1 = 2 · (Precision · Recall) / (Precision + Recall)

• Why the harmonic mean: it stays low if either metric is low, unlike the arithmetic mean, which forces a genuine trade-off between exactness and completeness.
• Worked example: a classifier yields TP = 40, FP = 10, FN = 20. Then Precision = 40/50 = 0.80, Recall = 40/60 ≈ 0.667, and F1 = 2·(0.80·0.667)/(0.80+0.667) ≈ 0.727.
• Precision–recall trade-off: raising the decision threshold usually increases precision but lowers recall; the right balance depends on cost — recall matters most in disease screening, precision in spam filtering.