Skip to content
Back to search results

Apriori Algorithm

Introduced by
Agrawal, R. & Srikant, R.
Year
1994
Type
Frequent itemset and association rule mining algorithm
Family
Machine learning
Font size

What does it do?

The Apriori algorithm, introduced by Agrawal and Srikant in 1994, is the foundational method for discovering frequent itemsets and association rules in transactional databases.

It uses a breadth-first, level-wise search guided by the anti-monotone property of support to efficiently enumerate all item combinations that co-occur above a user-set minimum threshold, then extracts interpretable if-then rules from those patterns.

The intuition behind the method

Consider a supermarket receipt database. Apriori's insight is the anti-monotone property: if a pair of products is rarely bought together, no larger set containing that pair can be frequent. This lets the algorithm prune the exponentially large search space of possible item combinations by building candidates level by level — starting with single items, then pairs, then triples — and discarding any candidate whose subsets are already known to be infrequent, before even counting it in the data.

History

Rakesh Agrawal and Ramakrishnan Srikant introduced the Apriori algorithm at VLDB 1994, building on Agrawal et al.'s 1993 formulation of the association rule mining problem. The name reflects its key insight: using prior knowledge of frequent (k)-itemsets to prune candidates at level k+1. It became the canonical benchmark against which all subsequent frequent-itemset algorithms — including FP-Growth (2000) and Eclat — are measured, and remains a standard chapter in data-mining and machine-learning textbooks.

When to use it

Use Apriori when the goal is to discover co-occurrence patterns or if-then relationships in transactional or binary item-presence data — market basket analysis, survey item co-endorsement, medical diagnosis co-occurrence, or text term association. It is suitable for moderate-sized datasets where transparency and interpretability of the output rules is a priority. Do not use Apriori when the transaction database is very large (millions of rows with wide item catalogs), as its repeated full database scans make it slow compared to FP-Growth; in those cases FP-Growth is preferred. It is also inappropriate for continuous numeric data without prior discretization, and it does not model directionality or causality.

Limitations and considerations

  • Repeated full database scans make it slow on large datasets — FP-Growth is often preferred at scale.
  • Lowering the support threshold can produce an exponential number of candidate itemsets and rules, making interpretation difficult.
  • Does not capture temporal order, directionality, or causal relationships between items.
  • Results are sensitive to the choice of support and confidence thresholds, which require domain knowledge or systematic tuning.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Generates fully interpretable if-then rules with quantified support, confidence, and lift.
  • The anti-monotone pruning property makes an otherwise exponential search tractable.
  • Requires no prior labeling of the data; it is entirely unsupervised.
  • Threshold parameters (support, confidence) give the analyst direct control over rule granularity.
  • Output rules are actionable and can be communicated to non-technical stakeholders without algorithmic background.
  • Seminal, heavily cited, and implemented in virtually every major data-mining library.

Applications

  • Market basket analysis: discovering which products are frequently purchased together to guide shelf layout and promotions.
  • Medical informatics: identifying co-occurring symptoms, diagnoses, or drug prescriptions in patient records.
  • Web usage mining: finding which pages or features users tend to visit or activate together.
  • Survey and questionnaire analysis: detecting which items or scale responses are systematically co-endorsed.
  • Recommender system bootstrapping: generating candidate item associations before deploying collaborative filtering.
  • Fraud detection: surfacing unusual co-occurrence patterns in transaction logs that deviate from normal baskets.

How it works

How it works

1

The analyst chooses two thresholds before running the algorithm: minimum support (the fraction of transactions that must contain a given itemset for it to be considered frequent) and minimum confidence (the conditional probability required for an if-then rule to be retained). These two values control the volume and specificity of the output and should be calibrated through domain knowledge or exploratory runs.

2

The algorithm makes one full scan of the transaction database to count how often each individual item appears. Only items whose support meets or exceeds the minimum support threshold are kept; the rest are discarded. This set of frequent single items forms the first level of candidates.

Formula
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

The frequent itemsets found at level k are joined pairwise to form candidate itemsets of size k+1. Only pairs that share the same first k-1 items are joined, a rule that keeps the candidate set compact. A new database scan counts the support of each candidate.

4

Before counting, every candidate of size k+1 is checked against all its (k)-subsets. If any subset was not frequent at the previous level, the candidate is pruned immediately without reading the data, exploiting the anti-monotone property to reduce computation. The survivors of this pruning step form the next level of frequent itemsets.

5

From every frequent itemset of size two or more, all possible if-then rules are generated by partitioning the items into an antecedent and a consequent. Each rule is evaluated on confidence — the proportion of antecedent transactions that also contain the consequent. Rules below the minimum confidence are discarded.

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

Surviving rules are ranked by lift, which compares the observed confidence with the baseline frequency of the consequent. A lift above 1 signals that the antecedent and consequent co-occur more than by chance; lift near 1 indicates independence; lift below 1 indicates a negative association. Rules with the highest lift are the most actionable discoveries.

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

Common pitfalls

  • Setting minimum support too low and drowning in thousands of low-quality rules without filtering by lift.
  • Interpreting high confidence as causation rather than co-occurrence — a rule with high confidence but lift near 1 is trivial.
  • Applying Apriori to continuous features without discretizing them first, which inflates the item space and degrades results.
  • Reporting rules without checking whether the itemset sample sizes are large enough to trust the support estimates.
  • Neglecting to remove uninformative rules (e.g., rules involving universally purchased items like a store loyalty card).

Frequently asked questions

What is the difference between support, confidence, and lift?

Support is the fraction of all transactions that contain the itemset — it measures prevalence. Confidence is the conditional probability that the consequent appears given the antecedent — it measures rule reliability. Lift is the ratio of observed confidence to the baseline frequency of the consequent; a lift above 1 shows a genuine positive association rather than a coincidence driven by item popularity.

When should I choose FP-Growth over Apriori?

FP-Growth compresses the database into a tree structure and mines it without repeated full scans, making it substantially faster on large datasets or when minimum support is low. Apriori is easier to understand and implement and works well on small to moderate datasets where runtime is not a bottleneck.

How do I choose minimum support and confidence?

There is no universal rule. Common practice is to run the algorithm at several support levels, plot the number of frequent itemsets against support, and choose a value in the elbow of the curve. Confidence is then set based on the business or research question — higher confidence for mission-critical rules, lower for exploratory discovery. Always validate the top rules against domain expertise.

Can Apriori handle numeric or continuous data?

Apriori requires binary item-presence data. Continuous variables must be discretized into bins (e.g., age into low/medium/high) before encoding as items. Poor discretization can severely distort the discovered rules, so binning strategy deserves careful thought.

Does Apriori imply causation between items?

No. Association rules capture co-occurrence, not causation or direction. A rule 'bread → butter' means they often appear in the same basket; it does not mean buying bread causes someone to buy butter, nor that the relationship is asymmetric in any causal sense.

Related methods

Sources

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    Open publication reference
    Copied.
  2. Apriori algorithm. Wikipedia.

    Open publication reference
    Copied.