Association rule learning

On this page 7

Association rule learning is an unsupervised machine learning method that discovers if-then relationships between items that frequently appear together in a dataset, expressed as rules such as {bread, butter} → {milk}. Each rule is judged by support, confidence and lift, which measure how common, how reliable and how surprising it is.

The technique became widely known through market basket analysis in retail during the 1990s, when Rakesh Agrawal and colleagues introduced the Apriori algorithm. It is now used wherever data can be framed as sets of co-occurring items, from web clickstreams to medical diagnoses.

How association rules are mined

Association rule mining runs in two stages: first find all frequent itemsets, then derive rules from them. The input is a collection of transactions, each a set of items, for example the products in one shopping receipt.

In the first stage, the algorithm counts how often each combination of items appears and keeps only those whose frequency exceeds a minimum support threshold. In the second stage, each frequent itemset is split into an antecedent (the left side) and a consequent (the right side), and only rules meeting a minimum confidence are retained.

The search is feasible because of the downward closure property, also called the Apriori principle: every subset of a frequent itemset must itself be frequent. An algorithm can therefore prune candidate itemsets as soon as any of their subsets fails the support test, which removes most of the exponential search space.

Support, confidence, lift and other measures

Interestingness measures decide which of the thousands of possible rules are worth attention. Support and confidence filter rules during mining, while lift and related measures rank the survivors by how much they deviate from chance.

The table below defines the main measures for a rule A → B, where P denotes the proportion of transactions containing the given items.

MeasureFormulaInterpretation
SupportP(A and B)Share of all transactions containing both sides
ConfidenceP(A and B) / P(A)How often B appears when A is present
LiftConfidence / P(B)Above 1 means positive association, 1 means independence
LeverageP(A and B) − P(A) × P(B)Absolute difference from independence
Conviction(1 − P(B)) / (1 − confidence)How often the rule would fail if A and B were independent
Core measures for a rule A → B

Confidence alone is misleading for popular consequents. If 80% of all baskets contain milk, a rule predicting milk with 75% confidence is actually a negative association, which lift reveals as a value below 1. Practitioners therefore always report lift alongside confidence.

Main algorithms and their trade-offs

Three classic algorithms dominate frequent itemset mining, and they differ mainly in how they traverse the search space and how much memory they consume. All produce the same frequent itemsets for the same thresholds.

AlgorithmSearch strategyStrengthLimitation
AprioriBreadth-first candidate generation with repeated database scansSimple and easy to explainMany scans and huge candidate sets on dense data
FP-GrowthCompressed prefix tree, no candidate generationTypically much faster on large datasetsThe tree can exceed memory on very diverse data
EclatDepth-first search with vertical transaction-ID listsFast support counting by set intersectionID lists grow large for frequent items
Classic frequent itemset mining algorithms

Extensions address specific needs. Closed and maximal itemset mining reduces redundant output, sequential pattern mining such as GSP or PrefixSpan respects the order of events, and quantitative association rules handle numeric attributes after discretization. Distributed implementations of FP-Growth run on cluster frameworks for billions of transactions.

Association rule learning is descriptive, not predictive: it reports co-occurrence patterns without a designated target variable. This sets it apart from supervised classifiers and from clustering, even though all three can describe the same data.

MethodOutputTarget variableTypical question answered
Association rulesIf-then item relationshipsNoneWhich items occur together
Decision treeHierarchical prediction rulesRequiredWhich attributes predict a class
k-means clusteringGroups of similar recordsNoneWhich customers resemble each other
Collaborative filteringPersonalized item scoresImplicit user preferenceWhat a specific user is likely to want
Association rules compared with neighboring methods

A decision tree also yields rules, but each rule predicts one fixed class label. Association rules may place any item on either side, which makes them more exploratory and far more numerous.

In recommender pipelines, association rules often serve as a transparent baseline or a cold-start fallback. They capture population-level patterns well but ignore individual history, so collaborative filtering or learned embedding models usually outperform them once enough user-level data exists.

Choosing thresholds and avoiding common mistakes

Threshold selection is the most consequential practical decision in association rule learning. Support set too high hides valuable niche patterns, while support set too low produces a combinatorial explosion of rules and long run times.

SymptomLikely causeRemedy
Millions of rulesMinimum support too lowRaise support or mine closed itemsets
Only obvious rulesSupport too high, popular items dominateLower support and rank by lift
Spurious rulesMultiple testing on many candidatesApply statistical significance tests or holdout validation
Rules about bags and receiptsUninformative items left in dataRemove administrative items before mining
Out-of-memory errorsDense data with long transactionsUse FP-Growth, sampling or distributed mining
Typical problems, causes and remedies

Typical retail starting points are support between 0.1% and 1% and confidence above 30%, but suitable values depend on catalog size and transaction length. Crucially, a strong rule shows correlation, not causation: placing two products together because a rule links them still needs an A/B test to confirm any sales effect.

A non-technical view

Association rule learning looks through many lists of things that happened together and notices which items tend to travel together. A supermarket might learn that people who buy pasta and tomato sauce often also pick up parmesan.

Each pattern gets three simple scores: how common it is, how dependable it is, and whether it beats pure coincidence. The method only finds patterns. People still decide whether a pattern is useful and whether acting on it actually helps.

A concrete example

An online hardware store analyzes 2.4 million orders from one year using FP-Growth with minimum support of 0.2% and minimum confidence of 25%. After removing shipping fees and gift wrap from the item lists, the analysis yields about 3,800 rules, which the team ranks by lift.

One rule stands out: customers buying a tile cutter and tile adhesive also buy spacers with 41% confidence and a lift of 6.8, although spacers appear in only 6% of orders overall. The store adds spacers as a suggested item on the tile cutter page and runs a four-week A/B test. The test group shows a measurable rise in spacer attachment, and the bundle becomes a permanent recommendation.