Apriori

Apriori is an algorithm for mining frequent itemsets and learning association rules over transactional databases. It aims to identify item combinations that appear together in a dataset with support above a user-specified threshold, enabling the discovery of meaningful associations between items.

The algorithm relies on the apriori principle: every nonempty subset of a frequent itemset must also be frequent. This anti-monotone property allows pruning of itemsets that contain an infrequent subset, reducing the search space and guiding the candidate generation process.

Operation proceeds in passes. In the first pass, all frequent 1-itemsets are found by counting item frequencies. In each subsequent pass, candidate k-itemsets are generated from frequent (k-1)-itemsets, candidates containing any infrequent (k-1) subset are pruned, and the database is scanned to estimate their supports. The process repeats until no new frequent itemsets are found. After obtaining frequent itemsets, association rules can be generated by partitioning each frequent itemset into antecedent and consequent parts and evaluating confidence, with rules meeting a minimum confidence threshold reported.

Complexity and variants: Apriori can be computationally expensive for large datasets due to candidate generation and multiple database scans. Various enhancements exist, such as hash-based pruning, partitioning, and sampling, as well as alternative mining algorithms (for example, FP-Growth) that aim to reduce candidate generation. Nevertheless, Apriori remains foundational in market basket analysis and broader association rule learning.

History: Apriori was introduced by Rakesh Agrawal and Ramakrishnan Srikant in 1994. It has influenced numerous extensions and appears in many data mining textbooks and software systems.