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.

Frequent itemsets and association rules

Frequent itemsets and association rules find which item combinations appear often in transaction data and which implication rules (X → Y) are strong, using measures such as support, confidence and lift and algorithms such as Apriori.

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

Frequent itemset mining and association rules are used by engineers to find useful correlations in large transaction data — for example market-basket analysis, recommendation systems, inventory planning and cross-selling. These methods convert raw transactions into simple rules (like “if A then B”) that business systems can act on.

Key ideas

  • Itemset: a set of items (for example {A,B}). An itemset containing k items is a k-itemset.
  • Support count (σ or count): the number of transactions that contain a given itemset.
  • Relative support (support): the fraction of all transactions that contain the itemset. If N is the number of transactions and count(X) is the support count, then support(X) = count(X)/N.
  • Frequent itemset: an itemset whose support is at least the user-specified minimum support (minsup). If using absolute thresholds, compare counts; if using relative thresholds, compare fractions.
  • Closed frequent itemset: a frequent itemset none of whose proper supersets has the same support (i.e., no superset occurs in exactly the same set of transactions).
  • Maximal frequent itemset: a frequent itemset that has no frequent superset.
  • Association rule: an implication of the form X → Y, where X and Y are itemsets and X ∩ Y = Ø. The rule means: when X appears in a transaction, Y tends to appear too.
  • Support of a rule: support(X ∪ Y) (fraction of transactions containing both X and Y).
  • Confidence of a rule: confidence(X → Y) = support(X ∪ Y) / support(X). Interpretation: estimated probability that Y appears given X.
  • Lift of a rule: lift(X → Y) = support(X ∪ Y) / (support(X)·support(Y)). Interpretation: how many times more likely X and Y occur together than if they were independent. lift > 1 indicates positive association; lift = 1 indicates independence; lift < 1 indicates negative association.
  • Conviction (optional): conviction(X → Y) = (1 − support(Y)) / (1 − confidence(X → Y)). Conviction measures implication strength considering how often the rule makes incorrect predictions.

Apriori principle (key theorem used by algorithms):

  • Apriori property: "All non-empty subsets of a frequent itemset must also be frequent."
    • Assumption: support is anti-monotone (if A ⊆ B then support(A) ≥ support(B)).
    • Proof (standard exam-style): Suppose itemset S is frequent but some non-empty subset T ⊂ S is infrequent. Then support(T) < minsup. But every transaction that contains S also contains T, so count(S) ≤ count(T). Hence count(S) < minsup, contradicting that S is frequent. Therefore all subsets must be frequent.

Apriori algorithm (high level, what to draw in exam):

  • Draw a flow diagram with boxes: (1) generate L1 (frequent 1-itemsets), (2) for k = 2 to until empty: join L(k−1) with L(k−1) to make candidates Ck, prune Ck using Apriori property, scan DB to get counts and make Lk, end. Label data flow and show a sample transaction table at start.
  • Candidate generation (join step): to form Ck from L(k−1), join two (k−1)-itemsets p and q (with items in each itemset kept in a fixed sorted order, e.g., lexicographic) if their first k−2 items are identical and their last items differ; result is candidate r = p ∪ q of size k. Then prune r if any (k−1)-subset of r is not in L(k−1).
  • Stop when Lk is empty. Output all L1 ∪ L2 ∪ ... as frequent itemsets.

Rule generation from frequent itemsets:

  • For each frequent itemset I and for each non-empty proper subset A ⊂ I, generate rule A → (I \ A). Compute confidence = support(I)/support(A). Keep rules whose confidence ≥ minconf.
  • For larger I use a systematic method: start with single-item consequents and grow consequent size using pruning based on confidence monotonicity (confidence never increases when you enlarge the consequent with the antecedent fixed).

Limitations and parameters:

  • Results depend strongly on minsup and minconf. Low minsup causes many itemsets; high minsup may miss useful rules.
  • Apriori requires multiple passes over the DB and can be slow for low minsup; FP-growth is an alternative (referenced in course list).

Formulas

support_count(X) = σ(X) = number of transactions that contain X

  • σ(X): integer count, unit: count (unitless). Applies always when counting occurrences.

support(X) = σ(X) / N

  • support(X): fraction between 0 and 1, unitless; σ(X) is support count, N is total number of transactions. Applies when you want relative support.

confidence(X → Y) = support(X ∪ Y) / support(X)

  • confidence: probability estimate, unitless. support(X ∪ Y) and support(X) are relative supports (fractions). Applies to any candidate rule X→Y with support(X) > 0.

lift(X → Y) = support(X ∪ Y) / (support(X) · support(Y))

  • lift: unitless ratio. Uses relative supports. Applies to measure dependence between X and Y.

conviction(X → Y) = (1 − support(Y)) / (1 − confidence(X → Y))

  • conviction: unitless; denominator non-zero unless confidence = 1. Applies as an alternative interestingness measure.

Worked examples

Example 1 — Apriori trace (university style): Given transactions (N = 6): T1: {A, B, C} T2: {A, C} T3: {B, C, D} T4: {A, B, D} T5: {A, B, C} T6: {B, C} Let minimum support = 3 transactions (minsup = 3). Find all frequent itemsets. Steps:

  1. Count single items: σ(A)=4 (T1,T2,T4,T5), σ(B)=5 (T1,T3,T4,T5,T6), σ(C)=5 (T1,T2,T3,T5,T6), σ(D)=2 (T3,T4).
    • L1 = {A(4), B(5), C(5)} because D has count 2 < 3 and is pruned.
  2. Generate C2 by joining L1 items: candidates AB, AC, BC.
    • Count: σ(AB)=3 (T1,T4,T5), σ(AC)=3 (T1,T2,T5), σ(BC)=4 (T1,T3,T5,T6).
    • L2 = {AB(3), AC(3), BC(4)} because all counts ≥ 3.
  3. Generate C3 by joining AB and AC -> ABC candidate; verify all 2-subsets (AB, AC, BC) are in L2 (they are), so keep ABC.
    • Count σ(ABC)=2 (T1,T5) < 3 so ABC is not frequent. L3 = Ø. Stop. Final frequent itemsets: L1 and L2 as listed.

Example 2 — Association rules and metrics (from Example 1): Use relative supports (divide counts by N = 6): support(A)=4/6 ≈ 0.6667, support(B)=5/6 ≈ 0.8333, support(AB)=3/6 = 0.5. Rule A → B:

  • confidence(A → B) = support(AB)/support(A) = 0.5 / 0.6667 = 0.75.
  • lift(A → B) = support(AB) / (support(A)·support(B)) = 0.5 / (0.6667·0.8333) ≈ 0.5 / 0.5556 ≈ 0.9.
  • conviction(A → B) = (1 − support(B)) / (1 − confidence(A → B)) = (1 − 0.8333) / (1 − 0.75) = 0.1667 / 0.25 ≈ 0.6668. Interpretation: confidence 75% is fairly strong, but lift < 1 (≈0.9) means A and B co-occur slightly less than expected under independence; conviction <1 shows the rule makes errors relatively often. (Give numeric rounding to two or three significant digits in answers.)

If the exam asked for a diagram for candidate generation: draw a small table of L2 items then arrows joining AB and AC to ABC and label the prune check (all 2-subsets present?) and the final count result.

Common mistakes

  • In candidate join step, joining wrong pairs (must match first k−2 items) or forgetting to prune candidates whose subsets are not frequent.
  • Wrong counting: forgetting that a transaction must contain all items in the itemset; double-counting transactions.
  • Rounding errors in lift and conviction; report to 2–3 decimal places and state exact fraction if needed.
  • Generating rules from non-frequent itemsets — rules come only from frequent itemsets.

For your exam

Types of questions you will see:

  • Definitions: define support, confidence, frequent itemset, Apriori property.
  • Short notes: explain Apriori algorithm with a diagram, list pros/cons and parameters.
  • Derivation/proof: prove the Apriori property by contradiction (show subsets must be frequent).
  • Numericals: run Apriori on a small transaction database (trace candidate generation and pruning) — show counts per step and final frequent itemsets.
  • Rule metrics: given counts compute support, confidence, lift, conviction for rules (show working).
  • Programs/pseudocode: write or explain the Apriori pseudocode or candidate-generation step.
  • Diagrams: draw candidate generation and pruning flow for k = 2, 3. What a full-marks answer includes:
  • Clear definitions with notation, correct thresholds (absolute/relative), step-by-step Apriori rounds with counts, correct pruning, correct rule metric calculations, and brief interpretation of final rules.

Quick check

  1. Define a frequent itemset in one sentence.
  2. State the Apriori property (one sentence).
  3. What does lift(X→Y) > 1 mean? Answers: 1) An itemset whose support (fraction of transactions containing it) is ≥ minimum support.; 2) Every non-empty subset of a frequent itemset is also frequent (support is anti-monotone).; 3) X and Y occur together more often than expected if they were independent (positive association).

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

Stuck on something here?