Association, Frequent Pattern and Sequential Mining

Introduction and Context

Data mining seeks useful, previously unknown patterns in large datasets. Association and frequent-pattern mining are especially important when observations consist of groups of items, events, or behaviours. A supermarket transaction, for example, may contain bread, milk, and butter. A web session may contain a sequence of page views. A medical record may contain diagnoses and treatments occurring over time.

This chapter develops three related approaches:

• Association-rule mining, which discovers relationships such as “customers who buy bread and butter often buy jam.”
• Frequent-pattern mining, which identifies itemsets or structures that occur frequently.
• Sequential-pattern mining, which discovers ordered patterns such as “customers who buy a laptop later buy a laptop bag.”

These methods support market-basket analysis, recommendation systems, cross-selling, inventory planning, clickstream analysis, fraud detection, and customer-journey analysis. Their usefulness depends not only on statistical frequency but also on business relevance, actionability, novelty, and ethical use.

Learning Objectives

By the end of this chapter, students should be able to:

1. Explain itemsets, transactions, support, confidence, lift, and related measures.

2. Apply the Apriori algorithm to a small transaction database.

3. Explain how FP-Growth reduces the candidate-generation burden of Apriori.

4. Distinguish association rules from sequential patterns.

5. Calculate and interpret support, confidence, and lift.

6. Evaluate whether a discovered pattern is useful rather than merely frequent.

7. Apply mining methods to market-basket and recommendation problems.

8. Recognize computational, statistical, ethical, and operational limitations.

1. Foundations of Frequent-Pattern Mining

Transactions, items, and itemsets

Let a transaction database be denoted by \(D\), containing \(N\) transactions. Each transaction is a set of items drawn from an item universe \(I\). For example:

• \(T_1 = \{bread, milk\}\)
• \(T_2 = \{bread, butter, jam\}\)
• \(T_3 = \{milk, butter\}\)

An itemset is a set of one or more items. An itemset containing \(k\) items is called a \(k\)-itemset. Thus, \(\{bread, butter\}\) is a 2-itemset.

A pattern is frequent when it satisfies a minimum support threshold, written \(minsup\). Support may be reported as a count or a proportion. The proportional support of itemset \(X\) is:

\[

support(X)=\frac{|\{T\in D:X\subseteq T\}|}{N}

\]

where \(|\cdot|\) denotes the number of transactions satisfying the condition. Support measures how common a pattern is in the database; it does not measure causation.

Association rules

An association rule has the form:

\[

X \Rightarrow Y

\]

where \(X\) and \(Y\) are itemsets, \(X\cap Y=\varnothing\), and \(X\) is the antecedent while \(Y\) is the consequent. The rule means that transactions containing \(X\) tend also to contain \(Y\). It is a probabilistic association, not a logical implication.

Three central measures are used.

Support of a rule:

\[

support(X\Rightarrow Y)=support(X\cup Y)

\]

This is the proportion of all transactions containing both sides.

Confidence:

\[

confidence(X\Rightarrow Y)=\frac{support(X\cup Y)}{support(X)}

\]

Confidence estimates the conditional probability \(P(Y\mid X)\), provided support is calculated over the same transaction population.

Lift:

\[

lift(X\Rightarrow Y)=\frac{confidence(X\Rightarrow Y)}{support(Y)}

=\frac{support(X\cup Y)}{support(X)support(Y)}

\]

Lift compares the observed co-occurrence with what would be expected if \(X\) and \(Y\) were statistically independent.

• Lift greater than 1 indicates positive association.
• Lift equal to 1 indicates independence under this measure.
• Lift less than 1 indicates negative association.

Lift does not prove causality. It may also be unstable when the consequent is very rare.

Other useful measures include leverage,

\[

leverage(X\Rightarrow Y)=support(X\cup Y)-support(X)support(Y),

\]

which gives the absolute difference from independence, and conviction,

\[

conviction(X\Rightarrow Y)=\frac{1-support(Y)}{1-confidence(X\Rightarrow Y)},

\]

when confidence is less than 1. Leverage is often easier to interpret in terms of transaction proportion, whereas lift expresses a relative comparison.

2. Worked Example: Measuring an Association Rule

Consider five transactions:

| Transaction | Items |

|---|---|

| T1 | bread, milk |

| T2 | bread, butter, jam |

| T3 | bread, milk, butter |

| T4 | milk, butter |

| T5 | bread, butter |

Consider the rule \(bread\Rightarrow butter\).

Bread occurs in T1, T2, T3, and T5: support(bread) = 4/5 = 0.80.

Butter occurs in T2, T3, T4, and T5: support(butter) = 4/5 = 0.80.

Both occur in T2, T3, and T5: support(bread, butter) = 3/5 = 0.60.

Therefore:

\[

confidence(bread\Rightarrow butter)=\frac{0.60}{0.80}=0.75

\]

and

\[

lift=\frac{0.75}{0.80}=0.9375.

\]

The rule has 60% support and 75% confidence, but lift below 1. Although bread buyers frequently buy butter, butter is already common in the database. Relative to independence, bread and butter occur together slightly less often than expected. A retailer should therefore avoid interpreting high confidence alone as evidence of a particularly strong association.

3. The Apriori Algorithm

Core principle

Apriori is a level-wise algorithm for finding frequent itemsets. Its efficiency depends on the Apriori property:

> Every non-empty subset of a frequent itemset must also be frequent.

Equivalently, if an itemset is infrequent, every larger itemset containing it must be infrequent. This is an anti-monotonic property and permits pruning.

For example, if \(\{A,C\}\) fails the minimum-support threshold, then \(\{A,C,D\}\) cannot be frequent.

Algorithmic stages

1. Count each individual item and retain frequent 1-itemsets, \(L_1\).

2. Join frequent \((k-1)\)-itemsets to create candidate \(k\)-itemsets, \(C_k\).

3. Remove candidates having an infrequent \((k-1)\)-subset.

4. Scan the database and count surviving candidates.

5. Retain candidates meeting \(minsup\) as \(L_k\).

6. Repeat until no new frequent itemsets remain.

7. Generate rules from frequent itemsets and filter them using confidence, lift, and business criteria.

Small Apriori calculation

Using the five transactions above, suppose \(minsup=0.60\). The item supports are:

• bread: 4/5 = 0.80
• milk: 3/5 = 0.60
• butter: 4/5 = 0.80
• jam: 1/5 = 0.20

Thus jam is removed. Frequent 2-itemsets include:

• {bread, milk}: 2/5 = 0.40, not frequent
• {bread, butter}: 3/5 = 0.60, frequent
• {milk, butter}: 2/5 = 0.40, not frequent

Since only {bread, butter} is frequent among the tested pairs, no 3-itemset containing an infrequent pair can be frequent. The algorithm terminates for this example.

Strengths and weaknesses

Apriori is conceptually clear and easy to implement. It is useful for teaching, small datasets, and settings where transparent candidate counts are valuable. Its main weakness is computational cost. It may require many database scans and may generate a very large number of candidates when the minimum support is low or the dataset contains many moderately frequent items.

4. FP-Growth

FP-Growth, or Frequent Pattern Growth, avoids explicit candidate generation. It compresses the transaction database into an FP-tree and mines the tree recursively.

Construction

The typical process is:

1. Scan the database and count item frequencies.

2. Remove items below minimum support.

3. Sort the remaining items in each transaction by descending global frequency.

4. Insert the ordered transactions into a prefix tree.

5. Maintain links between identical items in the tree through a header table.

6. Recursively construct conditional pattern bases and conditional FP-trees.

Shared prefixes are represented once, so a database with repeated combinations may be compressed substantially.

Comparison with Apriori

Apriori generates and tests candidate itemsets. FP-Growth generally reduces scans and candidate explosion, particularly for dense data or low support thresholds. However, FP-Growth may require more complex memory structures and can be less intuitive to implement manually. Neither algorithm automatically determines the right minimum support or identifies whether a rule is commercially useful.

A practical implementation may use Apriori for small exploratory datasets and FP-Growth for larger transaction collections. Distributed platforms and specialised libraries can further improve performance, but data preparation and rule evaluation remain essential.

5. Rule Generation and Pattern Evaluation

A frequent itemset can produce multiple rules. For a frequent itemset \(\{A,B,C\}\), possible rules include \(A\Rightarrow B,C\), \(A,B\Rightarrow C\), and \(A,C\Rightarrow B\), subject to non-empty antecedent and consequent sets.

Confidence is directional: \(A\Rightarrow B\) can have a different confidence from \(B\Rightarrow A\). Lift is also directional in interpretation when the antecedent and consequent have different business roles, although the numerical lift formula is symmetric for two itemsets.

A useful evaluation framework considers four dimensions:

1. Statistical strength: support, confidence, lift, leverage, or significance testing.

2. Business value: margin, incremental revenue, retention, or reduced cost.

3. Actionability: whether a decision or intervention can be taken.

4. Stability and validity: whether the pattern persists across time, locations, and validation samples.

A pattern with high confidence but low lift may simply reflect a popular product. A pattern with high lift but support of 0.01% may be too rare to support a reliable campaign. Multiple testing is another concern: searching thousands of candidate rules increases the chance of apparently strong patterns arising by chance. Hold-out validation, temporal validation, false-discovery controls, and domain review are therefore valuable.

6. Sequential Pattern Mining

Association mining treats a transaction as an unordered set. Sequential mining incorporates order and, often, time gaps.

A sequence is an ordered list of itemsets, for example:

\[

\langle \{laptop\},\{laptop\ bag, mouse\},\{warranty\}\rangle.

\]

A sequence \(S\) supports a sequential pattern \(P\) if \(P\) is a subsequence of \(S\), preserving order but not necessarily requiring adjacent events. The support of a sequential pattern is the proportion of sequences containing it at least once. A minimum gap, maximum gap, time window, or event duration may be imposed depending on the application.

For example, the pattern \(\langle A,B\rangle\) differs from the itemset \(\{A,B\}\): the former means A occurs before B; the latter ignores order.

Sequential algorithms

GSP (Generalized Sequential Pattern) uses a level-wise candidate-generation approach similar to Apriori. It creates candidate sequences, counts them, and prunes candidates whose subsequences are infrequent.

PrefixSpan projects the database according to observed prefixes and recursively mines projected databases. It usually avoids generating a large global candidate set and is widely used for sequential pattern discovery.

SPADE represents sequences using vertical id-lists, allowing efficient intersections of sequence identifiers and positions in suitable datasets.

Sequential mining is useful for customer journeys, purchase paths, treatment histories, equipment failures, and online navigation. It can also support next-event recommendation, although prediction requires additional modelling and evaluation beyond pattern discovery.

7. Applied Case: Illustrative Online Retail Scenario

Background

The fictional retailer Northstar Home sells appliances, accessories, and installation services through a website. The company wishes to improve recommendations without recommending products merely because they are popular.

Problem

The retailer has order histories, timestamps, product categories, prices, discounts, and customer segments. It wants to identify:

• products frequently purchased together;
• products purchased after an initial order;
• recommendations that increase useful basket value without encouraging unsuitable or excessive consumption.

Analysis

The data team first defines a transaction as one completed order and removes cancelled orders and test transactions. It distinguishes products from services and separates promotional bundles from ordinary purchases. For association mining, it sets an initial minimum support of 0.5%, then examines rules with confidence above 20% and lift above 1.2. These thresholds are screening values, not universal standards.

For sequential mining, customer orders are sorted by timestamp. A maximum inter-order gap of 90 days is selected for the first analysis because recommendations beyond that period may reflect a different purchasing cycle. The team mines patterns such as:

\[

\langle coffee\ machine\rangle \Rightarrow \langle coffee\ pods\rangle.

\]

It then compares support and lift across customer segments and validates patterns on a later month.

Approach and solution

FP-Growth identifies frequent product combinations. A rule is retained for testing only when it has adequate support, positive lift, and a plausible commercial action. Sequential patterns are mined with PrefixSpan. Candidate recommendations are filtered by stock availability, compatibility, customer consent, and product safety constraints.

A recommendation experiment uses a control group. The evaluation measures incremental click-through rate, conversion, margin, return rate, and customer complaints rather than relying only on confidence. A product that is often purchased with an incompatible accessory is excluded even if its statistical association is high.

Outcome

The retailer finds that some high-confidence rules add little value because the consequent is a widely purchased product. More useful rules have moderate confidence but strong lift and adequate margin. Sequential analysis reveals that installation service is often purchased shortly after large appliances, supporting a time-limited recommendation. The later-period validation shows that several seasonal rules weaken, so they are activated only during relevant periods.

Learning points

1. Correct transaction and sequence definitions strongly affect results.

2. Lift and support should be interpreted together.

3. Association is not causation; experiments are needed to estimate incremental impact.

4. Operational constraints such as inventory and compatibility are part of mining deployment.

5. Patterns should be monitored because consumer behaviour, prices, and catalogues change.

8. Practical Implementation Workflow

A reliable project normally follows these stages:

1. Define the decision problem. Specify what action a pattern will support.

2. Prepare the data. Resolve product identifiers, duplicates, refunds, missing timestamps, and customer or session boundaries.

3. Choose the unit of analysis. This may be order, visit, customer, account, machine, or treatment episode.

4. Set thresholds deliberately. Consider database size, cost of false discoveries, and business capacity.

5. Mine patterns. Use Apriori, FP-Growth, or a sequential method suited to the data.

6. Rank and filter. Combine statistical measures with domain constraints.

7. Validate. Use hold-out periods, cross-segment checks, and, where possible, controlled experiments.

8. Deploy responsibly. Integrate rules into recommendation, merchandising, or alerting systems.

9. Monitor drift. Recalculate measures as catalogue, prices, seasons, and customer behaviour change.

Sparse high-dimensional data may benefit from compact representations and distributed processing. However, parallelisation does not solve poor definitions, leakage, biased samples, or inappropriate interpretation.

9. Limitations, Ethics, and Governance

Statistical and computational limitations

Frequent-pattern mining can produce an overwhelming number of rules. Low support thresholds increase computational cost and may produce unreliable patterns. High thresholds can hide niche but valuable products. Confidence is affected by consequent popularity, while lift can be exaggerated for rare events. Correlation does not establish causation, and historical data may reflect earlier recommendation policies rather than natural customer preferences.

Privacy and fairness

Transaction and clickstream data may reveal sensitive characteristics, health conditions, financial circumstances, or household behaviour. Organisations should collect and use data under applicable privacy law, provide appropriate notices, restrict access, and apply retention and security controls. Personalisation should not infer or exploit sensitive attributes without a lawful and ethically justified basis.

Rules can also create unfair outcomes. A promotion based on historical purchases may exclude new customers or reinforce socioeconomic segmentation. Recommendation systems should be audited for disparate effects, proxy discrimination, manipulation, and excessive targeting. Human oversight is particularly important in healthcare, finance, employment, and other high-impact domains.

Best practices

• Treat rules as evidence for investigation, not automatic truth.
• Report support counts as well as percentages.
• Use time-aware validation to avoid future-information leakage.
• Compare rules with popularity and randomised baselines.
• Record threshold choices, data versions, and exclusions.
• Prefer interpretable metrics and explanations for consequential recommendations.
• Monitor business and social outcomes after deployment.

10. Contemporary Developments

Modern systems increasingly combine frequent-pattern mining with embeddings, graph models, and neural recommenders. Pattern mining remains valuable because it provides interpretable co-occurrence and sequence explanations. Hybrid systems may use mined rules as features, candidate generators, or safety constraints for a machine-learning recommender.

Streaming and incremental algorithms update patterns as new transactions arrive. Differential privacy and federated analytics aim to reduce exposure of individual records, although privacy guarantees can reduce utility and require careful parameter selection. Temporal, utility-based, high-utility, and contrast sequential mining extend classical methods by considering time, profit, group differences, or resource constraints. These extensions should be selected because they answer a defined decision problem, not simply because they are technically advanced.

Chapter Summary

Association mining discovers relationships among items, while frequent-pattern mining identifies structures that occur above a support threshold. Support measures prevalence, confidence estimates the conditional occurrence of a consequent given an antecedent, and lift compares observed co-occurrence with independence. Apriori exploits the anti-monotonicity of support to prune candidate itemsets; FP-Growth compresses transactions in an FP-tree and mines conditional structures without extensive candidate generation. Sequential mining adds order and time, using methods such as GSP, PrefixSpan, and SPADE. Effective applications require careful data definitions, threshold selection, validation, business evaluation, privacy protection, and monitoring. A statistically strong rule is not automatically useful, causal, fair, or safe.

Key Terms

Item: A single product, event, or attribute recorded in a transaction.

Transaction: An unordered collection of items associated with one observation or event boundary.

Itemset: A set of one or more items.

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

Association rule: A directional relationship written as antecedent implies consequent.

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

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

Support: The proportion or count of transactions containing a pattern.

Confidence: The proportion of antecedent transactions that also contain the consequent.

Lift: The ratio of observed confidence to consequent support.

Leverage: The difference between observed joint support and expected support under independence.

Apriori property: Every non-empty subset of a frequent itemset must be frequent.

Candidate itemset: An itemset generated for support counting before pruning.

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

Sequential pattern: An ordered pattern occurring in a sequence database.

Subsequence: A sequence contained in another sequence while preserving order.

PrefixSpan: A projected-database algorithm for sequential pattern mining.

Market-basket analysis: Mining product co-occurrence in customer transactions.

Pattern drift: Change in pattern frequency or strength over time.

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

Review Questions

Short Answer Questions

1. Define support and explain what it measures.

2. What is the difference between an itemset and a sequential pattern?

3. State the Apriori property.

4. Interpret a lift value of 1.5.

5. Why can high confidence be misleading when the consequent is very popular?

Long Answer Questions

1. Explain the Apriori algorithm, including candidate generation, pruning, and termination.

2. Compare Apriori and FP-Growth in terms of representation, computational cost, and implementation complexity.

3. Explain support, confidence, lift, and leverage, including the assumptions behind their interpretation.

4. Describe a complete workflow for applying association mining to an online retailer.

5. Discuss privacy, fairness, causality, and validation issues in recommendation systems based on mined patterns.

Analytical / Application Questions

1. Given a transaction database and a specified minimum support, calculate frequent itemsets using Apriori and generate two valid association rules. Report support, confidence, and lift.

2. A rule has 80% confidence, but its consequent appears in 78% of all transactions. Analyse whether the rule is likely to be useful and identify additional evidence required.

3. Design a sequential-mining study for a streaming service that wants to recommend a next action after a user watches a programme. Specify the sequence boundary, time window, support threshold strategy, validation method, and ethical safeguards.

Multiple Choice Questions with Answers

Question 1

Which measure compares the observed co-occurrence of two itemsets with the co-occurrence expected under independence?

A. Support

B. Confidence

C. Lift

D. Transaction count

Correct Answer: C. Lift

Question 2

The Apriori property states that:

A. Every frequent itemset has exactly two items

B. Every non-empty subset of a frequent itemset is frequent

C. All rules must have confidence above 50%

D. Items must occur in chronological order

Correct Answer: B. Every non-empty subset of a frequent itemset is frequent

Question 3

If support(X) = 0.40 and support(X and Y) = 0.20, what is confidence(X implies Y)?

A. 0.08

B. 0.20

C. 0.50

D. 0.60

Correct Answer: C. 0.50

Question 4

If confidence(X implies Y) is 0.60 and support(Y) is 0.30, the lift is:

A. 0.18

B. 0.30

C. 2.00

D. 2.30

Correct Answer: C. 2.00

Question 5

What is a principal advantage of FP-Growth over basic Apriori?

A. It proves causality

B. It avoids explicit candidate generation through an FP-tree

C. It requires no minimum-support threshold

D. It ignores item frequency

Correct Answer: B. It avoids explicit candidate generation through an FP-tree

Question 6

Which statement best distinguishes a sequential pattern from an itemset?

A. A sequential pattern preserves event order

B. An itemset always contains one item

C. A sequential pattern cannot contain time information

D. An itemset requires a confidence value

Correct Answer: A. A sequential pattern preserves event order

Question 7

Which algorithm uses projected databases to mine sequential patterns?

A. PrefixSpan

B. FP-Growth

C. K-means

D. Naive Bayes

Correct Answer: A. PrefixSpan

Question 8

A lift value below 1 generally indicates that the antecedent and consequent:

A. Have perfect positive dependence

B. Occur together more often than expected

C. Have negative association relative to independence

D. Have identical support

Correct Answer: C. Have negative association relative to independence

Question 9

Why should an association rule be validated on a later time period?

A. To guarantee that it is causal

B. To detect whether it remains stable and avoids time-related overfitting

C. To remove the need for support calculations

D. To make every rule frequent

Correct Answer: B. To detect whether it remains stable and avoids time-related overfitting

Question 10

Which is an appropriate ethical practice when deploying personalised recommendations?

A. Use sensitive inferences without governance if lift is high

B. Ignore customers who have little historical data

C. Audit for privacy, unfairness, and harmful targeting

D. Treat every discovered association as a fact

Correct Answer: C. Audit for privacy, unfairness, and harmful targeting