Apriori Algorithm

The Apriori algorithm finds relationships between items in a dataset — identifying which items are frequently bought together, and turning those patterns into rules.

In a supermarket, customers who buy pizza often buy soft drinks and breadsticks as well. Once that pattern is known, the shop can create combo offers, which makes shopping easier for customers and increases sales. Large stores place biscuits, chips, and chocolates near each other for the same reason. These relationships are expressed as association rules, and Apriori is the classic algorithm for finding them.

What Apriori Does

Apriori has two jobs:

1. Find frequent itemsets — groups of items that appear together often enough to matter.
2. Generate association rules from those itemsets.

It works on transaction databases: large collections of records, each listing the items in one purchase.

It was introduced in 1994 by Rakesh Agrawal and Ramakrishnan Srikant. The name comes from its use of prior knowledge — what it learned about smaller itemsets constrains which larger ones it needs to check.

The Three Measures

Apriori relies on three measures. Suppose a supermarket has 4,000 transactions:

• 400 include biscuits
• 600 include chocolate
• 200 include both

1. Support

Support shows how frequently an itemset appears in the dataset.

  Support(A) = (Transactions containing A) / (Total transactions)

  Support(Biscuits)  = 400 / 4000  = 10%
  Support(Chocolate) = 600 / 4000  = 15%

2. Confidence

Confidence measures how often the consequent appears when the antecedent does.

  Confidence(A → B) = (Transactions containing both) / (Transactions containing A)

  Confidence(Biscuits → Chocolate) = 200 / 400 = 50%

So half of the customers who bought biscuits also bought chocolate.

3. Lift

Lift measures how much stronger that relationship is than pure chance. The formula divides confidence by the support of the consequent — the item being predicted:

  Lift(A → B) = Confidence(A → B) / Support(B)

  Lift(Biscuits → Chocolate) = 0.50 / 0.15 = 3.33

Customers who buy biscuits are about 3.33 times more likely to buy chocolate than the average customer is.

Dividing by the support of the antecedent instead is a common error, and it inflates the result — here it would give 5 rather than 3.33. The comparison lift makes is "given they bought A, are they more likely to buy B than a random shopper?", so the baseline must be B's own frequency.

Interpreting lift

Lift is what separates an interesting rule from a merely common one. Bread and milk may appear together in most transactions, giving high support and confidence, while lift near 1 reveals that this is only because both are bought constantly — not because they are related.

The Apriori Principle

The algorithm rests on one property that makes the problem tractable:

• All subsets of a frequent itemset must also be frequent.
• If an itemset is infrequent, every superset of it is also infrequent.

The second statement is the useful one. A set cannot appear more often than any of its parts, so once {Milk, Oil} is known to be infrequent, every larger set containing both can be eliminated without counting it. This is the pruning that keeps Apriori from having to evaluate every possible combination.

How Apriori Works: A Worked Example

Take six transactions over the products Rice (R), Pulse (P), Oil (O), and Milk (M):

Set minimum support = 50%, which with 6 transactions means an itemset must appear at least 3 times.

Step 1 — Frequent single items

All four survive.

Step 2 — Candidate pairs

Two pairs fall below the threshold and are discarded.

Step 3 — Candidate triples

Here the Apriori principle does the work. Of the four possible triples, only one is even worth counting:

Counting the single surviving candidate:

  {Rice, Pulse, Oil} appears in transactions 1, 2, 4  →  count = 3  →  FREQUENT

Three of four candidates were eliminated without a database scan. On a real dataset with thousands of items, this is the difference between a feasible computation and an impossible one.

Note also the consistency check: {Rice, Pulse, Oil} has count 3, and its subset {Oil, Rice} also has count 3. A larger itemset can never exceed the count of any subset — if it does, there is an arithmetic error somewhere.

Generating Association Rules

Once frequent itemsets are found, rules are generated from them. For an itemset of n items, the number of possible rules is:

  2ⁿ − 2

For {Rice, Pulse, Oil}, that gives 2³ − 2 = 6 rules:

The first rule has 100% confidence: every transaction containing rice and oil also contained pulse. But its lift is 1.00 — meaning no real association, because pulse appears in every transaction anyway. High confidence with lift at 1 is the classic false positive of association rule mining, and it is exactly why lift is reported alongside confidence.

Two approaches to generating rules:

Brute force — enumerate every possible rule and calculate support and confidence for each. Correct but expensive.

Two-step approach — find frequent itemsets first, then generate rules only from those. This is what Apriori does, and it works because a rule can only have high support if the itemset it comes from is frequent.

Improving Apriori's Efficiency

Hash-based itemset counting — uses a hash table to reduce the number of candidate itemsets that must be tracked.

Transaction reduction — a transaction containing no frequent k-itemsets cannot contain any frequent (k+1)-itemsets, so it can be dropped from later scans.

Partitioning and sampling — process subsets of the database and combine results, reducing full scans.

FP-Growth — a later algorithm that avoids candidate generation entirely by compressing the database into a tree structure and mining it directly. It requires only two database scans instead of one per level, and is generally much faster on large datasets. Apriori remains the standard teaching algorithm because its logic is visible; FP-Growth is more common in production.

Applications

Market basket analysis — the original application: understanding which products are bought together, for placement and promotions.

E-commerce recommendations — "frequently bought together" suggestions.

Medical field — analyzing patient records for co-occurring conditions, symptoms, and treatments.

Education — examining relationships between student attributes, course choices, and outcomes.

Website design — analyzing navigation patterns to improve site structure.

Tourism — analyzing booking patterns to understand traveller preferences.

Forestry and environmental data — finding associations in species and habitat records.

Advantages

• Easy to understand — the logic is simple and the output is human-readable
• Works with unlabelled data — no training labels required, since it is unsupervised
• Well-extended — many improved variants exist for specific applications

Disadvantages

• High computational cost — requires scanning the database once for each itemset size
• Large numbers of candidate itemsets — combinations grow rapidly with the number of items, and a low support threshold can produce an unmanageable number
• Threshold sensitivity — set minimum support too high and real patterns are missed; too low and the output is swamped by noise. There is no principled way to choose it other than experimentation

Related Concepts

Association rule mining is one of the seven techniques covered in this series' lesson on data mining techniques, where support, confidence, and lift are introduced. The market basket application appears in the introduction lesson, and keyword-based association analysis — the same algorithm applied to words instead of products — is covered in the text data mining lesson.