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.
| Measure | Formula | Interpretation |
|---|---|---|
| Support | P(A and B) | Share of all transactions containing both sides |
| Confidence | P(A and B) / P(A) | How often B appears when A is present |
| Lift | Confidence / P(B) | Above 1 means positive association, 1 means independence |
| Leverage | P(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 |
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.
| Algorithm | Search strategy | Strength | Limitation |
|---|---|---|---|
| Apriori | Breadth-first candidate generation with repeated database scans | Simple and easy to explain | Many scans and huge candidate sets on dense data |
| FP-Growth | Compressed prefix tree, no candidate generation | Typically much faster on large datasets | The tree can exceed memory on very diverse data |
| Eclat | Depth-first search with vertical transaction-ID lists | Fast support counting by set intersection | ID lists grow large for frequent items |
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.
How it compares with related techniques
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.
| Method | Output | Target variable | Typical question answered |
|---|---|---|---|
| Association rules | If-then item relationships | None | Which items occur together |
| Decision tree | Hierarchical prediction rules | Required | Which attributes predict a class |
| k-means clustering | Groups of similar records | None | Which customers resemble each other |
| Collaborative filtering | Personalized item scores | Implicit user preference | What a specific user is likely to want |
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.
| Symptom | Likely cause | Remedy |
|---|---|---|
| Millions of rules | Minimum support too low | Raise support or mine closed itemsets |
| Only obvious rules | Support too high, popular items dominate | Lower support and rank by lift |
| Spurious rules | Multiple testing on many candidates | Apply statistical significance tests or holdout validation |
| Rules about bags and receipts | Uninformative items left in data | Remove administrative items before mining |
| Out-of-memory errors | Dense data with long transactions | Use FP-Growth, sampling or distributed mining |
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.