Association Rule Mining in Market Basket Analysis

Definition. Market basket analysis discovers associations among sets of items that frequently occur together in customer transactions. An association rule has the form $X \to Y$, where $X$ (antecedent) and $Y$ (consequent) are disjoint itemsets.

1. Key measures

• Support: $\text{sup}(X \to Y) = \frac{\text{transactions containing } X \cup Y}{\text{total transactions}}$ — how often the combination occurs.
• Confidence: $\text{conf}(X \to Y) = \frac{\text{sup}(X \cup Y)}{\text{sup}(X)}$ — how often the rule is correct when $X$ appears.
• Lift: $\text{lift} = \frac{\text{conf}(X \to Y)}{\text{sup}(Y)}$ — lift above 1 means the items are positively correlated, 1 means independence, below 1 negative correlation.

A rule is interesting when support, confidence and lift all exceed the thresholds $\text{min-sup}$, $\text{min-conf}$.

2. How rules are found: Apriori and FP-growth

1. Scan transactions and keep items with $\text{sup} \ge \text{min-sup}$ (frequent 1-itemsets).
2. Join frequent $k$-itemsets to form candidate $(k{+}1)$-itemsets.
3. Apriori principle (anti-monotone support): any superset of an infrequent itemset is also infrequent, so candidates can be pruned safely.
4. Rescan, repeat until no more frequent itemsets.
5. Generate rules from frequent itemsets and keep those with $\text{conf} \ge \text{min-conf}$.

FP-growth avoids repeated scans by compressing the database into an FP-tree and mining it recursively.

3. Worked mini-example

Six supermarket transactions, $\text{min-sup} = 0.4$, $\text{min-conf} = 0.6$:

Transaction	Items
T1	bread, butter
T2	bread, butter
T3	bread, milk
T4	butter, jam
T5	bread, butter, milk
T6	jam, milk

• $\text{sup}(\{\text{bread}\}) = 4/6 = 0.67$, $\text{sup}(\{\text{butter}\}) = 4/6 = 0.67$, $\text{sup}(\{\text{bread}, \text{butter}\}) = 3/6 = 0.50$.
• $\text{conf}(\text{bread} \to \text{butter}) = 0.50 / 0.67 = 0.75 \ge 0.60$ $\Rightarrow$ rule accepted.
• $\text{lift} = 0.75 / 0.67 = 1.125 > 1$, so bread and butter are positively associated.
• By contrast $\text{conf}(\text{milk} \to \text{butter}) = (1/6)/(3/6) = 0.33 < 0.60$, so that rule is rejected.

4. How businesses use this for sales strategy

1. Cross-selling and up-selling: recommendations such as customers who bought X also bought Y on product pages and in emails.
2. Store layout and shelf placement: complementary items (bread and butter, chips and beer) placed near each other to raise basket size.
3. Bundling and pricing: itemsets with high lift become combo offers and discount coupons.
4. Promotion planning: discount the antecedent to drive sales of the profitable consequent.
5. Catalogue and website design: group associated products in the same section or recommendation carousel.
6. Personalisation: rules feed recommendation engines and targeted campaigns, improving conversion and customer retention.
7. Inventory and shelf stocking: high-support bundles inform reorder quantities and planogram decisions.

Conclusion: association rule mining turns raw transaction logs into actionable if-then knowledge; by filtering on support, confidence and lift, businesses identify genuinely complementary products and use them to lift cross-sales, basket value and stock efficiency.