# Apriori

> Every subset of a frequent itemset is frequent, so grow candidates level by level and prune any with an infrequent subset.

Source: https://www.mlfoundry.in/learn/apriori  
Section: ML Algorithms › Unsupervised · Association Rule Learning  
Level: core · 16 min read · updated 2026-10-07

**Apriori:** finds every **frequent itemset** in a database of transactions — every set of items that appears together in at least a fraction $\sigma$ of the baskets — by searching **level by level**: frequent 1-itemsets, then 2-itemsets built from them, then 3-itemsets, and so on. It then turns frequent itemsets into **association rules** $A \Rightarrow C$ such as *{Bread, Jam} ⇒ {Butter}*, kept when their confidence is high enough.

- **Task:** Unsupervised pattern mining: frequent itemsets and association rules
- **Input → output:** a list of transactions (sets of items) → all itemsets with support $\ge\sigma$, plus rules with confidence $\ge\gamma$
- **Learns:** no parameters — it enumerates patterns; the "model" is the list of itemsets and rules with their support, confidence and lift
- **Training cost:** one database scan per level; total work $\approx \sum_k |C_k|\cdot n$ subset tests — exponential in the worst case, practical when $\sigma$ keeps $|C_k|$ small
- **Prediction cost:** look up rules whose antecedent is contained in a basket: $O(\#\text{rules})$ subset checks, or a hash lookup
- **Hyperparameters:** minimum support $\sigma$, minimum confidence $\gamma$, maximum itemset length; ranking metric (lift, leverage, conviction)
- **Assumes:** items are binary (present / absent) — no quantities, no order; patterns worth knowing are frequent

## The problem

A shop logs millions of baskets and wants to know which products are bought **together** — to place them on the same shelf, bundle them, or recommend one when the other is in the cart. With $d$ products there are $2^d-1$ possible itemsets. Counting all of them is hopeless: for $d=100$ that is about $1.27\times10^{30}$ sets, and even the *pairs* alone for a 10,000-product catalogue number 49,995,000 — each one needing a pass over the data to count.

Supervised methods do not help: there is no label to predict, and we want *every* strong co-occurrence, not one decision function. What we need is an exact way to skip the overwhelming majority of itemsets **without counting them** — while still guaranteeing that every frequent one is found.

## The idea

If {Bread, Jam, Milk} appears in at least 3 baskets, then {Jam, Milk} certainly appears in at least those same 3 baskets — a basket that contains the bigger set contains every part of it. Turned around: **if {Jam, Milk} is rare, every set that contains it is at least as rare.** So once we learn that one small itemset is infrequent, we can delete its entire family of supersets from the search, unseen.

Apriori exploits this level by level. Count single items; keep the frequent ones. Build 2-item candidates **only** from frequent items; count them; keep the frequent ones. Build 3-item candidates only from frequent pairs — and before counting, throw away any candidate that has an infrequent pair inside it. Repeat until no candidates remain. Each level needs one scan of the database, and the name says it all: knowledge from the previous level is used *a priori* to prune the next.

**Vocabulary**

- **Item:** one product / event / token, e.g. Bread
- **Transaction (basket):** one set of items bought together, $t\subseteq I$; the database $D$ is a list of $n$ of them
- **Itemset, k-itemset:** any set of items $X\subseteq I$; a $k$-itemset has exactly $k$ items
- **Support count:** $\sigma(X)$ = number of transactions that contain **all** of $X$
- **Support:** $s(X)=\sigma(X)/n$, the fraction of baskets containing $X$
- **Frequent itemset:** an itemset with $s(X)\ge$ the minimum support; $L_k$ = all frequent $k$-itemsets
- **Candidate set:** $C_k$ = the $k$-itemsets Apriori will actually count at level $k$
- **Downward closure (Apriori property):** every subset of a frequent itemset is frequent; equivalently, every superset of an infrequent itemset is infrequent
- **Rule A ⇒ C:** antecedent $A$ and consequent $C$, disjoint itemsets: *baskets with $A$ tend to contain $C$*
- **Lattice:** all $2^d-1$ itemsets arranged by size, with an edge from each set to its supersets one item bigger

## The math

Let $D=\{t_1,\dots,t_n\}$ be the transactions over item set $I$. The **support** of an itemset counts the transactions that cover it:

$$
s(X)=\frac{\sigma(X)}{n}=\frac{\big|\{\,t\in D : X\subseteq t\,\}\big|}{n}
$$

- $X$: an itemset
- $\sigma(X)$: support count: number of transactions containing every item of X
- $n$: number of transactions
- $T(X)$: below: the set $\{t: X\subseteq t\}$ of transactions covering $X$ (its *tidset*)

**Deriving the Apriori property.** Take $X\subseteq Y$. Any transaction that contains $Y$ contains every item of $Y$, hence every item of $X$. So the covering sets are nested, and their sizes follow:

$$
X\subseteq Y\;\Longrightarrow\;T(Y)\subseteq T(X)\;\Longrightarrow\;s(Y)\le s(X)
$$

- $T(\cdot)$: set of transactions covering an itemset
- $s(Y)\le s(X)$: support is anti-monotone: adding items can never raise it

The contrapositive is the pruning rule: if $s(X)<\sigma_{\min}$ then $s(Y)<\sigma_{\min}$ for **every** $Y\supseteq X$. Hence a $k$-itemset can only be frequent if all $k$ of its $(k-1)$-subsets are in $L_{k-1}$, and the candidates at level $k$ can be restricted to:

$$
C_k=\Big\{\,p\cup\{q_{k-1}\}\;:\;p,q\in L_{k-1},\;p_{1..k-2}=q_{1..k-2},\;p_{k-1}<q_{k-1}\Big\}\;\setminus\;\Big\{c : \exists\, s\subset c,\ |s|=k-1,\ s\notin L_{k-1}\Big\}
$$

- $p_{1..k-2}$: the first k−2 items of p, with items kept in one fixed (e.g. alphabetical) order
- $p\cup\{q_{k-1}\}$: join: two frequent (k−1)-sets with the same prefix give one k-set
- $\setminus\{\dots\}$: prune: drop candidates that have an infrequent (k−1)-subset

The join is **complete**: any frequent $k$-itemset $\{x_1<\dots<x_k\}$ has the two frequent subsets $\{x_1,\dots,x_{k-2},x_{k-1}\}$ and $\{x_1,\dots,x_{k-2},x_k\}$, which share their first $k-2$ items — so it is always generated. And it never generates the same candidate twice, because the shared prefix and the two last items determine the pair.

**Rules.** From a frequent itemset $X$ and a non-empty proper subset $A$, form $A\Rightarrow C$ with $C=X\setminus A$. Its strength is measured by:

$$
\operatorname{conf}(A\Rightarrow C)=\frac{s(A\cup C)}{s(A)}=\hat P(C\mid A),\qquad \operatorname{lift}(A\Rightarrow C)=\frac{\operatorname{conf}(A\Rightarrow C)}{s(C)}=\frac{s(A\cup C)}{s(A)\,s(C)}
$$

- $\operatorname{conf}$: fraction of baskets with A that also contain C — an estimate of P(C | A)
- $\operatorname{lift}$: how much more often A and C co-occur than if they were independent; 1 = independent, > 1 = positive association
- $s(C)$: baseline rate of the consequent

$$
\operatorname{lev}(A\Rightarrow C)=s(A\cup C)-s(A)\,s(C),\qquad \operatorname{conv}(A\Rightarrow C)=\frac{1-s(C)}{1-\operatorname{conf}(A\Rightarrow C)}
$$

- $\operatorname{lev}$: leverage: excess co-occurrence over independence, in absolute support units
- $\operatorname{conv}$: conviction: how much more often the rule would be wrong if A and C were independent; ∞ for a rule that is never wrong

Rule generation has its own anti-monotone property. For a fixed itemset $X$, $\operatorname{conf}(X\setminus C\Rightarrow C)=s(X)/s(X\setminus C)$. Moving an item from the antecedent to the consequent makes the antecedent smaller, so its support **grows** (Apriori property) and the confidence **can only fall**. If $\{B,J\}\Rightarrow\{U\}$ fails the confidence threshold, so do $\{B\}\Rightarrow\{J,U\}$ and $\{J\}\Rightarrow\{B,U\}$ — consequents can be grown level by level too.

**What the two thresholds do**

- **Minimum support σ:** sets the pruning power. Lowering it can only *add* frequent itemsets (the set $\{X: s(X)\ge\sigma\}$ grows as $\sigma$ falls), and the number of candidates — and runtime — grows roughly exponentially as patterns get longer. Raising it removes rare but possibly interesting combinations.
- **Minimum confidence γ:** only filters rules *after* mining; it costs nothing at the expensive itemset stage. High $\gamma$ keeps reliable rules, but confidence ignores the base rate $s(C)$, so it must be read together with lift.
- **Maximum length:** stops the level loop at $k_{\max}$; caps the worst case at $\sum_{k\le k_{\max}}\binom{d}{k}$ candidates.

## Worked example: ten breakfast baskets

Five items — **B**read, b**U**tter, **J**am, **M**ilk, **E**ggs — in ten baskets. Minimum support is 30% (a count of 3), minimum confidence 0.7. Items are kept in the fixed order B < U < J < M < E for the join.

The transactions. Highlighted: the three baskets containing {Bread, Butter, Jam}, the only frequent 3-itemset.

| Basket | Items | Letters |
| --- | --- | --- |
| T1 | Bread, Butter, Jam | B U J |
| T2 | Bread, Butter, Jam | B U J |
| T3 | Bread, Butter, Jam, Eggs | B U J E |
| T4 | Bread, Butter, Milk | B U M |
| T5 | Bread, Butter, Milk | B U M |
| T6 | Bread, Milk | B M |
| T7 | Butter, Milk, Eggs | U M E |
| T8 | Jam, Milk | J M |
| T9 | Bread, Milk | B M |
| T10 | Butter, Jam | U J |

**Apriori by hand (minimum support count 3)**

1. **Scan 1, count items.** B 7, U 7, J 5, M 6, E 2. Eggs falls below 3, so $L_1=\{B,U,J,M\}$ — and the 15 larger itemsets containing E are dead without being looked at.
2. **Join $L_1$.** Every pair of frequent items: $C_2=\{BU, BJ, BM, UJ, UM, JM\}$ — 6 candidates instead of the 10 possible pairs. At $k=2$ the prune step removes nothing (both 1-subsets are in $L_1$ by construction).
3. **Scan 2, count pairs.** BU 5, BJ 3, BM 4, UJ 4, UM 3, JM 1. So $L_2=\{BU,BJ,BM,UJ,UM\}$; only Jam + Milk is rare.
4. **Join $L_2$** (same first item): BU+BJ → BUJ, BU+BM → BUM, BJ+BM → BJM, UJ+UM → UJM.
5. **Prune.** BJM contains JM and UJM contains JM — not in $L_2$, so both are deleted **without counting**. $C_3=\{BUJ, BUM\}$.
6. **Scan 3.** BUJ 3 (T1, T2, T3), BUM 2 (T4, T5). $L_3=\{BUJ\}$.
7. **Join $L_3$.** A single itemset has no partner, so $C_4=\varnothing$ and the search stops after **3 scans**. In total **13** itemsets were counted out of 31, and **10** are frequent.

Level by level. Pruned = generated by the join but removed by the subset check before the scan.

| Level k | Joined | Pruned | Counted (support) | Frequent Lₖ |
| --- | --- | --- | --- | --- |
| 1 | 5 | 0 | B 7 · U 7 · J 5 · M 6 · E 2 | B, U, J, M |
| 2 | 6 | 0 | BU 5 · BJ 3 · BM 4 · UJ 4 · UM 3 · JM 1 | BU, BJ, BM, UJ, UM |
| 3 | 4 | 2 (BJM, UJM) | BUJ 3 · BUM 2 | BUJ |
| 4 | 0 | — | — | ∅ → stop |

**Rules.** Each frequent itemset of size $\ge 2$ yields candidate rules. From BUJ (support 3): $BJ\Rightarrow U$ has confidence $3/3=1.00$; $UJ\Rightarrow B$ $3/4=0.75$; $BU\Rightarrow J$ and $J\Rightarrow BU$ $3/5=0.60$; $B\Rightarrow UJ$ and $U\Rightarrow BJ$ $3/7=0.43$. From the pairs: $J\Rightarrow U$ $4/5=0.80$, $B\Rightarrow U$ and $U\Rightarrow B$ $5/7=0.71$, everything else below 0.7. Five rules pass:

All rules with confidence ≥ 0.7, sorted by lift (values from mlxtend, below). s(Butter) = s(Bread) = 0.7.

| Rule | Support | Confidence | Lift | Leverage | Conviction |
| --- | --- | --- | --- | --- | --- |
| **{Bread, Jam} ⇒ {Butter}** | 0.30 | **1.000** | **1.429** | 0.09 | ∞ |
| {Jam} ⇒ {Butter} | 0.40 | 0.800 | 1.143 | 0.05 | 1.50 |
| {Butter, Jam} ⇒ {Bread} | 0.30 | 0.750 | 1.071 | 0.02 | 1.20 |
| {Bread} ⇒ {Butter} | 0.50 | 0.714 | 1.020 | 0.01 | 1.05 |
| {Butter} ⇒ {Bread} | 0.50 | 0.714 | 1.020 | 0.01 | 1.05 |

**A new basket.** A customer has {Bread, Jam} in the cart. The applicable rules are those whose antecedent is inside the cart and whose consequent is not: $\{B,J\}\Rightarrow\{U\}$ (confidence 1.00, lift 1.43) is the strongest, so we **recommend Butter**. Note the bottom two rows: *Bread ⇒ Butter* has 71% confidence, which sounds strong, but its lift is 1.02 — Butter is in 70% of all baskets anyway, so knowing Bread is there tells us almost nothing.

> Figure: Apriori on the ten baskets, drawn on the lattice of all 31 itemsets (rows k = 1…5). With min support 3/10: Eggs (2) fails at k = 1 and its 15 supersets fade; the join proposes 6 pairs, JM (1) fails; the join proposes 4 triples, BJM and UJM are crossed out by the subset check before counting, BUJ (3) survives and BUM (2) fails; C₄ is empty. 13 of 31 itemsets are counted, 10 are frequent, and 5 rules reach confidence 0.7 — the basket {Bread, Jam} gets Butter from BJ → U (1.00, lift 1.43). Switch min support: at 2/10 Apriori counts 17 itemsets and finds 13 frequent ones; at 4/10 it counts 11 and finds 7.

## The algorithm, step by step

**Apriori(D, σ, γ)**

1. **Level 1.** One scan of $D$ counts every item; $L_1$ = items with count $\ge\sigma n$.
2. **Join.** For $k=2,3,\dots$: sort each itemset in $L_{k-1}$ by a fixed item order; merge every pair that agrees on its first $k-2$ items into a $k$-itemset.
3. **Prune.** Delete any candidate with a $(k-1)$-subset not in $L_{k-1}$ (store $L_{k-1}$ in a hash set, so each check is $k$ lookups).
4. **Count.** One scan of $D$: for every transaction, increment every candidate it contains (a hash tree or trie over $C_k$ finds them without testing all candidates).
5. **Filter.** $L_k=\{c\in C_k:\sigma(c)\ge\sigma n\}$. Stop when $L_k$ (or $C_{k+1}$) is empty.
6. **Rules.** For each frequent $X$ with $|X|\ge2$ and each non-empty $A\subset X$, output $A\Rightarrow X\setminus A$ if $\sigma(X)/\sigma(A)\ge\gamma$. All supports are already known — no more scans.

**Complexity**

- **Database scans:** $k_{\max}+1$ at most, where $k_{\max}$ is the length of the longest frequent itemset
- **Counting:** level $k$ costs about $n\cdot\min\!\big(|C_k|,\binom{w}{k}\big)$ subset tests, $w$ = average basket width; this dominates
- **Candidate generation:** $O(|L_{k-1}|^2\cdot k)$ for the join, $O(|C_k|\cdot k)$ hash lookups for the prune
- **Memory:** all of $C_k$ with counters must fit in memory; $|C_2|=\binom{|L_1|}{2}$ is usually the peak
- **Worst case:** a frequent itemset of length $m$ forces all $2^m-2$ of its proper subsets to be frequent — e.g. $2^{10}-2=1022$ for $m=10$ — so long patterns are inherently expensive

> **The output can be exponential, so no algorithm escapes it:** Apriori is not slow because it is naive — it counts only candidates whose every subset is frequent, which is the tightest set any level-wise method can count. When it is slow, it is because the *answer* is huge (low support, long patterns). The real costs Apriori adds are the repeated scans and the candidate sets held in memory; that is what **FP-Growth** (no candidates, two scans) and **Eclat** (vertical tidsets, intersections instead of scans) remove — see those articles.

## Variants and practical tuning

Classic refinements of Apriori and where the work goes.

| Variant | Change | Helps when |
| --- | --- | --- |
| AprioriTid | after scan 1, replace each transaction by the candidates it contains | later levels: the encoded database shrinks fast |
| DHP (hash-based) | while counting items, hash all pairs into buckets; a pair in a light bucket can't be frequent | C₂ is huge — the usual bottleneck |
| Transaction reduction | drop baskets that contain no frequent k-itemset from later scans | many short baskets |
| Partitioning | mine each chunk locally; any globally frequent set is frequent in some chunk; one verification scan | data does not fit in memory; 2 scans total |
| Sampling (Toivonen) | mine a sample at a lowered threshold, then verify on the full data | approximate answers are fine, scans are costly |
| FP-Growth / Eclat | no level-wise candidate generation at all | low support, dense data, long patterns |

**Tuning in practice**

- **Start high, lower slowly:** begin with a support that yields a few hundred itemsets (e.g. 1–5% of baskets for retail) and halve it while runtime and output size stay manageable
- **Rank by lift, not confidence:** filter by a modest confidence, then sort by lift or leverage; drop rules with lift ≤ 1
- **Cap the length:** `max_len=3` or 4 is often enough for actionable rules, and caps the worst case
- **Aggregate items:** rare SKUs never reach support; mining at the category level (all jams → Jam) finds patterns hidden at product level
- **Check stability:** re-mine on a different month or a bootstrap sample; rules that vanish were noise

> **High confidence can mean nothing:** Confidence is $\hat P(C\mid A)$, and if $C$ is in almost every basket every rule $\cdot\Rightarrow C$ looks confident. In the example, *Bread ⇒ Butter* has confidence 0.71 but lift 1.02 — Bread and Butter are close to independent. Always report lift (or leverage) alongside confidence, and treat lift < 1 as a *negative* association.

> **Low minimum support explodes:** Halving $\sigma$ can multiply the number of frequent itemsets many times over, and a few long frequent patterns drag in all their subsets ($2^m-2$ of them). If a run never finishes or memory blows up, raise the support, set a maximum length, or switch to FP-Growth — do not just wait.

> **Association is not causation:** A rule says two items co-occur, not that putting one in the cart causes the other. Many strong rules come from a common cause (a promotion, a recipe, a season). Validate any rule you act on with an experiment.

## In code

```python
import numpy as np
from itertools import combinations

def apriori(X, items, min_support):
    """X: boolean (n_transactions, n_items). Returns {itemset (tuple of col idx): support count}."""
    n = X.shape[0]
    min_count = int(np.ceil(min_support * n))
    counts = X.sum(axis=0)
    L = {(j,): int(c) for j, c in enumerate(counts) if c >= min_count}
    frequent, k, counted = dict(L), 2, X.shape[1]
    while L:
        prev = sorted(L)
        # join: two (k-1)-itemsets sharing their first k-2 items
        cands = [a + (b[-1],) for a, b in combinations(prev, 2) if a[:-1] == b[:-1]]
        # prune: every (k-1)-subset must be frequent
        prevset = set(prev)
        cands = [c for c in cands if all(s in prevset for s in combinations(c, k - 1))]
        counted += len(cands)
        # count: a transaction contains c iff all its columns are 1
        L = {}
        for c in cands:
            s = int(X[:, list(c)].all(axis=1).sum())
            if s >= min_count:
                L[c] = s
        frequent.update(L)
        k += 1
    return frequent, counted

def rules(frequent, n, min_conf):
    out = []
    for iset, s in frequent.items():
        for r in range(1, len(iset)):
            for A in combinations(iset, r):
                C = tuple(i for i in iset if i not in A)
                conf = s / frequent[A]
                if conf >= min_conf:
                    lift = conf / (frequent[C] / n)
                    out.append((A, C, s / n, conf, lift))
    return out

items = ["Bread", "Butter", "Jam", "Milk", "Eggs"]
baskets = ["BUJ", "BUJ", "BUJE", "BUM", "BUM", "BM", "UME", "JM", "BM", "UJ"]
code = {"B": 0, "U": 1, "J": 2, "M": 3, "E": 4}
X = np.zeros((len(baskets), len(items)), dtype=bool)
for i, b in enumerate(baskets):
    X[i, [code[ch] for ch in b]] = True

freq, counted = apriori(X, items, min_support=0.3)
print("candidates counted:", counted, "of", 2 ** len(items) - 1)      # 13 of 31
for iset, s in sorted(freq.items(), key=lambda kv: (len(kv[0]), kv[0])):
    print([items[j] for j in iset], s)                                 # ... ['Bread', 'Butter', 'Jam'] 3
for A, C, sup, conf, lift in rules(freq, len(baskets), 0.7):
    print([items[j] for j in A], "->", [items[j] for j in C], f"sup={sup:.2f} conf={conf:.3f} lift={lift:.3f}")
# ['Bread', 'Jam'] -> ['Butter'] sup=0.30 conf=1.000 lift=1.429  (and 4 more)
```

From scratch with NumPy: level-wise join, subset prune, boolean-matrix counting, and rules. Prints 13 candidates counted, the 10 frequent itemsets and the 5 rules.

```python
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules

baskets = [
    ["Bread", "Butter", "Jam"], ["Bread", "Butter", "Jam"], ["Bread", "Butter", "Jam", "Eggs"],
    ["Bread", "Butter", "Milk"], ["Bread", "Butter", "Milk"], ["Bread", "Milk"],
    ["Butter", "Milk", "Eggs"], ["Jam", "Milk"], ["Bread", "Milk"], ["Butter", "Jam"],
]
te = TransactionEncoder()
X = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)   # one-hot booleans

freq = apriori(X, min_support=0.3, use_colnames=True)      # optionally max_len=3
print(freq.sort_values("support", ascending=False).to_string(index=False))

rules = association_rules(freq, metric="confidence", min_threshold=0.7)
print(rules[["antecedents", "consequents", "support", "confidence", "lift", "leverage", "conviction"]]
      .sort_values("lift", ascending=False).round(3).to_string(index=False))
#  antecedents consequents  support  confidence  lift  leverage  conviction
# (Jam, Bread)    (Butter)      0.3       1.000 1.429      0.09         inf
#        (Jam)    (Butter)      0.4       0.800 1.143      0.05        1.50
# (Jam, Butter)    (Bread)      0.3       0.750 1.071      0.02        1.20
#      (Bread)    (Butter)      0.5       0.714 1.020      0.01        1.05
#     (Butter)     (Bread)      0.5       0.714 1.020      0.01        1.05
```

The same baskets with mlxtend: 10 frequent itemsets and the 5-rule table above, including leverage and conviction.

**Strengths**

- You need every frequent itemset exactly, with an easy-to-explain algorithm and output ("bought together in 30% of baskets").
- Support is moderately high and patterns are short — sparse retail baskets, click sets, symptom lists.
- Data lives in a database where one scan per level is cheap (SQL GROUP BY per level works).
- You want the candidate counts and supports themselves, e.g. to compute any rule metric afterwards.

**Limitations**

- Minimum support must be very low (rare but valuable items) — candidate sets explode.
- Data is dense or patterns are long: all 2^m − 2 subsets of a long pattern must be generated and counted.
- The database is huge and each scan is expensive — FP-Growth needs two scans, Eclat one.
- Items have quantities, order or time — use sequential pattern mining or a supervised model instead.

- **Market-basket analysis:** Shelf placement, bundles and "frequently bought together" in retail and e-commerce.
- **Recommendation seeds:** Rules with high lift give cheap, explainable item-to-item recommendations.
- **Medical and pharmacovigilance data:** Co-occurring diagnoses, or drug combinations that appear with adverse events more than expected.
- **Web usage and log mining:** Pages visited in one session, or alarm codes that fire together in system logs.

**Question:** In some database, {A, C} has support 0.3, {A} 0.4 and {C} 0.5. What are the confidence and lift of A ⇒ C?

- A. 0.60 and 1.20
- B. 0.75 and 1.50
- C. 0.75 and 0.60
- D. 0.30 and 0.75

**Answer:** B. 0.75 and 1.50 — $\operatorname{conf}=0.3/0.4=0.75$ and $\operatorname{lift}=0.75/0.5=1.5$: baskets with A contain C 1.5× as often as baskets in general.

**Question:** L₂ = {AB, AC, AD, BC, CD} (items ordered A < B < C < D). Which candidates survive the join and prune into C₃?

- A. ABC, ABD, ACD
- B. ABC, ACD
- C. ABC only
- D. ABC, ACD, BCD

**Answer:** B. ABC, ACD — The join merges pairs with the same first item: AB+AC → ABC, AB+AD → ABD, AC+AD → ACD (BC and CD have no partner). ABD contains BD, which is not frequent, so it is pruned. ABC and ACD have all three 2-subsets in L₂.

**Question:** Apriori finds that {Jam, Milk} appears in only 1 of 10 baskets (min count 3). What can it conclude about {Bread, Jam, Milk} without scanning?

- A. Nothing — it must be counted
- B. Its support is exactly 1
- C. Its support is at most 1, so it is infrequent
- D. Its support is at least 1

**Answer:** C. Its support is at most 1, so it is infrequent — Every basket containing {Bread, Jam, Milk} also contains {Jam, Milk}, so $\sigma(BJM)\le\sigma(JM)=1<3$. That is why BJM is pruned in the worked example (its true count is 0).

**Question:** {Bread, Jam} ⇒ {Butter} has confidence 1.0. Without any counting, what do we know about {Jam} ⇒ {Bread, Butter}?

- A. Its confidence is also 1.0
- B. Its confidence is at most 1.0 and can be lower
- C. Its confidence is at least 1.0
- D. Its lift is 1.0

**Answer:** B. Its confidence is at most 1.0 and can be lower — Both rules come from X = BUJ, with confidence $s(X)/s(\text{antecedent})$. Shrinking the antecedent from BJ to J can only raise its support, so confidence can only fall. Here it falls to $3/5=0.60$.

**Key points**

- Support is anti-monotone: $X\subseteq Y\Rightarrow s(Y)\le s(X)$. Every superset of an infrequent itemset is infrequent.
- Apriori is level-wise: join frequent $(k-1)$-itemsets sharing $k-2$ items, prune any candidate with an infrequent subset, then count the survivors in one scan.
- On the 10-basket example it counts 13 of 31 itemsets in 3 scans and finds 10 frequent ones; BJM and UJM are pruned without counting.
- Rules come from frequent itemsets for free: confidence = s(A∪C)/s(A). Always check lift, because confidence ignores how common the consequent already is.
- Minimum support controls the cost; low support or long patterns blow up candidate sets — then use FP-Growth or Eclat.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
