Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Apriori algorithm

Apriori is the classical algorithm for finding frequent itemsets and deriving association rules from transaction data using the downward-closure (Apriori) property to prune candidates.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Apriori is used by engineers to discover frequent patterns (itemsets) and association rules in transaction data — for example market-basket analysis, recommendation engines, and feature discovery for other mining tasks. It is the foundational algorithm students must understand before learning faster methods (for example FP-growth) and before applying association-rule pruning or parallelisation techniques.

Key ideas

  • Support count (also called frequency) of an itemset X, written σ(X), is the number of transactions in D that contain X. The support of X, written supp(X), is the fraction of transactions that contain X: supp(X) = σ(X) / N where N = |D|.

  • Frequent itemset: an itemset X is frequent if supp(X) ≥ minsup (or equivalently σ(X) ≥ min_support_count). minsup (or min_support_count) is an input threshold.

  • Association rule: an implication of the form X ⇒ Y, where X and Y are disjoint and non-empty itemsets (X ∩ Y = ∅). The rule means: when X appears in a transaction, Y often appears too.

  • Confidence of rule X ⇒ Y: conf(X ⇒ Y) = supp(X ∪ Y) / supp(X) (probability that Y appears given X appears). A rule is accepted if conf ≥ minconf.

  • Apriori property (downward closure / anti-monotone): If an itemset is frequent, then all its subsets are also frequent. Equivalently: if an itemset is infrequent, then all its supersets are infrequent. This property follows from set inclusion: σ(S) ≥ σ(T) whenever S ⊆ T because every transaction containing T also contains S; therefore if σ(S) < min_support_count then no superset T ⊇ S can have σ(T) ≥ min_support_count. This is the key pruning principle.

  • Apriori algorithm overview (high level, exact steps you must write in exams):

    1. Scan D to find frequent 1-itemsets L1 (items whose count ≥ min_support_count).
    2. For k = 2 while L_{k-1} is not empty: a. Generate candidate k-itemsets Ck by joining pairs of (k−1)-itemsets in L_{k-1} that share the first k−2 items (lexicographic join). For each candidate c in Ck, apply the prune step: if any (k−1)-subset of c is not in L_{k-1}, remove c (by Apriori property). b. Scan D and count occurrences σ(c) for each c ∈ Ck. c. Form Lk = {c ∈ Ck | σ(c) ≥ min_support_count}.
    3. All frequent itemsets are ∪k Lk. Generate association rules from each frequent itemset f (|f| ≥ 2) by splitting f into non-empty X and Y = f\X and testing conf(X⇒Y) ≥ minconf; use recursive pruning on consequents to avoid generating rules whose confidence cannot meet minconf (standard optimisation).
  • Candidate generation detail (what to write and why it is correct):

    • Join step: take p and q in L_{k-1} with first k−2 items identical and last item different; output candidate c = p ∪ q (a k-itemset). This ensures candidates are only unions of two frequent (k−1)-itemsets and reduces candidates.
    • Prune step: for each candidate c, enumerate all k−1 subsets; if any subset is not in L_{k-1}, remove c because of the Apriori property.
  • Complexity and behaviour: worst-case cost is exponential in |I| because candidate counts can be combinatorial. But with realistic min-support thresholds and sparse data, Apriori prunes many candidates. The algorithm needs repeated scans of D (one per Ck), which is the main I/O cost.

  • Diagrams to draw in an answer: draw an itemset lattice for a small itemset (e.g., items A,B,C) with levels 0..3; label nodes with itemsets and mark frequent ones (dark/boxed). Also draw a flowchart: (Start) → scan D → L1 → loop: apriori_gen(Lk-1) → count Ck over D → form Lk → stop if empty → output. Label each step.

Formulas

supp(X) = σ(X) / N

  • σ(X) = number of transactions containing X (support count); N = total number of transactions; unitless fraction; applies always when counting frequency.

X is frequent ⇔ supp(X) ≥ minsup

  • minsup = minimum support threshold (a fraction like 0.05 or 0.6); unitless. When minsup is given as a fraction, the equivalent count threshold is min_support_count = ceil(minsup · N).

conf(X ⇒ Y) = supp(X ∪ Y) / supp(X)

  • supp(X ∪ Y) and supp(X) are fractions; conf is a fraction (or percentage); applies when supp(X) > 0.

lift(X ⇒ Y) = supp(X ∪ Y) / (supp(X) · supp(Y))

  • lift > 1 indicates positive correlation; lift = 1 indicates independence; lift < 1 indicates negative correlation; unitless.

σ(X) = supp(X) · N

  • relates counts to fractions; σ(X) is integer count; N is integer number of transactions.

Syntax / pseudocode lines to remember: L1 = {items i | σ({i}) ≥ min_support_count} for k = 2 while L_{k-1} ≠ ∅: Ck = apriori_gen(L_{k-1}); count σ(c) for c ∈ Ck by scanning D; Lk = {c ∈ Ck | σ(c) ≥ min_support_count} apriori_gen(L_{k-1}): join step then prune step (remove candidates with any (k−1)-subset not in L_{k-1})

Worked examples

Example 1 — full trace (algorithmic): Given D with N = 5 transactions: T1 = {A,B,C} T2 = {A,C} T3 = {B,C} T4 = {A,B} T5 = {A,B,C} Let minsup = 60% (min_support_count = 0.6 × 5 = 3), minconf = 66%. Step 1: Count 1-itemsets: σ(A)=4, σ(B)=4, σ(C)=4 → all ≥ 3 so L1 = {A, B, C}. Step 2: k=2, generate C2 by joining L1 with itself: C2 = {{A,B}, {A,C}, {B,C}}. Count each:

  • σ({A,B}) appears in T1,T4,T5 → 3
  • σ({A,C}) appears in T1,T2,T5 → 3
  • σ({B,C}) appears in T1,T3,T5 → 3 All have σ = 3 ≥ 3 so L2 = {{A,B}, {A,C}, {B,C}}. Step 3: k=3, generate C3 by joining pairs in L2. Join {A,B} and {A,C} → candidate {A,B,C}. Check prune: all 2-subsets of {A,B,C} are {A,B}, {A,C}, {B,C} and all are in L2, so candidate kept. Count σ({A,B,C}) appears in T1,T5 → 2 which is < 3, so not frequent. L3 = ∅, stop. Frequent itemsets are L1 ∪ L2.

Example 2 — rule generation (numerical): From Example 1, consider itemset {A,B} with supp({A,B}) = σ/N = 3/5 = 0.6 and supp(A) = 4/5 = 0.8. Compute confidence of rule A ⇒ B: conf(A ⇒ B) = supp(A ∪ B) / supp(A) = 0.6 / 0.8 = 0.75 (75%). This is ≥ minconf (66%) so accept rule A ⇒ B. Similarly B ⇒ A has conf = 0.75. Compute lift: lift(A ⇒ B) = supp(A ∪ B) / (supp(A)·supp(B)) = 0.6 / (0.8·0.8) = 0.6 / 0.64 = 0.9375 — slightly < 1, which indicates a slight negative association (less frequent than expected under independence); students should report both confidence and lift when asked to comment. Final accepted rules (with conf 75%): A⇒B, B⇒A, A⇒C, C⇒A, B⇒C, C⇒B.

Common mistakes

  • Omitting the prune step (testing all (k−1)-subsets) — leads to too many candidates.
  • Using minconf before generating all frequent itemsets; confidence is computed from frequent sets only.
  • Not handling transactions as sets: treating order or duplicates in a transaction as separate items.
  • Off-by-one errors in k (starting at k=1 vs k=2) when writing loops.

For your exam

Question types you will see: definitions (support, confidence, Apriori property), a full-trace of Apriori on a small transaction DB, derive candidate generation for a given L_{k-1}, write pseudocode, compute rules and confidence/lift, and complexity/optimisation notes. A full-marks answer includes:

  • Clear definitions of support, support count, frequent itemset, association rule, confidence, lift.
  • Statement and proof (one or two lines) of the Apriori property.
  • Correct pseudocode or step-by-step algorithm with join and prune explained.
  • For trace questions: show L1, C2, L2, C3, L3 etc with counts and threshold checks; label N and min_support_count.
  • For rule questions: show computation of conf and lift and compare with minconf; list rules that meet thresholds.
  • Optional: mention optimisation (hashing candidates, transaction reduction, vertical format like Eclat) if marks allow.

Quick check

  1. State the Apriori property in one sentence.
  2. How do you compute confidence of rule X ⇒ Y using support counts? Give formula.
  3. In a DB with N = 100, an itemset has σ = 12. If minsup = 0.1, is it frequent? Show calculation. Answers: 1) If an itemset is frequent then all its subsets are frequent (downward closure). 2) conf(X ⇒ Y) = σ(X ∪ Y) / σ(X) (or supp(X ∪ Y)/supp(X)). 3) supp = 12/100 = 0.12 ≥ 0.1 so yes, it is frequent.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?