Associaton Analysis: From Binary Tables to the Apriori Algorithm
A step-by-step breakdown of how transaction data is evaluated, pruned, and transformed into actionable rules.
Before running market basket analysis or finding association rules, raw receipts need to be turned into a clean, organized table. As shown in the “From Receipts to a Binary Table” slide, each row stands for a transaction (T1 through T10) and each column represents a specific product (like Coffee, Muffin, Sandwich, Juice, or Salad). Instead of tracking complicated details like item counts, prices, or order, the table uses a simple binary system: a 1 means the item was bought, and a 0 means it wasn't. This makes counting frequencies straightforward—showing that Coffee appears in 7 transactions and Muffins in 6—which sets up a solid, streamlined foundation for checking item co-occurrence and calculating support.
In Association Rule Mining, building effective analytical models requires understanding how itemsets form directional rules. A collection containing k items is known as a k-itemset, such as {Coffee, Muffin} forming a 2-itemset or {Coffee, Muffin, Sandwich} forming a 3-itemset. An association rule connects these itemsets in an “IF-THEN” structure (X -> Y), where antecedent X and consequent Y are disjoint sets, such as {Sandwich, Coffee} implying {Muffin}. Order matters in these conditions, meaning the rule X -> Y is distinct from Y -> X. Crucially, the implying arrow records statistical co-occurrence rather than direct causation, indicating how items appear together in baskets rather than proving that buying X explicitly causes a customer to purchase Y.
As demonstrated, single items are evaluated across 10 sample baskets — showing Coffee appearing with the highest support at 0.70, down to Salad at 0.30. The metric extends seamlessly to itemsets, such as {Coffee}, {Muffin} appearing in 6 out of 10 baskets {support} = 0.60), and {Coffee},{Muffin}, {Sandwich} appearing in 3 baskets {support} = 0.30. Ultimately, support is crucial because it filters out random coincidences and uninteresting rules, ensuring that downstream algorithms like Apriori only focus on relationships anchored by statistically significant purchasing volume.
While support measures how frequently items appear together, confidence evaluates the reliability or strength of an association rule by calculating the conditional probability of buying item Y given that item X is already in the basket. Defined as confidence(X -> Y) = support(X U Y) / support(X), this metric estimates P(Y | X) and is strictly directional, meaning that rule X -> Y is not equal to rule Y -> X. Examining the same pair of items yields different confidence scores due to changing denominators: Muffin -> Coffee achieves a confidence of 1.00 (0.60 / 0.60) because every transaction containing a muffin also includes a coffee, whereas Coffee -> Muffin drops to 0.86 (0.60 / 0.70) because coffee is bought more frequently overall. Comparing other café rules shows Sandwich -> Coffee at 0.80 and Sandwich -> Muffin at 0.60, demonstrating how confidence helps marketers and data analysts determine how predictably one purchase leads to another.
While confidence shows rule reliability, lift measures whether items are truly associated or if their co-occurrence is merely a coincidence driven by high individual item popularity. Calculated as lift(X -> Y) = confidence(X -> Y) / support(Y) or support(X U Y) / (support(X) * support(Y)), lift controls for baseline probabilities to determine if items are bought together more often than expected by random chance. A lift value greater than 1 indicates a strong positive association (items are bought together more than chance), equal to 1 implies independence, and less than 1 reveals a negative association (items avoid each other). The rule Salad -> Juice yields a high lift of 2.50 (1.00 / 0.40), highlighting a powerful positive link. Conversely, Sandwich -> Muffin results in a lift of 1.00 (0.60 / 0.60), proving those items are independent despite having a seemingly high 60% confidence score, while Coffee -> Juice drops to a lift of 0.36 (0.143 / 0.40), exposing a true negative association.
To synthesize all three metrics, evaluating association rules side by side provides a complete picture of product relationships by balancing frequency, directional probability, and true statistical correlation. Comparing rules across support, confidence, and lift highlights two essential insights. First, lift is symmetric while confidence is not — for instance, Muffin -> Coffee and Coffee -> Muffin share the same support (0.60) and positive lift (1.43), yet differ in confidence (1.00 vs. 0.86) due to varying baseline item frequencies. Similarly, Salad -> Juice and Juice -> Salad both demonstrate a strong positive lift of 2.50, but feature different confidence scores (1.00 vs. 0.75). Second, a rule can display high confidence purely because the target item is globally popular, as seen with Sandwich -> Coffee (confidence 0.80, lift 1.14) and Sandwich -> Muffin (confidence 0.60, lift 1.00, indicating complete independence). Conversely, Coffee -> Juice yields a lift of only 0.36, confirming a clear negative association where customers actively avoid buying the two together. Ultimately, high confidence paired with a lift near 1 simply signals a popular product rather than a meaningful cross-selling link.
While standard metrics like support, confidence, and lift provide a strong foundation for association rule mining, advanced evaluation often requires looking at leverage and conviction to gain deeper insights into item relationships. Support filters out rare coincidences, confidence estimates rule reliability, and lift measures strength relative to chance (with a neutral value of 1). Moving beyond lift, leverage measures the absolute difference between the observed co-occurrence frequency and expected co-occurrence under independence; for instance, the rule Sandwich -> Coffee achieves a leverage of 0.40 — (0.50 * 0.70) = 0.05, demonstrating that 5% of all baskets contain this combination beyond what chance alone would predict. Meanwhile, conviction measures the directional dependency of a rule by comparing how often X occurs without Y against expected independence; for Sandwich -> Coffee, the conviction of (1–0.70) / (1–0.80) = 1.5 indicates that if Sandwich and Coffee were truly independent, the rule would be incorrect 1.5 times as often. Together, leverage and conviction refine association evaluation by isolating true incremental impact and measuring directional error rates.
To efficiently mine association rules from transactional datasets, algorithms typically employ a structured two-stage strategy. As illustrated in the slide titled “A Two-Stage Strategy,” the workflow begins with raw transactions consisting of multiple baskets and items, moving first into Stage 1 to identify frequent itemsets by retaining only those that meet or exceed a user-defined minimum support threshold (minsup). This initial stage is computationally heavy and dominates the process because candidate counting is where the combinatorial explosion occurs. Stage 2 then handles rule generation by splitting the frequent itemsets and keeping rules that satisfy a minimum confidence threshold (minconf), which is much faster since all rules originating from the same itemset share its support and require checking it only once. Ultimately, this process yields a final set of rules ranked by lift, governed by two user-defined thresholds where minsup prunes itemsets and minconf prunes rules.
To solve the computational bottleneck of searching through massive combinations of items, the Apriori algorithm relies on a logical shortcut known as the Apriori principle, which states that a whole is never more common than its parts. As illustrated in the slide titled The Apriori Principle, given a minimum support threshold of 3 out of 10 baskets, the lattice structure maps relationships from single items up to larger itemsets. By using this rule, any subset of a frequent itemset must also be frequent, and conversely, any superset containing an infrequent subset can be safely pruned without ever scanning the transaction data. For instance, once pairs like CJ, MJ, and SJ are identified as infrequent, higher-level combinations branching from them are immediately pruned and never counted, transforming an otherwise explosive combinatorial search into a manageable and efficient process.
To execute the itemset discovery process efficiently, the Apriori algorithm follows a systematic five-step iterative loop as outlined in the slide titled The Apriori Loop, Step by Step. The process begins in step one by counting individual items and keeping those that meet the minimum support threshold, followed in step two by joining pairs from the previous frequent set to form new candidate itemsets using a shared prefix to prevent duplicates. Step three prunes away candidates containing infrequent subsets, while step four scans the transaction baskets to count the remaining survivors. Finally, step five filters these counts to retain the frequent itemsets for that level, stopping if the result is empty or incrementing k to repeat the loop, ensuring that the algorithm performs only one data scan per level
The first pass of the Apriori algorithm evaluates individual items to determine which ones meet the minimum support threshold required for further analysis. Every item with a support value greater than or equal to minsup survives into the initial frequent 1-itemset (F1), keeping in mind the rule of thumb that the exact threshold value itself counts as frequent. When evaluating items across ten transactions — such as Coffee (0.70), Muffin (0.60), Sandwich (0.50), Juice (0.40), and Salad (0.30) — all five items qualify if minsup is set to 0.30, generating 10 potential candidate pairs (5 choose 2) for the next stage. However, raising minsup to 0.40 drops Salad, immediately eliminating four potential pairs before they are ever counted and significantly reducing downstream computational effort.
During the second pass of the mining process, candidate pairs of items are evaluated against the minimum support threshold to generate the frequent 2-itemset. Pairs meeting or exceeding the threshold are retained, such as coffee and muffin with a support of 0.60, coffee and sandwich at 0.40, and muffin and sandwich alongside juice and salad at 0.30. Conversely, pairs failing to reach the required support level are dropped, revealing underlying customer behavior patterns. For instance, nearly all juice combinations appear in only a single basket, indicating that juice drinkers form a distinct and separate consumer group compared to the core bakery shoppers.
Once frequent itemsets are identified, the next stage is generating association rules by splitting the itemsets into antecedents and consequents. A k-itemset produces 2^k — 2 candidate rules, meaning a 3-itemset like {Coffee, Muffin, Sandwich} yields 6 possible rules to test. Applying a minimum confidence threshold (such as 0.70) prunes weaker predictions. For instance, rules like Muffin, Sandwich -> Coffee (confidence 1.00, lift 1.43) and Coffee, Sandwich -> Muffin (confidence 0.75, lift 1.25) meet the standard and are kept, while rules with broader consequents fall below the threshold and are dropped. This filtering relies on rule-level pruning: moving items from the antecedent into the consequent can only decrease a rule’s confidence score.
While the Apriori algorithm provides a simple and intuitive foundation using level-wise candidate generation and anti-monotone subset pruning, it suffers from requiring multiple database scans and large candidate sets at low minimum support thresholds. To overcome these computational bottlenecks, alternative algorithms like FP-Growth and Eclat offer powerful search improvements while ultimately returning the exact same frequent itemsets. FP-Growth compresses transactional data into a compact FP-tree structure, enabling frequent itemset mining entirely without candidate generation through just two database scans, though the resulting tree can become large and complex to implement. Meanwhile, Eclat takes a vertical layout approach by intersecting transaction-id lists to perform rapid support counting via fast set intersections, making it highly efficient unless the dataset is dense enough to cause transaction ID lists to grow excessively large.
Association analysis transforms basic transactional counting into actionable evidence when evaluation metrics are interpreted with care. The core process relies on support to filter out random coincidences, confidence to gauge rule reliability, and lift to test associations against chance. To keep the computational workload manageable, the Apriori principle prunes the search lattice so that candidate mining can finish efficiently. Analysts must judge these findings by checking lift, setting thresholds deliberately, and treating the resulting rules as testable hypotheses. Looking ahead, the analytical framework transitions from simple association toward proving actual effects using sequential patterns and A/B testing.
Get Centenoaidan’s stories in your inbox
Join Medium for free to get updates from this writer.
References
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (pp. 207–216). ACM. https://doi.org/10.1145/170035.170072
Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases (pp. 487–499). Morgan Kaufmann.
Brin, S., Motwani, R., Ullman, J. D., & Tsur, S. (1997). Dynamic itemset counting and implication rules for market basket data. ACM SIGMOD Record, 26(2), 255–264. https://doi.org/10.1145/253262.253325
Hahsler, M., Grün, B., & Hornik, K. (2005). arules: A computational environment for mining association rules and frequent item sets. Journal of Statistical Software, 14(15), 1–25. https://doi.org/10.18637/jss.v014.i15
Han, J., Pei, J., & Tong, H. (2022). Data mining: Concepts and techniques (4th ed.). Morgan Kaufmann.
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12. https://doi.org/10.1145/335191.335372
Linden, G., Smith, B., & York, J. (2003). Amazon.com recommendations: Item-to-item collaborative filtering. IEEE Internet Computing, 7(1), 76–80. https://doi.org/10.1109/MIC.2003.1167344
Piatetsky-Shapiro, G. (1991). Discovery, analysis, and presentation of strong rules. In G. Piatetsky-Shapiro & W. J. Frawley (Eds.), Knowledge discovery in databases (pp. 229–248). AAAI Press/MIT Press.
Raschka, S. (2018). MLxtend: Providing machine learning and data science utilities and extensions to Python’s scientific computing stack. Journal of Open Source Software, 3(24), 638. https://doi.org/10.21105/joss.00638
Srivastava, J., Cooley, R., Deshpande, M., & Tan, P.-N. (2000). Web usage mining: Discovery and applications of usage patterns from web data. ACM SIGKDD Explorations Newsletter, 1(2), 12–23. https://doi.org/10.1145/846183.846188
Tan, P.-N., Kumar, V., & Srivastava, J. (2004). Selecting the right objective measure for association analysis. Information Systems, 29(4), 293–313. https://doi.org/10.1016/S0306-4379(03)00072-3
Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2019). Introduction to data mining (2nd ed.). Pearson.
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390. https://doi.org/10.1109/69.846291
