Write and explain the Apriori Algorithm used to identify frequently occurring elements and meaningful associations in a dataset.

🔥 Asked 5/10 papers📅 Last: Dec 2024📚 Mining Frequent Patterns

Dec 2021Jun 2023Dec 2023Dec 2024

Model Answer

The Apriori Algorithm is a classic algorithm used in Association Rule Mining to identify frequent itemsets in a transactional database. The name "Apriori" comes from the Latin term meaning "from before" — it uses prior knowledge of frequent itemset properties. The key principle is the Apriori Property: all subsets of a frequent itemset must also be frequent.

1Key Terminology

Before the algorithm: understand these terms. • Itemset: A collection of one or more items, e.g., {Bread, Milk} • Support Count: Number of transactions containing an itemset • Support (%) = (Transactions with itemset / Total transactions) × 100 • Minimum Support (min_sup): Threshold — itemsets below this are pruned • Frequent Itemset: An itemset whose support ≥ min_sup • Apriori Property: If an itemset is frequent, ALL its subsets must also be frequent. (Used for pruning)

2Apriori Algorithm — Pseudocode

Step 1 — Generate C1

Scan the entire database D to find the support count of each individual item. Create candidate 1-itemset C1.

Step 2 — Prune to L1

Eliminate candidates from C1 whose support count is less than min_sup. The remaining itemsets form the frequent 1-itemset L1.

Step 3 — Generate Ck from Lk-1

Join Lk-1 with itself to generate candidate k-itemsets Ck. Two itemsets are joined if they share (k-2) items as a common prefix.

Step 4 — Apply Apriori Pruning

For each candidate in Ck, check if all its (k-1)-subsets are in Lk-1. If any subset is NOT frequent, remove the candidate (Apriori property).

Step 5 — Scan and count

Scan database D to find the support count of each surviving candidate in Ck.

Step 6 — Prune to Lk

Remove candidates from Ck with support < min_sup. Remaining = Lk (frequent k-itemsets).

Step 7 — Repeat

Repeat Steps 3–6 with k = k + 1 until no new frequent itemsets are found.

3Worked Example

Transactions (min_sup = 2, min_conf = 60%): T1: {Bread, Milk} T2: {Bread, Diaper, Beer, Egg} T3: {Milk, Diaper, Beer, Cola} T4: {Bread, Milk, Diaper, Beer} T5: {Bread, Milk, Diaper, Cola} Step 1 — C1 (1-itemsets): Count each item. Prune those with support < 2. Frequent 1-itemsets L1 = {Bread(4), Milk(4), Diaper(4), Beer(3), Cola(2)} Step 2 — C2 (2-itemsets): Generate pairs from L1. Count support. Prune. Frequent 2-itemsets L2 = {{Bread,Milk}(3), {Bread,Diaper}(3), {Milk,Diaper}(3), {Beer,Diaper}(3)} Step 3 — C3 (3-itemsets): Generate triples from L2 pairs sharing a (k-1) prefix. L3 = {{Bread,Milk,Diaper}(3)} Algorithm terminates — no more frequent itemsets to generate.

4Advantages and Disadvantages

Advantage 1

Easy to understand and implement. The Apriori property provides an efficient pruning strategy that reduces the number of candidates.

Advantage 2

Works well on sparse datasets where most items are infrequent — large portions of the search space are pruned early.

Disadvantage 1

Requires multiple scans of the entire database — one scan per itemset level. This is very slow for large databases.

Disadvantage 2

Generates a huge number of candidate itemsets in the intermediate steps, consuming significant memory and I/O.

Key Formulas

Support(X) = (|Transactions containing X| / |Total Transactions|) × 100

Confidence(X→Y) = Support(X ∪ Y) / Support(X)

Lift(X→Y) = Confidence(X→Y) / Support(Y)

Apriori Property: if itemset X is frequent, then all subsets of X are also frequent

💡 Exam Tip

Write the pseudocode step-by-step. Always include a worked example — a table of transactions with support counts gets you the most marks. Remember: minimum support threshold is used to prune itemsets. This question has appeared in Dec 2023, Dec 2024, and Jun 2023 — prepare it thoroughly.

Resources

▶️

Apriori Algorithm with Example — Jenny's Lectures

Step-by-step Apriori algorithm with worked example

📄

IGNOU MCS-221 Block 3 — Unit 9: Frequent Pattern Mining

Official IGNOU material — Unit 9 covers Apriori in detail