Unit 3 — Association Analysis

Topics Covered

Syllabus topics: Association Rules — What is an Association Rule?, Methods to Discover Association Rules, A Priori Algorithm, Partition Algorithm, Pincer-Search Algorithm, Dynamic Itemset Counting Algorithm, FP-Tree Growth Algorithm, Generalized Association Rule, Association Rules with Item Constraints.

3.1 What an association rule is

Vocabulary

⚠️ X and Y must be disjoint

{bread, milk} → {milk} is not a valid rule. The consequent must contain no item from the antecedent, or the "rule" is trivially true and says nothing.

3.2 Support, confidence and lift

support(X → Y)    = σ(X ∪ Y) / N              "how often does this happen?"

confidence(X → Y) = σ(X ∪ Y) / σ(X)           "when X happens, how often does Y?"
                  = support(X ∪ Y) / support(X)

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

N = 5

σ({milk, nappies})       = T3, T4, T5           = 3
σ({milk, nappies, beer}) = T3, T4               = 2
σ({beer})                = T2, T3, T4           = 3

support    = 2/5                    = 0.40
confidence = 2/3                    = 0.667
lift       = 0.667 / (3/5) = 0.667 / 0.6 = 1.111

⚠️ Confidence alone is misleading

This is the most important idea in the unit, and it is a guaranteed exam question.

Suppose 800 of 1,000 students play cricket and 900 study data science, with 720 doing both.

{cricket} → {data science}

support    = 720/1000                    = 0.72   ← looks strong
confidence = 720/800                     = 0.90   ← looks very strong
lift       = 0.90 / (900/1000) = 0.90/0.90 = 1.00 ← INDEPENDENT

The rule looks excellent by support and confidence and is worthless: 90% of all students study data science anyway, so knowing they play cricket tells you nothing. Confidence is high only because the consequent is common.

Lift corrects for this, and it is why every serious analysis reports it. Make the numbers slightly worse — 700 of the 800 cricketers — and lift falls to 0.875/0.9 = 0.972, a negative association hiding behind 87.5% confidence.

Other interest measures

Support and lift are symmetric; confidence and conviction are not. So X → Y and Y → X always share a support and a lift but generally differ in confidence — which is how you tell the direction of a rule.

3.3 The problem, and why it is hard

Finding rules is a two-step process:

1. Find all frequent itemsets — those with support ≥ minsup. This is the expensive step.

2. Generate strong rules from them — those with confidence ≥ minconf. This is cheap by comparison.

Total possible rules

From d items the number of possible rules is 3ᵈ − 2^(d+1) + 1. For d = 6 that is 729 − 128 + 1 = 602 rules. The exponential in the base 3 comes from each item being in the antecedent, the consequent, or neither.

3.4 The Apriori algorithm

X ⊆ Y  ⟹  support(X) ≥ support(Y)

                    {}
        ┌───────┬────┴───┬───────┐
       {A}     {B}      {C}     {D}
      ┌──┴──┬───┴──┬─────┴──┐
    {A,B}  {A,C}  {A,D}  {B,C} {B,D} {C,D}
      │      │             ╳     ╳     ╳     ← {B,C} infrequent...
   {A,B,C} {A,B,D} …       ╳╳╳╳╳╳╳╳╳╳╳╳     ← ...so ALL its supersets pruned

The algorithm

L₁ = {frequent 1-itemsets}                    (one pass over the data)
k = 2
while L(k-1) is not empty:
    Cₖ = apriori_gen(L(k-1))                  ← join, then prune
    for each transaction t in D:              ← ONE pass per level
        for each candidate c in Cₖ:
            if c ⊆ t: c.count++
    Lₖ = { c in Cₖ : c.count ≥ minsup_count }
    k++
return the union of all Lₖ

apriori_gen has two parts:

• Join step. Join L(k−1) with itself: two (k−1)-itemsets combine if their first k−2 items are identical. (Keeping the items sorted is what makes this work and avoids generating each candidate twice.)

• Prune step. Discard any candidate having any (k−1)-subset not in L(k−1). This is the Apriori principle applied before counting.

Complexity and weaknesses

Apriori's two weaknesses, both examined:

1. Too many candidates. With 10⁴ frequent 1-itemsets, C₂ has about 10⁴ × 10⁴ / 2 = 5 × 10⁷ candidates. The k=2 step is usually the bottleneck.

2. Too many database scans. Finding a frequent 20-itemset needs 21 passes over data that may be far larger than memory.

Every remaining algorithm in this unit attacks one of those two problems.

3.5 The Partition algorithm

Scan 1:  for each partition i:
             find ALL locally frequent itemsets in partition i
             (in memory, with minsup applied to that partition's size)
         global candidates = UNION of all local frequent itemsets

Scan 2:  count every global candidate over the WHOLE database
         keep those meeting global minsup

3.6 The Pincer-Search algorithm

MFCS starts as the single itemset containing ALL items.
Each pass:
    count Cₖ (bottom-up) AND the members of MFCS (top-down)
    any MFCS member found frequent  → move to MFS; its subsets need no counting
    any infrequent itemset found    → SPLIT the MFCS members containing it

⚠️ Maximal versus closed itemsets

Another guaranteed two-mark question.

Every maximal itemset is closed; the converse is false.

3.7 Dynamic Itemset Counting (DIC)

Transactions:  |--M--|--M--|--M--|--M--|--M--|  (wraps around to the start)
Start counting  1-sets
       at M:    + any 2-set whose 1-subsets already look frequent
      at 2M:    + any 3-set whose 2-subsets already look frequent   ...

The trade-off

DIC's assumption is its weakness. It decides an itemset "looks frequent" from a prefix of the data. If the data is sorted — by date, by store, by category — that prefix is unrepresentative, DIC starts counting the wrong itemsets, and it can perform worse than Apriori. Shuffling the data first is not optional.

3.8 The FP-Growth algorithm

Step 1 — Build the FP-tree

Scan 1: count each item's support, discard infrequent items, and sort the rest by descending frequency (the F-list).

Scan 2: for each transaction, drop infrequent items, sort the rest into F-list order, and insert the resulting path into the tree, incrementing counts where a prefix already exists.

                    null
                   /    \
              B:4        C:1
             /   \          \
         C:3      E:1        A:1
          |
         E:3
          |
         A:2

Step 2 — Mine the tree, from the least frequent item upwards

For each item, find its conditional pattern base (the prefix paths ending at that item, with counts), build a conditional FP-tree, and recurse.

Item A (count 3, the last in the F-list):

Paths ending in A:  B:C:E:A with count 2   → prefix {B, C, E} : 2
                    C:A     with count 1   → prefix {C}       : 1

Conditional pattern base of A = { {B,C,E}: 2, {C}: 1 }

Counts within that base: B:2, C:3, E:2
Only C ≥ 3, so the conditional FP-tree for A is a single node C:3.

Frequent patterns ending in A:  {A}: 3,  {C,A}: 3

Item E (count 4):

Paths ending in E:  B:C:E with count 3  → prefix {B, C} : 3
                    B:E   with count 1  → prefix {B}    : 1

Conditional pattern base of E = { {B,C}: 3, {B}: 1 }
Counts: B:4, C:3 — both ≥ 3.

Conditional FP-tree for E:  B:4 → C:3

Mining it recursively gives:  {E}: 4,  {B,E}: 4,  {C,E}: 3,  {B,C,E}: 3

Item C (count 4):

Paths ending in C:  B:C with count 3 → prefix {B}: 3
                    C:1              → prefix {} : 1
Counts: B:3 ≥ 3.
Frequent patterns:  {C}: 4,  {B,C}: 3

Item B (count 4, first in the F-list, so no prefixes): {B}: 4

Collected result: {A}:3, {B}:4, {C}:4, {E}:4, {C,A}:3, {B,C}:3, {C,E}:3, {B,E}:4, {B,C,E}:3.

Nine frequent itemsets — identical to Apriori's answer. Note that Apriori wrote {A,C} and FP-Growth writes {C,A}; itemsets are unordered, so these are the same set. The two algorithms must always agree; they differ only in how they get there.

3.9 Generalized association rules

                    Food
            ┌────────┴────────┐
        Dairy               Bakery
      ┌───┴───┐           ┌───┴────┐
   Milk    Cheese      Bread   Croissant
   ┌─┴──┐
 Amul  Nandini

The three strategies

Uniform support's dilemma is the exam point. Set minsup high enough to control the number of Dairy → Bakery-level rules and no individual product passes; set it low enough for products and the upper levels produce an unmanageable flood. Reduced support exists precisely because one threshold cannot serve both.

⚠️ Redundant ancestor rules

If Milk → Bread has confidence 80%, and Amul Milk is 25% of all milk, then Amul Milk → Bread at confidence ≈ 80% tells you nothing new — it is the expected consequence of the ancestor rule.

A descendant rule is redundant if its support and confidence are close to what the ancestor rule predicts. Only report a descendant rule when it deviates — if Amul Milk → Bread had confidence 95%, that is a real finding.

3.10 Association rules with item constraints

Unconstrained mining produces far too many rules, most of them uninteresting. Constraints let the user say what they are looking for — and, crucially, good constraints can be pushed into the mining algorithm rather than applied to its output, which is where the speed comes from.

Practice problems

lift({A,E} → {B}) = 1.00 / (7/9) = 1.00 / 0.778 = 1.286
lift({E} → {A,B}) = 1.00 / (4/9) = 1.00 / 0.444 = 2.250

                     null
                   /      \
                B:7        A:2
              /  |  \         \
          A:4   C:2  D:1       C:2
         / | \
      E:1 D:1 C:2
               |
              E:1

From E:1 under B → A         →  {B, A} : 1
From E:1 under B → A → C     →  {B, A, C} : 1

Conditional pattern base of E = { {B,A}: 1, {B,A,C}: 1 }

Counts within the base:  B: 1+1 = 2 ✓,  A: 1+1 = 2 ✓,  C: 1 ✗

Conditional FP-tree for E:  B:2 → A:2

N = 1000
σ(tea) = 600,  σ(coffee) = 750,  σ(tea ∪ coffee) = 400

support    = 400/1000              = 0.40   (40%)
confidence = 400/600               = 0.667  (66.7%)
lift       = 0.667 / (750/1000) = 0.667 / 0.75 = 0.889

Exam questions from this unit

Two marks

1. Define support, confidence and lift.
2. State the Apriori principle.
3. What is the anti-monotone property?
4. Why is confidence alone misleading?
5. Distinguish a maximal from a closed frequent itemset.
6. How many itemsets are possible with d items?
7. How many rules can a frequent k-itemset generate?
8. Why does FP-Growth sort items by descending frequency?
9. What is a conditional pattern base?
10. Distinguish an anti-monotone from a monotone constraint.

Five marks

1. Explain the Apriori algorithm with a worked example.
2. Explain rule generation from frequent itemsets.
3. Explain the Partition algorithm and prove its completeness.
4. Explain Pincer-Search and when it outperforms Apriori.
5. Explain Dynamic Itemset Counting.
6. Explain generalized (multi-level) association rules.
7. Explain constraint-based mining and the constraint types.

Ten marks

1. Given a transaction database, apply Apriori fully — all passes, all candidate generation and pruning, all frequent itemsets, all strong rules with support, confidence and lift.

2. Construct an FP-tree for a given database and mine it completely, showing every conditional pattern base and conditional tree.

3. Compare Apriori and FP-Growth exhaustively, with a worked example of each on the same data.

Mistakes that cost marks