Association, Sequential and Pattern Mining

Introduction and Context

Association, sequential, and pattern mining are methods for discovering meaningful regularities in large collections of records. They are especially valuable when the analyst does not begin with a clearly specified dependent variable. Instead of asking whether a known predictor explains a known outcome, pattern mining asks: Which events, products, behaviours, or attributes occur together or in a meaningful order?

In retail, the records may be shopping baskets. In digital services, they may be clickstreams. In banking, they may be transaction histories. In healthcare, they may be sequences of diagnoses, treatments, and outcomes. The central challenge is to distinguish useful regularities from accidental co-occurrences. This requires formal measures, efficient algorithms, domain knowledge, validation, and responsible interpretation.

Association mining discovers co-occurrence relationships, such as customers who buy bread and cheese also frequently buy butter. Sequential mining incorporates order, such as customers who purchase a printer later purchase ink. Pattern mining is the broader field that includes these and related forms of structured discovery.

Learning Objectives

After studying this chapter, a learner should be able to:

1. Represent transactional and sequential data for mining.
2. Explain itemsets, support, confidence, lift, conviction, and related measures.
3. Generate frequent itemsets using Apriori and FP-Growth.
4. Construct and evaluate association rules.
5. Distinguish association from sequential pattern mining.
6. Apply sequence-support measures and sequential mining algorithms.
7. Assess usefulness, statistical reliability, scalability, and business relevance.
8. Identify ethical, privacy, and governance risks in pattern discovery.

1. Data Representations and Fundamental Concepts

A transaction database is a collection of transactions, each containing a set of items. Let the item universe be I = {i₁, i₂, ..., i_m}, and let a transaction database be D = {T₁, T₂, ..., T_N}, where each transaction T_j is a subset of I. A transaction normally records presence or absence, not quantity. If quantity matters, quantitative association mining or a separate preprocessing strategy is required.

An itemset is a set of one or more items. A k-itemset contains exactly k items. For example, {tea, sugar} is a 2-itemset. An itemset is frequent when its support reaches a user-defined minimum support threshold.

Support is the proportion of transactions containing an itemset X:

Here, |D| is the number of transactions and |{T ∈ D : X ⊆ T}| is the number containing X. Support lies between 0 and 1, or between 0% and 100%. It measures prevalence, not profitability, causality, or usefulness.

The support-count form is:

If the minimum support is minsup, X is frequent when σ(X) ≥ minsup. A critical property is downward closure, also called the Apriori property:

Thus, every subset of a frequent itemset must also be frequent. Equivalently, if an itemset is infrequent, all of its supersets are infrequent. This property enables pruning.

2. Association Rules and Evaluation Measures

An association rule has the form X → Y, where X and Y are disjoint itemsets. X is the antecedent or left-hand side; Y is the consequent or right-hand side. The rule does not imply causality. It states that transactions containing X tend to contain Y at a specified level of association.

The support of a rule is the support of its complete itemset:

Confidence estimates the conditional probability of Y among transactions containing X:

Confidence is directional. In general, confidence(X → Y) differs from confidence(Y → X). It is also sensitive to the baseline frequency of Y. If Y is purchased by nearly everyone, many rules ending in Y will have high confidence even if X contributes little information.

Lift compares the observed co-occurrence with the co-occurrence expected under independence:

Lift greater than 1 indicates positive association, lift equal to 1 is consistent with independence, and lift less than 1 indicates negative association. Lift is symmetric for X and Y, although the rule confidence is not.

The leverage of a rule is the difference between observed and independent co-occurrence:

Leverage is zero under independence. Unlike lift, it reflects an absolute difference in probability and tends to favour patterns with greater population impact.

Conviction is another directional measure:

For confidence less than 1, conviction greater than 1 suggests that X provides information about the absence of Y. Conviction becomes infinite when confidence is exactly 1 and σ(Y) is less than 1. It should be interpreted carefully when supports are very small.

Worked Example: Computing Rule Measures

Suppose a retailer has 1,000 transactions. Bread appears in 400, butter in 300, and both in 180.

Thus, σ(bread) = 0.40, σ(butter) = 0.30, and σ(bread ∪ butter) = 0.18. For the rule bread → butter:

The rule has 18% support, 45% confidence, lift 1.5, and leverage 0.06. The observed joint purchase rate is 6 percentage points higher than the rate expected under independence. It may be useful for promotion or shelf analysis, but it does not prove that buying bread causes buying butter.

3. Frequent Itemset Mining

Apriori Algorithm

Apriori proceeds level by level. It first finds frequent 1-itemsets, joins them to form candidate 2-itemsets, counts their supports, and repeats. Candidate generation uses the principle that a candidate can be frequent only if every immediate subset is frequent.

A simplified procedure is:

1. Scan the database to count individual items.
2. Retain items meeting minimum support.
3. Join frequent (k−1)-itemsets to form candidate k-itemsets.
4. Prune candidates with an infrequent (k−1)-subset.
5. Scan the database and count surviving candidates.
6. Repeat until no new frequent itemsets remain.

Apriori is transparent and useful for teaching and moderate data volumes. Its weaknesses are repeated database scans and potentially large candidate sets. Low minimum-support thresholds can cause severe computational growth.

FP-Growth

FP-Growth avoids explicit candidate generation. It compresses transactions into an FP-tree, a prefix structure in which common transaction prefixes share nodes. Mining proceeds recursively through conditional pattern bases and conditional FP-trees.

FP-Growth is often faster than Apriori when transactions share prefixes or the database is large. However, implementation, memory management, and interpretation can be more complex. Neither algorithm automatically determines an appropriate minimum support; that remains a modelling and business decision.

Rule Generation

Once frequent itemsets have been found, rules are generated by dividing each frequent itemset into non-empty antecedent and consequent parts. For a frequent itemset Z, every non-empty proper subset X can define a rule X → Z−X. Rules are then filtered by minimum confidence and additional criteria such as lift, leverage, novelty, or business value.

A rule-discovery workflow should separate:

• statistical prevalence: support;
• conditional reliability: confidence;
• departure from independence: lift or leverage;
• decision value: margin, actionability, timing, and cost;
• stability: replication across time, stores, or customer segments.

4. Sequential Pattern Mining

Association rules ignore order. Sequential mining represents each customer or entity as an ordered sequence of itemsets:

Each element s_t is an event or itemset, and the order of elements is meaningful. For example, ⟨{phone}, {case}, {screen_protector}⟩ represents a customer buying a phone, then a case, then a screen protector. Items in the same element occur in the same event or time period; elements occur in sequence.

A sequence A is contained in sequence B when the events of A can be matched to events of B in the same order, not necessarily contiguously. For example, ⟨{A}, {C}⟩ occurs in ⟨{A}, {B}, {C}⟩. Whether gaps are allowed is a modelling choice.

Sequence support is the proportion of sequences in the database containing the pattern:

The denominator should be defined clearly. It may be all customers, all sessions, or all eligible customers who had an opportunity to experience the pattern. Different denominators can produce different conclusions.

Sequential rules often include time constraints. A rule may be written as A → B within 30 days, or may require a minimum and maximum gap between events. Time-window choices affect support and should be justified by domain knowledge.

Sequential Mining Algorithms

GSP uses a candidate-generation approach adapted to ordered patterns. It repeatedly generates candidate sequences and prunes those whose subsequences are infrequent. It can be costly when many candidate sequences are possible.

PrefixSpan grows patterns by projecting the database according to prefixes. It generally avoids generating all candidates explicitly and can be efficient for long sequences. SPADE uses a vertical representation in which occurrence positions are stored and intersected. The choice among algorithms depends on sequence length, sparsity, temporal constraints, memory, and implementation environment.

Association Versus Sequential Mining

5. Interestingness, Statistical Reliability, and Business Value

No single metric identifies a useful pattern. High confidence may be caused by a popular consequent. High lift may be unstable when support is tiny. High support may describe an obvious pattern with little strategic value.

Analysts should consider the following:

• Minimum support should reflect both computational feasibility and business reach.
• Confidence should be compared with the consequent baseline support.
• Lift should be accompanied by support or counts.
• Leverage can reveal practical population impact.
• Statistical significance tests, confidence intervals, or resampling can assess uncertainty.
• Multiple-testing correction is important because thousands or millions of candidate rules are examined.
• Temporal validation can test whether a pattern persists in later periods.
• Holdout data can reduce overfitting.
• Domain experts should assess novelty, plausibility, and actionability.

For example, a rule with support 0.001 and lift 12 may represent only a handful of customers. It can be interesting for niche personalization but unsafe as a general merchandising conclusion. Conversely, a rule with lift 1.05 and support 0.35 may have modest association but substantial operational value.

Association patterns are descriptive. Confounding variables, promotions, store layout, seasonality, and customer selection can generate observed relationships. Causal claims require experimental or quasi-experimental designs. If a recommendation is deployed, an A/B test can assess incremental revenue, conversion, retention, or customer experience.

6. Applied Case: Illustrative Retail Replenishment System

Background

This fictional case concerns MarketWay, a supermarket chain with transaction histories, loyalty identifiers, timestamps, store locations, product categories, prices, and promotions. Management wants to improve cross-selling without increasing irrelevant recommendations.

Problem

The initial proposal is to recommend every product that appears in a high-confidence rule. Analysts recognize that this could produce excessive recommendations and could confuse association with causation. They therefore design a staged analysis.

Analysis

The team cleans returns, excludes cancelled orders, standardizes product identifiers, and separates regular purchases from promotional bundles. It creates weekly customer baskets and defines an eligibility rule: a customer must have purchased in the relevant department during the observation period.

Apriori is first run with a minimum support of 2% and minimum confidence of 30%. Rules are ranked using support, confidence, lift, leverage, margin, and stability across stores. A rule involving specialty coffee and filters has support 4%, confidence 52%, and lift 2.1. A second rule has confidence 88% but lift 1.02 because the consequent is purchased by almost every eligible customer. The second rule is deprioritized despite its higher confidence.

Sequential analysis then examines purchases within 60 days. The pattern ⟨{coffee_machine}, {coffee_pods}⟩ is frequent among first-time machine purchasers. The team tests whether the pattern is merely caused by a launch promotion. After controlling operationally by comparing promoted and non-promoted periods, the association remains but is weaker.

Approach and Solution

MarketWay deploys rules only when they satisfy four conditions: adequate support, lift above a selected baseline, stability across validation periods, and a positive expected business case. Recommendations are capped at two per customer session. The system uses a holdout group and measures incremental conversion rather than clicks alone.

Outcome

The pilot produces a moderate increase in attachment sales and no material increase in unsubscribes. Several rules fail in the holdout period, demonstrating that historical discovery alone is insufficient. The strongest rules are incorporated into replenishment reminders, while weak rules are retained for monitoring rather than automatic action.

Learning Points

The case illustrates that preprocessing, denominator choice, temporal validation, business constraints, and experimentation are as important as algorithm selection. It also shows why high confidence cannot be used as the sole decision criterion.

7. Applications Across Organisations

In retail, patterns support basket analysis, bundle design, shelf planning, coupon targeting, and replenishment. In e-commerce, sequential patterns support next-best-action recommendations, journey analysis, and churn interventions. In manufacturing, event sequences can reveal combinations of sensor alerts preceding equipment failure. In telecommunications, usage sequences can indicate upgrade opportunities or service problems. In healthcare, coded treatment sequences may support pathway analysis, although clinical validation and privacy safeguards are essential.

In operations, patterns can identify recurring combinations of delays, machine states, or service tickets. In customer analytics, they can distinguish onboarding paths associated with retention from paths associated with abandonment. In fraud detection, unusual sequential combinations can be used as risk signals, but a pattern is not proof of wrongdoing.

8. Implementation and Best Practices

A professional implementation should follow these steps:

1. Define the decision and the unit of analysis.
2. Specify event, transaction, customer, and time-window definitions.
3. Clean identifiers, duplicates, returns, cancellations, and missing timestamps.
4. Select support thresholds using both data scale and business reach.
5. Mine patterns with an algorithm appropriate to data volume and structure.
6. Calculate multiple interestingness measures.
7. Remove redundant, trivial, unstable, or misleading rules.
8. Validate with temporal, geographic, or customer holdouts.
9. Consult domain specialists.
10. Test actions experimentally before large-scale deployment.
11. Monitor drift, performance, fairness, and customer response.

Rule redundancy is common. If a rule X → Y has nearly the same meaning as a more specific rule X ∪ Z → Y, a condensed rule set may be preferable. Closed and maximal frequent itemsets can reduce the number of patterns presented to users, although they do not eliminate the need for interpretation.

Scalability may require distributed processing, compact data structures, sampling, or incremental mining. Streaming environments require attention to changing support, concept drift, and window definitions. A rule that was valid last year may become invalid after a pricing change, product substitution, or change in customer behaviour.

9. Ethical, Privacy, and Governance Issues

Pattern mining can expose sensitive behaviour even when individual names are removed. Purchase histories, medical sequences, location traces, and browsing events may be personal data. Organisations should apply purpose limitation, data minimisation, access control, retention limits, and appropriate consent or legal bases.

Sensitive attributes should not be used casually to create discriminatory targeting. A seemingly neutral rule may act as a proxy for protected characteristics. Analysts should conduct fairness assessments, document feature and threshold choices, and provide governance review for high-impact uses.

Re-identification risk can arise when rare combinations are published. Reports should suppress or aggregate small counts where appropriate. Individuals should not be subjected to consequential decisions solely because they match an opaque pattern. Explainability, audit logs, human review, and appeal mechanisms are particularly important in financial, employment, insurance, education, and healthcare settings.

10. Contemporary Developments

Modern pattern mining increasingly combines classical frequent-pattern methods with graph mining, embeddings, recommender systems, process mining, and real-time event processing. Neural sequence models can predict the next event, but they may be less interpretable than explicit sequential rules. A practical architecture often uses a predictive model for ranking and pattern mining for explanation, diagnostics, or governance.

Causal discovery and uplift modelling address a different question: which intervention changes an outcome? They should not be confused with association mining. Privacy-preserving analytics, federated learning, and secure multiparty computation are emerging approaches for reducing the need to centralise sensitive behavioural data, though they introduce computational and governance challenges.

Chapter Summary

Association mining discovers items that occur together, while sequential mining discovers ordered event patterns. Transactions are represented as sets; sequences preserve temporal order. Support measures prevalence, confidence measures conditional reliability, lift compares observed co-occurrence with independence, leverage measures absolute departure from independence, and conviction provides a directional measure related to rule violations. Apriori uses downward closure for candidate pruning, whereas FP-Growth compresses transactions in an FP-tree. GSP, PrefixSpan, and SPADE support sequential discovery through different representations and search strategies.

Useful pattern discovery requires more than high metric values. Analysts must consider support counts, baseline prevalence, uncertainty, multiple testing, temporal stability, causality, business value, and ethical risk. A reliable workflow combines careful data preparation, algorithmic mining, domain interpretation, holdout validation, experimentation, governance, and ongoing monitoring.

Key Terms

Association rule: A directional statement relating an antecedent itemset to a consequent itemset.

Antecedent: The left-hand side of an association rule.

Consequent: The right-hand side of an association rule.

Transaction: A set of items observed in one event or basket.

Itemset: A collection of one or more items.

Frequent itemset: An itemset whose support reaches the minimum-support threshold.

Support: The proportion of records containing an itemset or pattern.

Confidence: The conditional proportion of consequent occurrences among antecedent occurrences.

Lift: The ratio of observed joint support to support expected under independence.

Leverage: The difference between observed and independent joint support.

Conviction: A directional measure comparing consequent absence with rule failure.

Apriori property: The principle that every subset of a frequent itemset is frequent.

FP-tree: A compressed prefix structure used by FP-Growth.

Sequential pattern: An ordered set of events recurring across entity histories.

Sequence support: The proportion of entity sequences containing a specified pattern.

Temporal window: The permitted time interval for events in a sequential pattern.

Closed itemset: A frequent itemset with no proper superset having the same support.

Pattern redundancy: Repetition or near-repetition among discovered rules.

Actionability: The extent to which a pattern supports a feasible decision or intervention.

Concept drift: Change in data-generating behaviour over time.

Review Questions

Short Answer Questions

1. Define support and explain why it is useful in frequent-itemset mining.
2. Why can confidence be misleading when the consequent is very common?
3. State the interpretation of lift equal to 1.
4. Distinguish a transaction from a sequence.
5. Name two differences between Apriori and FP-Growth.

Long Answer Questions

1. Explain the Apriori property and show how it reduces candidate search.
2. Compare support, confidence, lift, leverage, and conviction as rule-evaluation measures.
3. Describe the complete workflow for deploying association rules in a retail organisation.
4. Explain how sequential pattern mining differs from ordinary association mining, including temporal constraints.
5. Discuss privacy, fairness, and governance risks in customer pattern mining.

Analytical / Application Questions

1. A rule has support 0.12, antecedent support 0.30, and consequent support 0.40. Calculate its confidence and lift, and interpret both values.
2. Design a sequential-mining study for predicting customer churn. Specify the unit of analysis, event representation, time window, validation strategy, and business action.
3. A rule has high lift but very low support, while another has modest lift and very high support. Explain which additional evidence you would request before selecting either rule for deployment.

Multiple Choice Questions with Answers

Question 1

Which measure compares observed co-occurrence with co-occurrence expected under independence?

A. Support

B. Confidence

C. Lift

D. Count

Correct Answer: C. Lift

Question 2

A transaction database contains 1,000 transactions, and 250 contain itemset X. What is the support of X?

A. 0.025

B. 0.25

C. 2.5

D. 250

Correct Answer: B. 0.25

Question 3

If support(X ∪ Y) = 0.18 and support(X) = 0.40, what is confidence(X → Y)?

A. 0.22

B. 0.45

C. 0.58

D. 2.22

Correct Answer: B. 0.45

Question 4

What does lift equal to 1 indicate for a rule, subject to sampling variation?

A. Perfect positive association

B. Perfect negative association

C. Consistency with independence

D. That the rule has 100% confidence

Correct Answer: C. Consistency with independence

Question 5

Which property allows Apriori to prune a candidate when one of its subsets is infrequent?

A. Stationarity

B. Downward closure

C. Normality

D. Randomization

Correct Answer: B. Downward closure

Question 6

Which algorithm uses a compressed prefix tree and generally avoids explicit candidate generation?

A. Apriori

B. GSP

C. FP-Growth

D. Linear regression

Correct Answer: C. FP-Growth

Question 7

What is the defining feature of sequential pattern mining?

A. It ignores timestamps completely

B. It preserves event order

C. It requires numerical target variables

D. It only analyses single-item transactions

Correct Answer: B. It preserves event order

Question 8

A rule has support 0.12, antecedent support 0.30, and consequent support 0.40. What is its lift?

A. 0.10

B. 0.40

C. 1.00

D. 1.20

Correct Answer: D. 1.20

Question 9

Why should a high-confidence rule be assessed against consequent support?

A. Confidence is always symmetric

B. A common consequent can produce high confidence without strong association

C. Support cannot be calculated for consequents

D. Lift is defined as confidence squared

Correct Answer: B. A common consequent can produce high confidence without strong association

Question 10

Which validation approach is especially appropriate for detecting whether a discovered pattern persists in future business conditions?

A. Temporal holdout validation

B. Removing all timestamps

C. Increasing confidence mechanically

D. Using only the training data

Correct Answer: A. Temporal holdout validation