Further Reading: Chapter 23

Association Rules and Market Basket Analysis

Foundational Papers

1. "Mining Association Rules Between Sets of Items in Large Databases" --- Rakesh Agrawal, Tomasz Imielinski, and Arun Swami (1993) The paper that started it all. Agrawal, Imielinski, and Swami introduced the problem of mining association rules from transaction databases, defined support, confidence, and the frequent itemset framework, and proposed the AIS algorithm (a precursor to Apriori). Published at ACM SIGMOD 1993. The paper is short and readable. The problem formulation is more important than the specific algorithm, which was quickly superseded by Apriori.

2. "Fast Algorithms for Mining Association Rules" --- Rakesh Agrawal and Ramakrishnan Srikant (1994) The paper that introduced the Apriori algorithm. Agrawal and Srikant formalized the downward closure property (if an itemset is infrequent, all its supersets are infrequent) and used it to prune the candidate generation step. The result was dramatically faster mining than the AIS algorithm. Published at VLDB 1994. This paper defines the standard algorithm taught in every data mining course. Read sections 2-3 for the algorithm; skip the database-specific optimizations unless you are building your own implementation.

3. "Mining Frequent Patterns without Candidate Generation" --- Jiawei Han, Jian Pei, and Yiwen Yin (2000) The FP-Growth paper. Han, Pei, and Yin proposed compressing the transaction database into a Frequent Pattern tree (FP-tree) and mining frequent itemsets directly from the tree, completely eliminating the candidate generation step. The result was orders-of-magnitude speedup on large datasets. Published at ACM SIGMOD 2000. FP-Growth is the default algorithm in most modern implementations (including mlxtend and Spark MLlib). Read this for the tree construction algorithm and the recursive mining procedure.

Interestingness Metrics

4. "Interestingness Measures for Data Mining: A Survey" --- Liqiang Geng and Howard J. Hamilton (2006) A comprehensive survey of over 20 interestingness measures for association rules, including support, confidence, lift, conviction, cosine, Jaccard, and several information-theoretic measures. Published in ACM Computing Surveys. The paper classifies measures along several dimensions (symmetry, monotonicity, sensitivity to data size) and provides guidelines for selecting measures based on domain requirements. Essential reading if you need to choose between metrics for a specific application.

5. "Association Rules and the Disjunctive Normal Form" --- Chun-Nan Hsu and Yiming Yang (2000); supplemented by Tao Zhang (2000) Zhang's metric for measuring rule interestingness was introduced to address limitations of lift and conviction for rules involving rare items. The metric is bounded between -1 and +1, handles both positive and negative associations, and is more robust to base-rate effects than lift. The original formulation appears in several papers from this period; Geng and Hamilton (item 4) provides a unified treatment.

6. "Selecting the Right Interestingness Measure for Association Patterns" --- Pang-Ning Tan, Vipin Kumar, and Jaideep Srivastava (2004) A focused analysis comparing 21 interestingness measures on real datasets. Tan, Kumar, and Srivastava showed that different measures can rank the same set of rules in completely different orders, and that no single measure is universally best. Published at KDD 2004. The paper provides decision tables for choosing measures based on properties like null-invariance and symmetry. Read this before choosing a metric for production rule filtering.

Scalable Implementations

7. "Parallel FP-Growth for Query Recommendation" --- Haoyuan Li, Yi Wang, Dong Zhang, Ming Zhang, and Edward Chang (2008) The paper describing the parallelization of FP-Growth for MapReduce (and later Spark). Li et al. proposed a partitioning strategy that distributes the mining across multiple machines while maintaining correctness. This is the algorithm behind Spark MLlib's FPGrowth implementation. Published at RecSys 2008. Read this if you need to mine association rules on datasets with billions of transactions that do not fit in single-machine memory.

8. Spark MLlib Documentation --- FPGrowth The official documentation for Spark's distributed FP-Growth implementation. Covers the API for both Scala and PySpark, parameter tuning (minSupport, minConfidence, numPartitions), and integration with Spark DataFrames. The FPGrowth model can generate rules directly and make predictions (i.e., recommendations given a set of items). Available at spark.apache.org/docs/latest/ml-frequent-pattern-mining.html.

Applications

9. "The Discovery of Association Rules in Retail Transaction Data" --- Michael J.A. Berry and Gordon S. Linoff (1997) From the book Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management. Berry and Linoff popularized the beer-and-diapers story (while noting its uncertain provenance) and provided some of the earliest practical guidance for applying association rules in retail. The chapter covers data preparation, threshold selection, and translating rules into merchandising actions. Dated in its technology but timeless in its business framing.

10. "Recommendation Systems: Principles, Methods and Evaluation" --- F.O. Isinkaye, Y.O. Folajimi, and B.A. Ojokoh (2015) A survey that places association rule-based recommendations in the broader context of collaborative filtering, content-based, and hybrid recommender systems. Published in the Egyptian Informatics Journal. The paper covers how association rules compare to matrix factorization and nearest-neighbor approaches for product recommendation. Read this to understand where market basket analysis fits in the recommendation ecosystem and when other methods outperform it.

11. "Market Basket Analysis in Insurance" --- various industry reports Association rules have found applications beyond retail: in insurance (which policy combinations predict claims), healthcare (which diagnosis codes co-occur), and telecommunications (which service bundles predict churn). Industry whitepapers from McKinsey, Deloitte, and SAS provide case studies. The framework is identical; only the domain vocabulary changes. Search for "market basket analysis" combined with your industry for relevant examples.

mlxtend Library

12. "mlxtend: A Python Library for Machine Learning Extensions" --- Sebastian Raschka (2018) The paper describing mlxtend, the Python library used throughout this chapter for Apriori, FP-Growth, and association rule generation. Published in the Journal of Open Source Software. mlxtend provides a consistent API for frequent itemset mining and rule generation, with support for multiple interestingness metrics. Documentation: rasbt.github.io/mlxtend. The frequent_patterns module is the most used component for association rule mining in Python.

13. mlxtend Frequent Patterns Documentation The official documentation for mlxtend's association rule mining modules: TransactionEncoder, apriori, fpgrowth, and association_rules. Includes examples, parameter descriptions, and performance tips. The documentation covers the one-hot encoding requirement, the use_colnames parameter, and the metrics available for rule filtering (support, confidence, lift, conviction, Zhang's metric, leverage, and others). Available at rasbt.github.io/mlxtend/user_guide/frequent_patterns.

Advanced Topics

14. "Mining Sequential Patterns: Generalizations and Performance Improvements" --- Rakesh Agrawal and Ramakrishnan Srikant (1996) Sequential pattern mining extends association rules to ordered data: which sequences of purchases (or events) occur frequently? The rule {bought laptop in January} -> {bought laptop bag in February} has a temporal ordering that standard association rules ignore. Agrawal and Srikant introduced the GSP (Generalized Sequential Patterns) algorithm. Published at EDBT 1996. Read this if your transaction data has timestamps and you care about the order of purchases, not just co-occurrence.

15. "Constraint-Based Mining of Association Rules" --- Jian Pei, Jiawei Han, and Laks V.S. Lakshmanan (2001) In practice, you often want rules that satisfy specific constraints: rules involving a particular product, rules with consequents in a specific category, rules where the antecedent has fewer than 3 items. Pei, Han, and Lakshmanan formalized constraint-based mining and showed how to push constraints into the mining algorithm (rather than mining all rules and filtering afterward). Published in the Data Mining and Knowledge Discovery journal. This is the theoretical foundation for the filtering pipelines described in this chapter.

16. "Quantitative Association Rules" --- Ramakrishnan Srikant and Rakesh Agrawal (1996) Standard association rules are binary: an item is in the basket or it is not. Quantitative association rules handle continuous attributes: "Customers aged 30-45 with income > $80,000 tend to buy premium products." Srikant and Agrawal proposed discretization strategies and modified the Apriori algorithm to handle intervals. Published at ACM SIGMOD 1996. Read this if your data naturally involves quantities (purchase amounts, viewing hours) rather than binary presence/absence.

17. "High-Utility Itemset Mining" --- Vincent S. Tseng et al. (2015) Standard association rules treat all items equally: bread and caviar each contribute one unit to the basket. High-utility itemset mining incorporates item-specific weights (profit margin, strategic importance) into the mining process. A rule involving a high-margin item is more valuable than an equally supported rule involving a low-margin item. Published in ACM Computing Surveys. This is the theoretical framework for business-weighted rule mining.

Textbooks

18. Introduction to Data Mining, Chapter 6 --- Pang-Ning Tan, Michael Steinbach, and Vipin Kumar (2005, 2nd edition 2019) Chapter 6 provides the most thorough textbook treatment of association rules: support, confidence, lift, the Apriori algorithm, FP-Growth, and interestingness measures. The 2nd edition includes updated examples and a discussion of scalability. The treatment is more mathematical than this chapter but includes proofs of the downward closure property and formal analysis of algorithmic complexity.

19. Data Mining: Concepts and Techniques, Chapters 6-7 --- Jiawei Han, Micheline Kamber, and Jian Pei (2011, 3rd edition) Han, Kamber, and Pei wrote the definitive data mining textbook. Chapters 6 and 7 cover frequent itemset mining (including the FP-Growth algorithm that Han co-invented), association rules, constraint-based mining, and sequential pattern mining. The treatment is comprehensive and includes pseudo-code for all major algorithms.

20. Machine Learning with Python Cookbook, Chapter 16 --- Chris Albon (2018) A practical cookbook-style reference that includes a short, code-focused treatment of association rules using mlxtend. Useful as a quick reference for the API calls, though it does not cover the theory in depth.

How to Use This List

If you read nothing else, read Agrawal and Srikant (item 2) for the Apriori algorithm and Han, Pei, and Yin (item 3) for FP-Growth. Together they cover the two foundational algorithms in the field.

If you need to choose between interestingness metrics, read Tan, Kumar, and Srivastava (item 6). Their comparison of 21 metrics on real data demonstrates that metric choice matters and provides a framework for making the choice systematically.

If you are scaling to large datasets, read Li et al. (item 7) and the Spark MLlib documentation (item 8). Single-machine mlxtend works up to roughly 1 million transactions; beyond that, distributed mining is necessary.

If you want to extend association rules to sequences, quantities, or weighted items, read Agrawal and Srikant (item 14) on sequential patterns, Srikant and Agrawal (item 16) on quantitative rules, and Tseng et al. (item 17) on high-utility mining. These extensions handle data that does not fit the standard binary-basket framework.

If you want the deepest textbook treatment, start with Tan, Steinbach, and Kumar Chapter 6 (item 18) and supplement with the original papers for specific algorithms.

This reading list supports Chapter 23: Association Rules and Market Basket Analysis. Return to the chapter to review concepts before diving in.