--- title: "Short note: Apriori and its drawbacks" subject: "Data Mining" chapter: 4 key: "semester_7/data_mining:apriori-note-drawbacks" source: https://www.bctengineer.com/q/semester_7/data_mining/apriori-note-drawbacks site: BCT Engineering --- # Short note: Apriori and its drawbacks Data Mining · Chapter 4: Association Analysis - Asked in: year not given, 3 marks; year not given, 4 marks - 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/apriori-note-drawbacks - Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4 ## Question Write a short note on the Apriori algorithm and its drawbacks. ## Short answer Apriori mines frequent itemsets using level-wise search and the Apriori property (all subsets of frequent itemset are frequent). Steps: find L1, generate candidates, prune using property, count support, repeat. Drawbacks: multiple database scans, huge candidate sets, high computation/memory, slow at low support or dense data, many uninteresting rules. ## Answer **Apriori** is the classic algorithm (Agrawal and Srikant, 1994) for mining frequent itemsets and association rules from transaction data. It uses a **level-wise, breadth-first search**: the frequent k-itemsets L_k are used to generate candidate (k+1)-itemsets, and the database is scanned to count their support. #### Key idea: the Apriori property All non-empty subsets of a frequent itemset must also be frequent; so any candidate with an infrequent subset is pruned without counting. #### Steps 1. Scan the database and find the frequent 1-itemsets L₁ (support ≥ min_sup). 2. **Join**: build candidates C_{k+1} from L_k. 3. **Prune**: remove candidates having an infrequent k-subset. 4. **Count**: scan the database to count support and obtain L_{k+1}. 5. Repeat until no new frequent itemsets are found; then generate rules X → Y with confidence ≥ min_conf. *Example*: {A, C, D}, {B, C, E}, {A, B, C, E}, {B, E} with min_sup = 2 give L₁ = {A, B, C, E}, L₂ = {AC, BC, BE, CE}, L₃ = {BCE}. #### Drawbacks - **Many database scans**: one scan for each level; for a frequent itemset of size n, n scans are needed. - **Huge candidate sets**: 10⁴ frequent 1-itemsets give over 10⁷ candidate 2-itemsets; very long patterns need up to 2¹⁰⁰ candidates. - **Heavy counting cost** (each candidate must be matched with every transaction), and a lot of memory. - Slow at **low minimum support** or on dense data. - Generates a very large number of rules, many uninteresting. Improvements: hashing (DHP), transaction reduction, partitioning, sampling, dynamic itemset counting, and the FP-growth algorithm. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does the Apriori property allow the algorithm to do? A. Prune any candidate that has an infrequent subset without counting it B. Skip the first database scan C. Count only the itemsets with the highest confidence D. Guarantee every candidate is frequent Answer: A. All subsets of a frequent itemset must be frequent, so a candidate with an infrequent subset cannot be frequent and is pruned. (Key point: Apriori property) 2. How does Apriori generate candidates? A. Every possible itemset is generated at once B. Frequent k-itemsets L_k are used to build candidate (k+1)-itemsets, level by level C. Candidates are built from infrequent itemsets D. It builds a tree and mines it recursively Answer: B. Apriori is a level-wise, breadth-first search: L_k gives C_(k+1), which is then counted in a database scan. (Key point: Level-wise search) 3. For a frequent itemset of size n, how many database scans does Apriori need? A. Exactly 2 scans B. 1 scan C. n scans, one per level D. 2^n scans Answer: C. One scan is needed for each level, so many scans are needed for long patterns. (Key point: Database scans) 4. 10^4 frequent 1-itemsets lead to how many candidate 2-itemsets? A. About 10^4 B. About 10^3 C. Fewer than 10^5 D. More than 10^7 Answer: D. All pairs of frequent items are candidates, giving about n(n-1)/2, which is over 10^7 for n = 10^4. (Key point: Candidate explosion) ## Related in Data Mining - [Association analysis and Apriori pruning](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aassociation-apriori-pruning) — Data Mining, chapter 4, asked 2× - [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 four transactions, support 2](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-y63-min-support-2) — Data Mining, chapter 4 - [Apriori advantages and disadvantages](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-pros-cons) — 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 HotDogs data with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-hotdogs-rules) — Data Mining, chapter 4 ## Related in other subjects - [Greedy best-first drawbacks; A*](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Agreedy-best-first-vs-astar) — Artificial Intelligence, chapter 3