The encyclopedia · R&D & Science · Technical decision · 1994
IBM's Apriori mined what shoppers buy together by pruning impossible candidates
Agrawal and Srikant's 1994 Apriori algorithm found frequent item-sets in huge transaction logs by using a subset rule to prune candidates early.
IBM Almaden Research Center
the move
Retailers wanted to know which products are bought together, but the number of possible item combinations exploded exponentially with the number of SKUs.
Apriori, published in 1994, exploits a property: any superset of an infrequent item-set must itself be infrequent. It counts single items, keeps frequent ones, grows them into pairs, and repeats, so it never counts a candidate whose parent already failed.
The trick converts a search that quickly becomes unmanageable into one that touches only the small frontier of frequent sets. It turned market-basket analysis into a practical database query.
why it works
- Downward closure prunes the search before it grows, so run time tracks frequent sets, not all sets.
- A database scan per level keeps memory bounded to candidate sets.
- It gives exact frequent sets, not a heuristic or a sampled approximation.
- The same pruning generalises to sequence and pattern mining beyond baskets.
what transfers
Before searching a huge space, look for a monotonic property that lets you discard whole branches at once. A rule that rules out a region shrinks the hunt from exponential to linear.
what came after
Apriori became the canonical association-rule algorithm and a standard lesson in data mining. It seeded the field that powers recommendation, assortment and cross-sell analysis, and later fpgrowth and other methods that cut its scans.
references
spotted an error? The archive wants to know.