A4.3.5 · Machine learning approaches
Association rules
By the end you can
Describe how rules such as “bread and butter” are found in large data sets, and calculate support, confidence and lift.
Supermarkets noticed long ago that customers who buy nappies often buy something else on the same trip. Finding patterns like this by hand in millions of receipts is impossible; does it automatically. The output is a set of rules of the form if X then Y, where X and Y are : groups of items such as {bread} and {butter}. The “if” side of a rule is its antecedent and the “then” side is its consequent, and either can hold several items, as in {bread, milk} → {butter}. No item is labelled in advance, so this is unsupervised learning.
Three numbers: support, confidence and lift#
| Measure | Formula | Reads as |
|---|---|---|
| baskets containing the items ÷ all baskets | How common the combination is. | |
| support(X and Y) ÷ support(X) | Of the baskets with X, how many also have Y: how reliable the rule is. | |
| confidence(X → Y) ÷ support(Y) | How much more often Y turns up with X than it does anyway. |
Look at the ten baskets in the lab below. Bread appears in 7 of them, butter in 6, and both together in 5. For the rule bread → butter:
- Support of {bread, butter} = 5 ÷ 10 = 0.50.
- Confidence = 5 ÷ 7 = 0.71: about 71% of bread baskets also hold butter.
- Lift = 0.71 ÷ 0.60 = 1.19. Butter is in 60% of all baskets, so a confidence of 71% is only a little above chance.
This shows why confidence alone can mislead. A rule can have high confidence simply because the “then” item is bought by almost everyone. Lift corrects for that. Compare eggs → milk: confidence 0.75, but lift 1.25, a stronger association even though the support is lower.
Ten shopping baskets
- 1. bread, butter, milk
- 2. bread, butter
- 3. bread, milk, eggs
- 4. bread, butter, jam
- 5. milk, eggs
- 6. bread, butter, milk, eggs
- 7. milk, cereal
- 8. bread, jam
- 9. butter, milk
- 10. bread, butter, eggs
Support of the pair
0.50
5 of 10 baskets have both
Confidence
0.71
5 of the 7 baskets with bread also have butter
Lift
1.19
butter is in 6 of 10 baskets anyway (0.60)
Lift above 1 means the two items appear together more than chance would suggest. Lift of 1 means they are unrelated. Lift below 1 means buying one makes the other less likely.
Find all the rules that pass your thresholds
- eggs → milk: support 0.30, confidence 0.75, lift 1.25
- butter → bread: support 0.50, confidence 0.83, lift 1.19
- bread → butter: support 0.50, confidence 0.71, lift 1.19
- eggs → bread: support 0.30, confidence 0.75, lift 1.07
Finding the rules efficiently#
A shop with 10 000 products has far too many possible combinations to count every one. The algorithm saves effort with one observation: if an itemset is infrequent, any bigger set that contains it must be infrequent too. So:
- Set a minimum support and a minimum confidence. Count each single item and throw away those below the minimum support.
- Build pairs only from the survivors, count them, and discard those below the minimum support.
- Repeat with triples, and so on, until no bigger set is frequent.
- From each frequent set, form every possible rule and prune (discard) those below the minimum confidence. The survivors are then judged by lift; other measures such as conviction and leverage exist but are not needed here.
With minimum support 0.3 and minimum confidence 0.6, the ten baskets give 4 rules: eggs → milk (lift 1.25), butter → bread (lift 1.19), bread → butter (lift 1.19), eggs → bread (lift 1.07).
Where it is used, and its limits#
- Retail: shelf layout, bundles, “customers who bought this also bought…”.
- Medicine: finding symptoms or conditions that tend to occur together.
- Policing and security: spotting patterns of crimes that occur together, to plan where to patrol.
- Websites: pages or features that are used together.
- Finance: combinations of transaction features that often appear together in fraud.
Check yourself
Association rules
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
5 questions · 16 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Of 200 shopping baskets, 80 contain tea, 100 contain biscuits and 60 contain both. Calculate the support of {tea, biscuits}, the confidence of tea → biscuits and the lift of tea → biscuits.
[4]Calculate: Work out the number, showing the working.
2.Explain what a lift of (a) 1 and (b) 3 means for the rule “if a customer buys X, they buy Y”.
[3]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.Describe how the Apriori algorithm finds frequent itemsets.
[3]Describe: A detailed account: say what happens, step by step if it is a process.
4.Outline two real-world uses of association rule learning.
[3]Outline: A brief account: the main points, without much detail.
5.Distinguish between support and confidence.
[3]Distinguish: Make the differences between two things clear.
In a nutshell
- Association rule learning finds “if X then Y” patterns in transactions. It is unsupervised: nothing is labelled.
- Support = fraction of transactions containing the itemset. Confidence = support(X and Y) ÷ support(X). Lift = confidence ÷ support(Y).
- Lift above 1: positive association. Lift of 1: unrelated. Lift below 1: the items go together less than chance.
- Apriori counts single items, discards those below a minimum support, and builds bigger sets only from frequent smaller ones.
- Uses: market basket analysis, recommendations, finding conditions that occur together. A rule shows a pattern, not a cause.