Data Science & Machine Learning — Article 31

Association Rules: A Comprehensive Guide

Explore detailed Association Rules

Data Science & Machine Learning — Article 31

Introduction

Every method so far has worked on a rectangular table of numbers. Transaction data is not that.

A supermarket basket contains three items out of forty thousand, the next contains a different three, and there is no target variable anywhere.

Association rule mining answers a different shape of question: which things co-occur more often than chance would suggest? The framework is simple enough to compute by hand, and it contains a trap that catches almost everyone.

Table of Contents

• Introduction
• Table of Contents
• What is Association Rules
• Core Components of Association Rules
• Mathematical Foundation
• Types of Association Rules
• Evaluation Metrics
• Selecting Evaluation Metrics
• Assumptions and Practical Considerations

What is Association Rules

Definition

Association rule mining discovers implications of the form A ⇒ B in transactional data, where A and B are disjoint sets of items, and quantifies each rule’s usefulness with measures of how often it applies and how much better than chance it performs.

Why it is needed

• Transaction data is sparse, variable length, and unlabelled, so the supervised and clustering frameworks do not apply.
• Co-occurrence patterns drive concrete decisions: shelf placement, cross-selling, bundling.
• Rules are directly interpretable, unlike the dense component mixtures of Articles 28 to 31.
• The itemset search space is 2ⁿ, so the field needed and produced genuinely clever algorithms.

Where it is used

Real world analogy

A shopkeeper who has watched the till for years notices things. Nappies and beer often leave together on Friday evenings. Bread and milk go together constantly, but so does bread with almost everything, so that pairing tells them nothing useful. Association rule mining is that intuition made arithmetic, and the second observation is exactly the trap Section 5.6 formalizes.

Key characteristics

• Unsupervised. There is no target variable, only co-occurrence.
• Interpretable. A rule states itself in plain terms.
• Combinatorial. 2ⁿ — 1 possible item sets, so pruning is essential rather than an optimization.
• Correlational, not causal. A rule says two things co-occur, never that one causes the other.
• Threshold driven. Results depend entirely on the minimum support and confidence chosen.

How this differs from everything before it

Core Components of Association Rules

Items and Transactions

• Purpose: the raw data structure.
• Function: an item is an atomic element, a transaction is a set of items.
• Relationship: sets, not counts. Standard association rule mining ignores quantity, so buying three loaves is the same as buying one.
• Practical example: transaction bread, milk, diaper.

Itemset

• Purpose: any collection of items whose co-occurrence is of interest.
• Function: a k-itemset contains k items.
• Relationship: the search space is all 2ⁿ — 1 non-empty subsets, which is why pruning matters.
• Practical example: the 2-itemset diaper, beer.

Support

• Purpose: measures how often an itemset appears.
• Function: the fraction of transactions containing it.
• Relationship: the pruning quantity, because it satisfies the downward closure property derived in Section 5.4.
• Practical example: support 0.4 meaning the itemset appears in 4 of 10 transactions.

Confidence

• Purpose: measures how reliably the antecedent predicts the consequent.
• Function: the conditional probability P(B∣ A), estimated as supp(A∪ B)/supp(A).
• Relationship: the metric that misleads. Section 5.6 shows why it must never be used alone.
• Practical example: confidence 0.80 that sounds strong and means nothing.

Lift

• Purpose: measures association strength relative to chance.
• Function: confidence divided by the consequent’s own support.
• Relationship: the correction for confidence’s blind spot. Lift 1 means independence.
• Practical example: lift 1.1429 meaning a 14 percent improvement over baseline.

Minimum Thresholds

• Purpose: control how many rules survive.
• Function: min_support prunes the itemset search, min_confidence filters rules.
• Relationship: the results depend entirely on these, and there is no principled way to set them. They are business decisions.
• Practical example: min_support = 0.3 reducing 63 candidate itemsets to 12 frequent ones.

Downward Closure

• Purpose: makes the search tractable.
• Function: every subset of a frequent itemset is frequent, so a set containing an infrequent subset cannot be frequent.
• Relationship: the single property that turns an intractable search into a practical one. Section 5.5 measures a 74.6 percent saving on a tiny example.

• Practical example: if beer is infrequent, no itemset containing beer needs checking.

Mathematical Foundation

Variables

Formula

Support, the fraction of transactions containing an itemset:

Confidence, the conditional probability of the consequent:

Lift, confidence relative to the consequent’s baseline:

Leverage, the absolute difference from independence:

Conviction, the ratio of expected to observed rule violations:

Downward closure, the pruning principle:

Mathematical Intuition

Five ideas define the framework:

• Support is a joint probability, confidence a conditional one. Support measures how often the pattern occurs at all; confidence measures its reliability when the antecedent is present.

Both are needed because a perfectly reliable rule covering 0.1 percent of transactions is usually not actionable.

• Lift is the independence test. Under independence supp(A∪ B) = supp(A)supp(B), which makes lift exactly 1. So lift measures departure from independence, and it is symmetric: lift(A⇒ B) = lift(B⇒ A).
• Confidence has a systematic blind spot. It never looks at supp(B). A rule predicting a very common consequent inherits high confidence automatically, whether or not the antecedent carries any information. Section 5.6 measures this.
• Downward closure runs in both directions. Positively, every subset of a frequent set is frequent. Contrapositively, any set containing an infrequent subset is infrequent, and that form is what lets an algorithm skip enormous swathes of the search space without counting them.
• The search is exponential without pruning. 2ⁿ — 1 itemsets for n items: at n = 40 that is over 1⁰¹². Downward closure is not an optimization, it is what makes the problem solvable at all.

Step by Step Derivation

Two results matter: downward closure, and lift’s relationship to independence.

Proving downward closure

Step 1: Take itemsets X ⊆ Y and consider any transaction T containing Y.

Step 2: Set containment is transitive, so Y ⊆ T and X ⊆ Y together give X ⊆ T.

Step 3: Therefore every transaction containing Y also contains X.

Step 4: Taking cardinalities and dividing by N:

Step 5: Take the contrapositive with respect to a threshold s. If supp(X) < s for some subset X ⊆ Y, then supp(Y) ≤ supp(X) < s, so Y is infrequent too.

This is the Apriori pruning rule. An itemset can be discarded without ever counting it, provided any one of its subsets is already known to be infrequent.

Step 6: Note the practical consequence. Candidate generation proceeds level by level. At level k, only sets whose every (k-1)-subset is frequent need be considered. Section 5.5 Step 8 measures the saving.

Lift and independence

Step 7: If A and B are statistically independent, the joint probability factorizes.

Step 8: Substituting into the lift definition:

Step 9: So lift has an interpretable scale with a meaningful reference point:

Step 10: Confidence has no such reference point. Rearranging the lift definition:

Read this carefully. Confidence is the product of the genuine association strength and the consequent’s own prevalence. A rule can achieve high confidence purely because supp(B) is large, with lift exactly 1 and therefore zero informational content. That is the trap, and Section 5.6 exhibits it exactly.

The Confidence Trap

Step 10 of the derivation predicted that confidence can be high with lift exactly 1. Here is that case, in this dataset.

The rule beer⇒milk.

Eighty percent confidence. Presented alone, that reads as a strong and actionable finding.

Lift is exactly 1 and leverage is exactly 0. Beer and milk are statistically independent in this data.

The rule carries zero information. Its 80 percent confidence is entirely explained by milk appearing in 80 percent of all transactions: predicting milk is right 80 percent of the time no matter what you condition on.

This is Step 10 made concrete, since conf = lift×supp(B) = 1.0 × 0.8 = 0.8.

Worse: high confidence can accompany negative association.

The rule beer⇒bread:

Sixty percent confidence sounds reasonable, but lift 0.75 means buying beer makes bread less likely than the 80 percent baseline. Acting on this rule as though it were positive would be actively wrong.

The full picture for consequent = bread, ranked by lift:

Confidence and lift rank these in the same order here, but disagree completely on sign. Four of the five rules have confidence at or above 0.5 and lift below 1, meaning every one of them is a negative association dressed as a plausible prediction.

Get Arko Sengupta’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The practical rule: filter by support and confidence to control volume, then rank and interpret by lift. A rule with lift at or below 1 is not a finding regardless of its confidence.

Interpretation, and What These Metrics Cannot Tell You

Three limits are worth stating explicitly.

Rules are not causal. diaper⇒beer having lift 1.14 says the two co-occur more than chance. It does not say buying nappies causes buying beer, nor the reverse.

A confounder, such as being a parent shopping on a Friday evening, explains both. Every rule in this framework is a statement about association only.

Lift is symmetric, confidence is not. Since

lift cannot distinguish direction. Confidence can: conf(diaper⇒beer) = 0.5714 while conf(beer⇒diaper) = 0.4/0.5 = 0.8000. If direction matters operationally, confidence carries that information and lift does not, which is one legitimate use for it.

Thresholds determine the output. There is no principled way to choose min_support. Too high and rare but valuable patterns vanish; too low and the rule count explodes combinatorially.

The choice is a business decision about what volume of pattern is worth acting on, and it should be reported alongside the results.

Types of Association Rules

Apriori

• Definition: the original level-wise algorithm, generating and testing candidates by size.
• Working principle: at each level, joins frequent (k-1)-itemsets, prunes any candidate with an infrequent subset, then scans the database to count survivors.
• Advantages: simple, easy to reason about, and the pruning is provably correct by Step 5.
• Disadvantages: requires a database scan per level, and candidate generation can still explode on dense data.
• Applications: the standard teaching algorithm and adequate for moderate data.

FP-Growth

• Definition: Frequent Pattern Growth, which avoids candidate generation entirely.
• Working principle: compresses the database into an FP-tree, a prefix tree of frequency-ordered transactions, then mines recursively from conditional sub-trees.
• Advantages: only two database scans regardless of itemset size, and typically an order of magnitude faster than Apriori.
• Disadvantages: the tree must fit in memory, and the implementation is considerably more involved.
• Applications: the practical default for large transaction databases.
• Covered in: Article 35.

Eclat

• Definition: Equivalence Class Transformation, using a vertical data layout.
• Working principle: stores a transaction-ID list per item, then computes itemset support by intersecting those lists.
• Advantages: no repeated database scans, and intersection is fast on sparse data.
• Disadvantages: TID lists can consume substantial memory for frequent items.
• Applications: sparse data with many items.
• Covered in: Article 34.

Closed and Maximal Itemsets

• Definition: compressed representations of the frequent itemset collection.
• Working principle: an itemset is closed if no superset has the same support, and maximal if no superset is frequent at all.
• Advantages: dramatically fewer itemsets reported. Closed itemsets lose no support information; maximal ones are the most compact.
• Disadvantages: maximal itemsets discard the support of subsets, so rule confidence cannot be recovered from them alone.
• Applications: dense data where the frequent itemset count is unmanageable.

Sequential Pattern Mining

• Definition: extends the framework to ordered transactions.
• Working principle: algorithms such as GSP or PrefixSpan mine subsequences rather than subsets, respecting order.
• Advantages: captures temporal structure that set-based mining discards entirely.
• Disadvantages: a much larger search space, since order multiplies the possibilities.
• Applications: clickstream analysis, treatment pathways, purchase sequences.

Multi-Level and Quantitative Rules

• Definition: extensions handling item hierarchies and numeric attributes.
• Working principle: multi-level mining uses a taxonomy such as “dairy” containing “milk”. Quantitative mining discretizes numeric attributes into ranges before treating them as items.
• Advantages: finds patterns at the right granularity, and extends the method to non-transactional data.
• Disadvantages: discretization boundaries are arbitrary and strongly affect the results.
• Applications: retail with product taxonomies, and mining rules from tabular data.

Evaluation Metrics

Association rules have no held-out score in the usual sense. Evaluation is a matter of choosing metrics that do not mislead.

Support

• Interpretation: how often the pattern occurs, hence how much of the business it touches.
• When to use: always, as the first filter. A rule covering 0.01 percent of transactions is rarely actionable however reliable it is.
• Limitations: says nothing about strength. High support can simply mean both items are individually common.

Confidence

• Interpretation: the estimated P(B∣ A).
• When to use: to control rule volume, and when direction matters, since it is asymmetric where lift is not.
• Limitations: must never be used alone. Section 5.6 exhibited a rule with confidence 0.8000 and lift exactly 1.0000, carrying zero information. Confidence factorizes as lift×supp(B), so a common consequent inflates it for free.

Lift

• Interpretation: how much more often A and B co-occur than independence predicts. Exactly 1 under independence.
• When to use: the primary ranking metric.
• Limitations: symmetric, so it cannot distinguish A⇒ B from B⇒ A. It is also unstable for very low support itemsets, where a single transaction can move it substantially.

Leverage

• Interpretation: the absolute excess co-occurrence over independence, on the support scale. Zero under independence.
• When to use: when the volume of the effect matters, not just its ratio. Lift 5 on 0.1 percent support is a smaller opportunity than lift 1.2 on 40 percent.
• Limitations: bounded by support, so it inherently favours frequent itemsets.

Leverage and lift answer different questions. Section 5.6’s independent rule had leverage exactly 0.0000, agreeing with lift 1.0000, which is a useful cross-check.

Conviction

• Interpretation: how much more often the rule would be violated under independence than it actually is. Infinite for a rule with no exceptions.
• When to use: when you care about violations rather than confirmations, and it is asymmetric unlike lift.
• Limitations: undefined at confidence 1, and less intuitive to explain.

Rule Count and Redundancy

• Interpretation: how many rules survived, and how many are trivial variants of each other.
• When to use: assessing whether the thresholds produced a usable result.
• Limitations: no automatic notion of redundancy. A rule A,B⇒C adds nothing over A⇒C if their lifts are equal.

Thousands of rules is a failure of the analysis, not a rich result. Raise the thresholds, or filter to closed itemsets.

Statistical Significance

• Interpretation: whether an observed lift could plausibly arise by chance.
• When to use: when acting on a rule carries real cost, especially at low support.
• Limitations: mining thousands of rules creates a severe multiple-comparisons problem. With 10,000 rules tested at α = 0.05, roughly 500 will appear significant by chance alone.

A Fisher exact test on the 2×2 contingency table gives a p-value per rule, but it must be corrected for multiplicity. This is the same concern raised for stepwise regression in Article 8 Section 9.5, and it is equally serious here.

Selecting Evaluation Metrics

Business considerations

• Report all three of support, confidence, and lift. Confidence alone is the single most common way association rule results mislead, and Section 5.6 quantifies exactly how.
• State the thresholds used. Results are not reproducible or comparable without them, since the rule set is entirely determined by min_support and min_confidence.
• Be explicit that rules are associations. Acting on diaper⇒beer by moving shelves is reasonable; claiming nappies cause beer purchases is not supported by anything in this framework.
• A high-lift rule on tiny support may be a genuine niche opportunity or pure noise. Check the absolute transaction count, not just the fraction.

Dataset characteristics

• Very common items generate spurious high-confidence rules, exactly as bread and milk did at support 0.8.
• Very rare items produce unstable lift, since a single transaction can move the ratio a long way.
• Dense data explodes the frequent itemset count, so closed or maximal representations become necessary.
• Item granularity matters enormously. Mining at SKU level finds almost nothing; mining at category level may be too coarse to act on.

Common mistakes

• Ranking or filtering by confidence alone. Section 5.6's rule had confidence 0.8000 and lift exactly 1.0000.
• Treating high confidence as evidence of positive association, when four of five bread rules had confidence above 0.5 and lift below 1.
• Reading a rule causally.
• Not reporting the thresholds.
• Setting min_support so low that the rule count explodes, then reporting the top few by confidence.
• Ignoring the multiple-comparisons problem when thousands of rules are tested.
• Reporting A⇒ B and B⇒ A as two findings when lift is identical for both.
• Comparing lift across datasets with different item prevalences.

Assumptions and Practical Considerations

Data Is Genuinely Transactional

• Requirement: observations are sets of items, with no meaningful order or quantity.
• Why: standard mining treats transactions as sets, so it discards both order and multiplicity.
• Check: ask whether order or quantity matters for the decision you plan to make.
• Fix: sequential pattern mining if order matters; quantitative rules if amounts do.

Item Granularity Is Appropriate

• Requirement: items defined at a level where co-occurrence is both detectable and actionable.
• Why: at SKU level nearly every itemset falls below any reasonable support. At the level of "food" everything co-occurs trivially.
• Check: inspect the single-item support distribution. If almost all items sit below min_support, the granularity is too fine.
• Fix: roll up to a category taxonomy, or use multi-level mining.

Thresholds Are Chosen Deliberately

• Requirement: min_support and min_confidence justified by business need.
• Why: the entire rule set is determined by them, and no principled default exists.
• Check: vary them and observe how the rule count changes.
• Violation sign: thresholds chosen to produce a pleasing number of rules after the fact.
• Fix: decide in advance what coverage makes a pattern worth acting on, and report the thresholds.

Enough Transactions for Stable Estimates

• Requirement: support estimates based on enough transactions to be reliable.
• Why: support is a proportion, so its standard error is roughly √(p(1-p)/N). At N = 100 a support of 0.05 rests on five transactions.
• Guideline: require a minimum absolute count, not just a fraction. Thirty transactions is a reasonable floor.
• Fix: raise min_support, or collect more data.

The Search Is Computationally Feasible

• Requirement: the itemset search completes.
• Why: the space is 2ⁿ - 1, and downward closure helps only when the data is sparse enough for pruning to bite.
• Check: count items above min_support. If that number is large and the data dense, expect an explosion.
• Fix: FP-Growth instead of Apriori, a higher min_support, or closed itemsets.

Results Will Not Be Read Causally

• Requirement: an explicit commitment to interpreting rules as associations.
• Why: nothing in support, confidence, or lift distinguishes causation from confounding.
• Fix: state it alongside the results, and design an experiment if a causal claim is actually needed.

Multiple Comparisons Are Acknowledged

• Requirement: awareness that mining many rules guarantees some spurious ones.
• Why: testing 10,000 rules at α = 0.05 yields roughly 500 false positives by chance.