Association Rules: Finding Which Items Turn Up Together
An association rule is an if-then statement that reports a relationship between items recorded in the same transaction.
The antecedent is the "if" part, the item or set of items that triggers the rule.
The consequent is the "then" part, the item or set of items that tends to appear alongside it.
Association rule learning is unsupervised, since nothing in the data is labelled and the algorithm is searching for co-occurrence rather than predicting a target.
Example
In a supermarket data set a rule might read: if a customer buys bread and butter, then they are likely to buy milk.
Written in the usual notation that is {bread, butter} $\Rightarrow$ {milk}.
The rule says nothing about why the pattern exists, only that the items keep appearing together.
The Three Metrics That Decide Whether a Rule Is Worth Anything
Support measures how often the itemset appears at all, as a share of every transaction. $$\text{Support}(A) = \frac{\text{transactions containing } A}{\text{total transactions}}$$
Low support means the rule rests on too few cases to trust.
Confidence measures how often the consequent appears when the antecedent does.
$$\text{Confidence}(A \Rightarrow B) = \frac{\text{Support}(A \cup B)}{\text{Support}(A)}$$
High confidence on its own can still be misleading if the consequent is simply a very common item.
Lift compares the rule against what you would expect from chance alone. $$\text{Lift}(A \Rightarrow B) = \frac{\text{Confidence}(A \Rightarrow B)}{\text{Support}(B)}$$
A lift above 1 means buying $A$ genuinely raises the chance of buying $B$, a lift of 1 means the two are independent, and a lift below 1 means $A$ makes $B$ less likely.
Example
Calculating the Three Metrics on 200 Transactions
A shop records 200 baskets. Bread appears in 100 of them, milk in 120, and bread and milk together in 80.
Support for {bread, milk} is $80 / 200 = 0.40$, so the pair appears in 40% of baskets.
Support for {bread} alone is $100 / 200 = 0.50$.
Confidence for {bread} $\Rightarrow$ {milk} is $0.40 / 0.50 = 0.80$, so 80% of bread buyers also bought milk.
Support for {milk} alone is $120 / 200 = 0.60$.
Lift is $0.80 / 0.60 = 1.33$, so a bread buyer is about a third more likely to buy milk than a random shopper is.
The rule survives all three tests: it covers enough baskets, it holds most of the time, and it beats chance.
Reading a Rule That Fails the Lift Test
Suppose 90% of all baskets contain a carrier bag, and 90% of baskets containing coffee also contain a carrier bag.
Confidence for {coffee} $\Rightarrow$ {carrier bag} is 0.90, which looks impressive on its own.
Support for {carrier bag} is also 0.90, so lift is $0.90 / 0.90 = 1.00$.
The rule is worthless, because coffee buyers are no more likely to take a bag than anyone else, and only lift exposes that.
Common Mistake
Confidence alone rewards popular items, so the highest-confidence rules in a data set are often the least useful.
Always report lift alongside confidence when judging a rule.
A rule can also be statistically strong and still trivial, such as "customers who buy bread also buy food".
The Apriori Algorithm
Apriori is the standard method for finding frequent itemsets and turning them into rules.
Set the thresholds for minimum support and minimum confidence before starting.
Find the frequent single items, keeping only those that meet the minimum support.
Build larger itemsets by combining frequent smaller ones, then check each against the support threshold again.
Generate rules from every frequent itemset and calculate the confidence of each.
Prune the rules that fall below the confidence threshold.
Why Apriori Prunes Early
The number of possible itemsets grows explosively with the number of distinct products, so testing all of them is impossible in a real shop.
Apriori relies on one observation: if an itemset is infrequent, every larger set containing it must also be infrequent.
So once {caviar} falls below minimum support, the algorithm never wastes time testing {caviar, bread} or {caviar, milk}.
That single rule is what makes the search tractable on data sets with thousands of products.
Note
The choice of minimum support is a judgement call with real consequences.
Set it high and you find only the obvious pairings you already knew about.
Set it low and the algorithm returns thousands of rules, most of which are noise.
Where Association Rules Are Used
Market basket analysis is the original application, where retailers use the rules to decide shelf layout, bundle offers and which products to place near the till.
Crime analysis is the scenario the syllabus names, where the rules might show that areas with high rates of vandalism also see frequent theft, which helps a force allocate patrols.
Medical research applies the same method to case records to surface symptoms and conditions that keep occurring together.
Recommendation systems use frequent itemsets to build the "customers also bought" panel.
Common Mistake
An association rule shows correlation and never proves causation.
Vandalism and theft occurring together does not mean one causes the other, since both may follow from a third factor such as low street lighting.
Reading a rule as a cause is the most common analytical error in this topic.
The Ethical Weight of Predictive Policing
Rules mined from crime records reflect where the police already went, not where crime necessarily happened.
Directing more patrols to those areas produces more recorded incidents there, which strengthens the rule on the next run.
That feedback loop can entrench over-policing of specific communities while the recorded data appears to justify it.
The practical safeguard is to check whether the input data represents the whole population before acting on any rule drawn from it.
Active recall
Define antecedent and consequent, using an example rule of your own.
Write the formulas for support, confidence and lift.
In 500 transactions, tea appears in 200, biscuits in 250, and both together in 120. Calculate the confidence and lift of {tea} $\Rightarrow$ {biscuits}.
What does a lift value of exactly 1 tell you about a rule?
Which property of infrequent itemsets lets Apriori avoid testing most combinations?
Explain one ethical problem with using association rules on crime data.
