Association Rule

Association rule learning is a foundational data mining technique for uncovering frequent patterns, correlations, and co-occurrence relationships within large collections of transactional or categorical data. Rules take the canonical form "If A, then B," where A and B are sets of items (itemsets), and the strength of each rule is quantified using several key metrics. Support measures how often the combined itemset appears across all transactions, filtering out rare and potentially spurious patterns. Confidence captures the conditional probability that B occurs given A, while lift compares the observed co-occurrence frequency against what would be expected if A and B were statistically independent — a lift greater than 1 signals a genuinely interesting association rather than a coincidental one.

The practical viability of association rule mining depends heavily on efficient algorithms for enumerating frequent itemsets, since the search space grows exponentially with the number of distinct items. The Apriori algorithm, introduced in 1994, exploits the antimonotone property — any superset of an infrequent itemset must also be infrequent — to prune the search space dramatically. Later algorithms such as FP-Growth avoid the costly candidate generation step entirely by compressing the transaction database into a compact tree structure, enabling much faster mining on large-scale data.

Association rules have found broad application well beyond their origins in retail market basket analysis, where the classic example is the co-purchase of items like bread and butter. The technique is now routinely applied in bioinformatics (discovering co-expressed genes), web usage mining (identifying navigation patterns), fraud detection, and recommendation systems. In machine learning pipelines, mined association rules can serve as interpretable feature relationships or as a basis for constructing structured prior knowledge, making them a useful bridge between descriptive analytics and predictive modeling.