---
title: "Association analysis and Apriori pruning"
subject: "Data Mining"
chapter: 4
key: "semester_7/data_mining:association-apriori-pruning"
source: https://www.bctengineer.com/q/semester_7/data_mining/association-apriori-pruning
site: BCT Engineering
---

# Association analysis and Apriori pruning

Data Mining · Chapter 4: Association Analysis

- Asked in: 2066 Bhadra, 2+6 marks; year not given, 2+8 marks; year not given, 2+6 marks; 2065 Baisakh; year not given (asked 2 times)
- Video: [Lec - 18: Apriori Algorithm in Data Mining | Real Life Example](https://www.youtube.com/watch?v=o_hnNBM0jtk) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/association-apriori-pruning
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4

## Question

What is association analysis? Write the A-priori algorithm with its pruning principle (explain the Apriori principle and the algorithm for frequent itemset generation).

## Short answer

Association analysis discovers rules X→Y with support and confidence. The Apriori principle: all subsets of a frequent itemset are frequent; thus, any itemset with an infrequent subset is pruned. Algorithm: find frequent 1-itemsets; repeatedly join frequent (k-1)-itemsets, prune using subset criterion, and scan database for support until no new frequent itemsets.

## Answer

#### Association analysis
**Association analysis** (association rule mining) discovers interesting relations, in the form of rules X → Y, among items in large transaction data. *Example*: {bread, butter} → {milk} [support 5%, confidence 80%] means 80% of customers who buy bread and butter also buy milk.

- **Support**(X → Y) = (transactions containing X ∪ Y)/(total transactions)
- **Confidence**(X → Y) = support(X ∪ Y)/support(X)

The task has two steps: (1) find all **frequent itemsets** (support ≥ minsup), (2) generate **strong rules** from them (confidence ≥ minconf). Step 1 is the expensive one, as N items give 2ᴺ − 1 candidate itemsets.

#### Apriori principle
> If an itemset is frequent, then **all of its subsets must also be frequent**.

Equivalently, if an itemset is infrequent, all its supersets are infrequent. This follows from the **anti-monotone** property of support: s(X) ≥ s(Y) whenever X ⊆ Y.

#### Pruning
If {A, B} is infrequent, then {A, B, C}, {A, B, D}, {A, B, C, D} … are not counted at all. During candidate generation, any (k+1)-itemset that has a k-subset not in L_k is removed **before** the database is scanned. This greatly reduces the search space.

#### Apriori algorithm
```text
L1 = frequent 1-itemsets                  (scan database)
for (k = 2; L(k-1) not empty; k++):
    Ck = join L(k-1) with itself          (join step)
    remove from Ck every candidate having an
        infrequent (k-1)-subset           (prune step)
    scan database; count support of each candidate in Ck
    Lk = candidates in Ck with support >= minsup
answer = union of all Lk
```
**Join step**: two frequent (k−1)-itemsets that share the first (k−2) items are joined: {A, B} and {A, C} give {A, B, C}.

#### Small example (minsup = 2 transactions)
T: {A, C, D}, {B, C, E}, {A, B, C, E}, {B, E}.
- L₁ = {A:2, B:3, C:3, E:3}; D (1) is dropped.
- C₂ counts: AB 1, AC 2, AE 1, BC 2, BE 3, CE 2 → L₂ = {AC, BC, BE, CE}.
- Joining BC and BE gives {B, C, E}; all its 2-subsets are in L₂, so it is kept; count = 2 → L₃ = {BCE}. {A, B, C} is never counted: the join does not produce it, and it would be pruned anyway because {A, B} is infrequent.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. The Apriori principle states:
   A. If an itemset is frequent, all its subsets are frequent
   B. If frequent, all supersets are frequent
   C. Subsets of infrequent sets are frequent
   D. Support increases with itemset size
   Answer: A. Support is anti-monotone. (Key point: Apriori principle)

2. Confidence of X -> Y is:
   A. support(X u Y)/support(Y)
   B. support(X u Y)/support(X)
   C. support(X)/support(Y)
   D. support(X) x support(Y)
   Answer: B. Fraction of X-transactions that also contain Y. (Key point: Confidence)

3. The prune step removes a candidate when:
   A. Its support is above minsup
   B. It has fewer than k items
   C. Any of its (k-1)-subsets is infrequent
   D. It has no common first items
   Answer: C. Done before scanning the database. (Key point: Prune step)

4. Which itemsets are joined to make {A,B,C}?
   A. {A,B} and {C,D}
   B. {B,C} and {D,E}
   C. {A} and {B,C} only
   D. {A,B} and {A,C}, sharing the first k-2 items
   Answer: D. Join frequent (k-1)-itemsets sharing first k-2 items. (Key point: Join step)

## Related in Data Mining

- [Apriori on HotDogs data with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-hotdogs-rules) — Data Mining, chapter 4
- [Apriori on restaurant orders](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-restaurant) — Data Mining, chapter 4
- [FP-Growth and Apriori disadvantage](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-growth-vs-apriori) — Data Mining, chapter 4
- [Apriori on 8 transactions, 25% support](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-b65-transactions) — Data Mining, chapter 4
- [Apriori on t1-t5 with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-t1-t5-rules) — Data Mining, chapter 4
- [Association rules, support, confidence](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aassociation-rule-support-confidence) — Data Mining, chapter 4

## Related in other subjects

- [Dependency, association, aggregation, realization](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Afour-primary-class-relations) — Object Oriented Analysis and Design, chapter 2
- [Conventional vs renewable energy for generation](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Aconventional-vs-renewable-generation) — Power System Analysis I, chapter 1, asked 2×
- [Why generation and distribution voltages are lower](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Ageneration-distribution-lower-voltage) — Power System Analysis I, chapter 1
- [Reactive power injection and generation limits](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Areactive-power-injection-limits) — Power System Analysis II, chapter 1