Practical 9: Association Rule Mining with Apriori

Reading the passes

Pass 1 counts the five items. geometry-box appears in one basket out of twelve, support 0.083, and is dropped. Everything else survives.

Pass 2 builds six pairs from the four surviving singles, which is 4 choose 2, and drops {calculator, highlighter} at 0.167. Note what is not there: no pair containing geometry-box was ever built, because the Apriori rule says a pair cannot be frequent if one of its items is not.

Pass 3 is where the saving shows. Five frequent pairs can be joined into several triples, but only two candidates appear, {calculator, notebook, pen} and {highlighter, notebook, pen}, because those are the only triples all three of whose pairs survived pass 2. A triple containing {calculator, highlighter} would have been built by a naive program and counted for nothing. One of the two is then dropped on its own support and the other, at 0.417, is kept.

Pass 4 finds no candidates at all and the loop stops. Ten frequent itemsets in total: four singles, five pairs and one triple.

Interpreting the rules, which is the third thing MU asks for

Every frequent itemset of two or more items yields rules, one for each way of cutting it into a left and a right side. The nine that reach a confidence of 0.70 are in the table. Read three of them.

{highlighter} -> {pen}: support 0.583, confidence 0.875, lift 1.050. Seven of the eight baskets with a highlighter also had a pen. The lift is just above 1, so a highlighter does make a pen a little more likely than average, but only a little: pens are in 10 of the 12 baskets anyway.

{notebook, pen} -> {highlighter}: support 0.417, confidence 0.714, lift 1.071. The highest lift in the table. Somebody buying both a notebook and a pen is the most likely of anybody to add a highlighter, and this is the rule a shopkeeper would act on.

{calculator} -> {pen}: support 0.333, confidence 0.800, lift 0.960. Here is the trap, and it is the reason this section exists. A confidence of 0.800 looks strong and the rule is worthless. Four of the five calculator baskets also had a pen, which sounds compelling until you notice that pens are in 0.833 of all baskets. So a calculator buyer is slightly less likely to buy a pen than a random customer is, and the lift of 0.960 says exactly that. Acting on this rule, putting the pens next to the calculators, would be acting on nothing.

{highlighter, notebook} -> {pen}: confidence 0.833, lift 1.000. Exactly 1. Perfect independence: knowing about the highlighter and notebook changes the chance of a pen not at all.

So the interpretation, in the form to write in the journal: rank by lift, filter by support and confidence. Support says the rule is worth caring about because it happens often enough; confidence says it holds up when it happens; lift says it is telling you something you did not already know.

Two honest warnings about small data

Twelve baskets is enough to demonstrate the algorithm and far too few to believe the rules. A support of 0.25 is three baskets. One more or one fewer moves it by 0.083, and several of the rules above would change places. A real market-basket study runs to tens of thousands of transactions, and a write-up here should say plainly how many baskets the figures came from.

And geometry-box was dropped at pass 1, so no rule involving it can ever be found however strong it might be. That is what a minimum support threshold does: it buys speed by refusing to look at anything rare. A rare but valuable pattern is invisible to Apriori, and the threshold is a choice, not a fact.

Procedure

1. Write the transactions, one per line, and read them into sets.
2. Choose a minimum support and a minimum confidence, and say what the support means in baskets.
3. Count the support of every single item; keep the frequent ones and print which were dropped.
4. Build pairs from the frequent singles; count and keep. Print the candidates as well as the survivors, so the reader can see what was counted.
5. Build triples only from candidates every subset of which was frequent, and say how many candidates that rule saved.
6. Stop when a pass produces no candidates.
7. For every frequent itemset of two items or more, generate a rule for each way of splitting it, and compute support, confidence and lift.
8. Sort by confidence, apply the minimum, and interpret at least three rules in English, including one whose lift is below 1.

Observations

Result

Apriori was implemented and run over twelve transactions with a minimum support of 0.25 and a minimum confidence of 0.70. It found ten frequent itemsets in four passes: four single items, five pairs and one triple. The Apriori property reduced pass 3 to two candidates, because those were the only triples every pair of which had survived pass 2. Nine rules met the confidence threshold. The highest lift, 1.071, belongs to notebook and pen implying highlighter; the rule calculator implying pen has a confidence of 0.800 and a lift of 0.960, meaning a calculator buyer is slightly less likely than an average customer to buy a pen, and two rules have a lift of exactly 1.000, meaning their two sides are independent.

Where marks are lost

Reporting confidence without lift. The 0.800-confidence rule above is worthless and only lift says so.

Building candidates without the Apriori check. The program is then brute force wearing Apriori's name. Show the candidate counts so the saving is visible.

Mixing up support and confidence. Support is out of all the baskets. Confidence is out of the baskets containing the left side only.

Generating rules from the infrequent itemsets. Rules come from the frequent ones only, which is why the frequent itemsets are found first.

Forgetting the one-item rules. An itemset of three items yields six rules, not two: three with a single item on the left and three with a pair.

Using a list where a set is needed. Membership and subset tests on sets are what make this readable and fast.

Not saying how many transactions there were. Twelve baskets is a demonstration, not evidence.

Setting the minimum support after looking at the answers. Choose it first and say why.

For the journal

Aim; support, confidence and lift each defined with a formula; the Apriori property in one sentence, both ways round; the transactions; the pass-by-pass output showing every candidate and whether it was kept; the count of frequent itemsets; the rule table with all three measures; at least three rules interpreted in English, one of them with lift below 1; the two observation tables; the result; a sentence on what a minimum support threshold makes invisible.

Quick revision

• Association rule mining is unsupervised: no labels, only patterns.
• Support of X: the fraction of all baskets containing X.
• Confidence of X implying Y: support of X and Y together, divided by support of X.
• Lift: confidence divided by the support of Y. Above 1 informative, 1 independent, below 1 discouraging.
• The Apriori property: every subset of a frequent itemset is frequent.
• So a candidate with any infrequent subset is never counted. That is the whole saving.
• Pass k builds its candidates by joining frequent itemsets of size k minus 1.
• Stop when a pass yields no candidates.
• An itemset of size n yields 2^n - 2 rules.
• A high confidence with a lift below 1 is a rule worth ignoring.
• A minimum support threshold makes rare patterns invisible, by design.

Questions you must be able to answer

1. What is support, and out of what? The fraction of all the transactions that contain the itemset. Out of every basket, not just the relevant ones.

2. What is confidence, and how is it different? Of the baskets that contain the left side of the rule, the fraction that also contain the right side. Its denominator is the left side's support, not the total.

3. What is lift, and why does it matter? Confidence divided by the support of the right side. It says whether the left side actually makes the right side more likely. In this run one rule had confidence 0.800 and lift 0.960, so the rule is worse than guessing.

4. State the Apriori property. Every subset of a frequent itemset is itself frequent. Equivalently, if any subset of a candidate is infrequent, the candidate is infrequent and need not be counted.

5. Where did that property save work in your run? In pass 3: only two triples were built out of the five frequent pairs, because those were the only ones all of whose pairs had survived pass 2.

6. How many rules come out of a frequent itemset of three items? Six: three with one item on the left and two on the right, and three the other way round. In general 2 to the power n, minus 2.

7. Your algorithm found no rule involving geometry-box. Why? It appeared in one basket of twelve, support 0.083, below the minimum of 0.25, so it was dropped in pass 1 and no itemset containing it was ever built.

8. Two of your rules have a lift of exactly 1.000. What does that mean? That the two sides are independent: knowing the left side changes the chance of the right side not at all. The rule is true and useless.

9. Would you act on the rule from calculator to pen? No. Its confidence of 0.800 only reflects that pens are in 0.833 of all baskets anyway; its lift of 0.960 says a calculator buyer is slightly less likely than average to buy a pen.

10. What would you change before trusting any of these rules? The number of transactions. Twelve baskets means one basket is 0.083 of support, so most of these figures are within a basket or two of each other.