Association Rule Mining (Apriori)
- Introduced by
- Rakesh Agrawal & Ramakrishnan Srikant
- Year
- 1994
- Type
- Unsupervised pattern discovery algorithm
- Family
- Pattern mining
What does it do?
Association Rule Mining is an unsupervised data-mining technique that discovers co-occurrence patterns among items in transactional datasets.
Formally introduced by Agrawal, Imieliński, and Swami in 1993, and refined with the landmark Apriori algorithm by Agrawal and Srikant in 1994, it identifies rules of the form X ⇒ Y — meaning that transactions containing itemset X tend to also contain itemset Y — quantified by support, confidence, and lift.
The intuition behind the method
Imagine a supermarket receipt log: if thousands of customers who buy bread and butter also buy milk, that pattern deserves attention. Association Rule Mining works like a meticulous librarian combing through every receipt, counting how often item combinations appear together, and surfacing the combinations that exceed a minimum frequency. Once frequent groups are found, the algorithm asks: given you already have these items, how reliably does that predict the next item? This frequency-then-confidence two-pass logic is the heart of Apriori.
History
The foundational paper by Agrawal, Imieliński, and Swami (1993) defined the association rule problem in the context of supermarket transaction data. Agrawal and Srikant's 1994 VLDB paper introduced the Apriori algorithm and its efficient pruning strategy, making large-scale mining practical. Subsequent work produced FP-Growth (Han et al., 2000), which avoids candidate generation entirely, and ECLAT, which mines in vertical data format — establishing a rich algorithmic family now central to data mining curricula.
When to use it
Association Rule Mining suits large transactional datasets where the goal is to discover co-occurrence patterns without a predefined target variable. It assumes items are binary (present/absent) per transaction. It is appropriate for market basket analysis, recommendation systems, web clickstream analysis, and medical co-diagnosis discovery. It is unsuitable for continuous or ordinal data unless pre-discretized, for datasets with very high dimensionality (exponential candidate space), or when causal rather than associative inference is required. Alternatives include FP-Growth for faster frequent-itemset enumeration and sequence mining when temporal order matters.
Limitations and considerations
- Exponential candidate space: rule count grows combinatorially with the number of distinct items.
- Support–confidence framework can yield misleading rules when item base rates vary widely (lift adjustment required).
- Binary transaction model requires discretization of continuous variables, introducing information loss.
- High minimum support thresholds miss rare but valuable rules; low thresholds generate thousands of trivial rules.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Fully unsupervised: no labeled data or predefined target needed.
- Interpretable output: rules are human-readable if-then statements with quantified support and confidence.
- Scalable via Apriori pruning; FP-Growth variant eliminates repeated database scans entirely.
- Domain-agnostic: applied across retail, healthcare, web analytics, and bioinformatics.
Applications
- Retail: product placement and cross-selling recommendation from point-of-sale transaction logs.
- Healthcare: co-occurrence analysis of diagnoses, procedures, or medications in electronic health records.
- Web analytics: clickstream pattern discovery for page recommendation and navigation optimization.
- Bioinformatics: identification of co-expressed gene sets and protein interaction motifs.
- Cybersecurity: detection of correlated network events indicative of intrusion patterns.
How it works
How it works
The algorithm scans the transaction database D to count how often each itemset X appears. An itemset is declared frequent — and placed in L_k — only when its support (the fraction of transactions containing it) meets or exceeds the user-defined minimum support threshold σ_min. The process starts with individual items (k=1) and iteratively builds larger candidate sets.
Formula
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}The anti-monotonicity property of support states that any subset of a frequent itemset must itself be frequent. Apriori exploits this by pruning every candidate k-itemset whose (k-1)-subsets are not all in the verified frequent set L_{k-1}. This dramatically reduces the search space, avoiding expensive database scans for itemsets that cannot possibly be frequent.
Formula
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kFrom each frequent itemset X ∪ Y, the algorithm generates rules X ⇒ Y where X and Y are disjoint subsets. A rule is retained only when its confidence — the conditional probability of Y given X, computed as support(X ∪ Y) / support(X) — meets or exceeds the minimum confidence threshold γ_min. This step converts raw co-occurrence into directional predictive statements.
Formula
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}Retained rules are ranked and filtered by lift, which measures how much more likely Y is to appear with X than by chance. Lift > 1 indicates positive correlation beyond independence; lift = 1 indicates independence; lift < 1 indicates a negative correlation. Additional interestingness measures such as conviction and leverage can further refine the rule set for practical deployment.
Formula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Common pitfalls
- Setting minimum support too low floods the analyst with spurious rules; threshold selection requires domain knowledge or cross-validation.
- Confusing statistical association with causation: high lift does not imply that X causes Y.
- Ignoring the item frequency distribution: common items dominate rules and crowd out meaningful rare-item associations.
- Treating confidence alone as a quality metric; a rule with high confidence but low lift may perform no better than random chance.
Frequently asked questions
What is the difference between support, confidence, and lift?
Support measures how frequently an itemset appears in the dataset as a whole. Confidence measures the conditional probability of the consequent given the antecedent. Lift normalizes confidence by the consequent's marginal frequency, revealing whether the co-occurrence exceeds what would be expected under independence. All three metrics are needed together for robust rule evaluation.
How does the Apriori algorithm reduce computational cost?
Apriori exploits the anti-monotonicity property: if an itemset is infrequent, all of its supersets must also be infrequent. By discarding any candidate whose subsets are not all verified as frequent, the algorithm prunes vast portions of the search space before counting, drastically reducing the number of database passes required compared to brute-force enumeration.
When should I use FP-Growth instead of Apriori?
FP-Growth is preferred when the dataset is large and the minimum support threshold is low, because it compresses the transaction database into a compact FP-tree structure and mines patterns directly without generating explicit candidates. This eliminates repeated full-database scans, making it substantially faster than Apriori on dense datasets with many frequent itemsets.
Related methods
Sources
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
Open DOI referenceCopied.Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
Open publication referenceCopied.