Apriori: Frequent Itemsets via the Apriori Algorithm#

Stage 3 · 🛒 Market Basket & Association Rules · Lesson 20 of 56 · intermediate

◀ Previous · How Association Rules Are Discovered: Concepts, Scale, Measures, and the Apriori Approach · Next · association_rules: Generating Association Rules from Frequent Itemsets (mlxtend) ▶ · ↑ Section

Important

✨ AI-generated content. This page was written with the assistance of an AI language model and is provided as a learning aid. Despite careful review, it may still contain mistakes, omissions, or out-of-date information. Whether you are new to the topic, a team lead, or a senior practitioner, treat it as a starting point rather than an authoritative reference: read it critically and independently verify anything you act on (code, commands, figures, and factual claims) against official documentation and primary sources before relying on it.

Prior knowledge#

The Apriori algorithm, introduced by Agrawal and Srikant in 1994, is the classic method for finding all frequent itemsets — the groups of items whose support clears a chosen minimum. Its name comes from the a priori (prior) knowledge it exploits: it uses the frequent itemsets already found at one size to decide what is worth checking at the next.

The level-wise search#

The algorithm walks the itemsets level by level, from small to large, applying downward closure at every step. The key move is candidate generation: a \(k\)-item candidate is formed only if all of its \((k{-}1)\)-item subsets are already known to be frequent. Any candidate with an infrequent subset is discarded before its support is ever counted — that is where the saving comes from.

One level at a time#

Concretely, each level repeats three steps:

Generate candidate \(k\)-itemsets by combining frequent \((k{-}1)\)-itemsets, then prune those with any infrequent subset;
Count each surviving candidate’s support with a single scan of the transaction database;
Keep those meeting minimum support as the frequent \(k\)-itemsets.

Start with frequent single items (\(k = 1\)) and repeat, increasing \(k\), until no new candidates survive. The cost is that dense data can still spawn many candidates and repeated database scans — Apriori is simple and correct, not always the fastest.

Then the rules#

Apriori delivers frequent itemsets; turning them into rules is the easy second half. For each frequent itemset, split it into an antecedent and consequent every way possible and keep the splits whose confidence (or lift) clears a threshold. Because both sides come from a frequent itemset, the rule’s support is already known — which is exactly what the next lesson automates in Python.

Hint