What association rule learning is

Association rule learning looks for patterns like:

• {bread, butter} → {milk}{bread, butter} → {milk}

which reads as “shoppers who buy bread and butter also tend to buy milk.” The classic use case is market basket analysis: mining a store’s receipts to find which products tend to appear together, so you can bundle them, place them near each other, or recommend one when a customer adds the other to their cart.

This is a different flavor of unsupervised learning from clustering or anomaly detection. Instead of grouping instances (customers, transactions), it groups items and looks for co-occurrence patterns across many transactions.

Key metrics

Everything starts from support — how common something is — and builds up to confidence and lift, which score a candidate rule.

Support

How often an itemset appears across all transactions:

• support({A, B})support({A, B}) = fraction of transactions containing both A and B

Confidence

How often B shows up, given that A already did:

• confidence(A -> B) = support({A, B}) / support({A})confidence(A -> B) = support({A, B}) / support({A})

Lift

How much more likely B is when A happens, compared to B’s overall baseline rate:

• lift(A -> B) = confidence(A -> B) / support({B})lift(A -> B) = confidence(A -> B) / support({B})

lift > 1lift > 1 means A and B genuinely co-occur more than chance would predict. lift == 1lift == 1 means they’re independent — B is just as likely whether or not A happened, so the rule isn’t actually telling you anything useful, no matter how high its confidence looks. lift < 1lift < 1 means A and B are negatively correlated — buying A makes B less likely.

From itemset to rule

A single frequent itemset like {bread, butter}{bread, butter} can generate more than one rule, depending on which item you put on the left (antecedent) vs. the right (consequent). Each direction gets scored independently:

  flowchart LR
  I["Frequent itemset
{bread, butter}"] --> R1["Rule: bread -> butter"]
  I --> R2["Rule: butter -> bread"]
  R1 --> M1["confidence(bread->butter)
lift(bread->butter)"]
  R2 --> M2["confidence(butter->bread)
lift(butter->bread)"]

Apriori idea

Checking every possible itemset is exponential in the number of products, so the Apriori algorithm prunes the search using one key rule:

• if an itemset is frequent, every one of its subsets must also be frequent
• (equivalently) if an itemset is infrequent, every superset of it is infrequent too — no point in even counting it

That lets Apriori build up frequent itemsets level by level — first single items, then pairs, then triples — throwing away anything that couldn’t possibly be frequent before it even bothers counting it.

  flowchart TD
  A["Find frequent 1-itemsets"] --> B["Generate candidate 2-itemsets"]
  B --> C["Prune infrequent"]
  C --> D["Generate candidate 3-itemsets"]
  D --> E["Repeat until no more frequent itemsets"]

Computing it by hand

transactions = [
    {"milk", "bread", "butter"},
    {"bread", "butter"},
    {"milk", "bread"},
    {"milk", "bread", "butter", "eggs"},
    {"bread", "eggs"},
]
 
 
def support(itemset):
    itemset = set(itemset)
    hits = sum(1 for t in transactions if itemset.issubset(t))
    return hits / len(transactions)
 
 
def confidence(antecedent, consequent):
    return support(antecedent | consequent) / support(antecedent)
 
 
def lift(antecedent, consequent):
    return confidence(antecedent, consequent) / support(consequent)
 
 
sup_bb = support({"bread", "butter"})
conf = confidence({"bread"}, {"butter"})
lft = lift({"bread"}, {"butter"})
 
print("support(bread, butter):", round(sup_bb, 2))
print("confidence(bread -> butter):", round(conf, 2))
print("lift(bread -> butter):", round(lft, 2))

transactions = [
    {"milk", "bread", "butter"},
    {"bread", "butter"},
    {"milk", "bread"},
    {"milk", "bread", "butter", "eggs"},
    {"bread", "eggs"},
]
 
 
def support(itemset):
    itemset = set(itemset)
    hits = sum(1 for t in transactions if itemset.issubset(t))
    return hits / len(transactions)
 
 
def confidence(antecedent, consequent):
    return support(antecedent | consequent) / support(antecedent)
 
 
def lift(antecedent, consequent):
    return confidence(antecedent, consequent) / support(consequent)
 
 
sup_bb = support({"bread", "butter"})
conf = confidence({"bread"}, {"butter"})
lft = lift({"bread"}, {"butter"})
 
print("support(bread, butter):", round(sup_bb, 2))
print("confidence(bread -> butter):", round(conf, 2))
print("lift(bread -> butter):", round(lft, 2))

support(bread, butter): 0.6
confidence(bread -> butter): 0.6
lift(bread -> butter): 1.0

support(bread, butter): 0.6
confidence(bread -> butter): 0.6
lift(bread -> butter): 1.0

Interesting result: bread -> butterbread -> butter has decent confidence (60%), but its lift is exactly 1.01.0. That’s because breadbread shows up in every single transaction — so knowing someone bought bread tells you nothing extra about whether they’ll also buy butter. Compare that to the other direction:

transactions = [
    {"milk", "bread", "butter"},
    {"bread", "butter"},
    {"milk", "bread"},
    {"milk", "bread", "butter", "eggs"},
    {"bread", "eggs"},
]
 
 
def support(itemset):
    itemset = set(itemset)
    hits = sum(1 for t in transactions if itemset.issubset(t))
    return hits / len(transactions)
 
 
def confidence(antecedent, consequent):
    return support(antecedent | consequent) / support(antecedent)
 
 
print("confidence(butter -> bread):", round(confidence({"butter"}, {"bread"}), 2))

transactions = [
    {"milk", "bread", "butter"},
    {"bread", "butter"},
    {"milk", "bread"},
    {"milk", "bread", "butter", "eggs"},
    {"bread", "eggs"},
]
 
 
def support(itemset):
    itemset = set(itemset)
    hits = sum(1 for t in transactions if itemset.issubset(t))
    return hits / len(transactions)
 
 
def confidence(antecedent, consequent):
    return support(antecedent | consequent) / support(antecedent)
 
 
print("confidence(butter -> bread):", round(confidence({"butter"}, {"bread"}), 2))

confidence(butter -> bread): 1.0

confidence(butter -> bread): 1.0

Every transaction with butter also had bread — 100% confidence. butter -> breadbutter -> bread is the far more useful rule here, even though the raw support of the itemset is identical either way. This is exactly why you always report confidence and lift alongside support: support alone can’t tell you which direction of a rule is meaningful.

Practical note

Apriori is often implemented with specialized libraries (e.g., mlxtendmlxtend) for real datasets with thousands of items, since level-wise candidate generation gets expensive fast. You can learn — and even prototype — the concepts without installing anything, as shown above.

Mini-checkpoint

If a rule has confidence 0.9 but lift 1.0, what does that mean?

• It’s not actually more informative than the baseline — B is just common anyway, regardless of A.

🧪 Try It Yourself

Exercise 1 – Compute Support

Exercise 2 – Compute Confidence

Exercise 3 – Compute Lift and Spot a Weak Rule

Next

That wraps up the clustering, anomaly-detection, and association-rule side of Phase 6. Head back to Introduction to Clustering if you want to revisit how unlabeled data gets grouped in the first place, or continue to Principal Component Analysis (PCA) — the dimensionality-reduction topics that round out this phase.