--- title: "Apriori on restaurant orders" subject: "Data Mining" chapter: 4 key: "semester_7/data_mining:apriori-restaurant" source: https://www.bctengineer.com/q/semester_7/data_mining/apriori-restaurant site: BCT Engineering --- # Apriori on restaurant orders Data Mining · Chapter 4: Association Analysis - Asked in: year not given, 4+8 marks - Video: [#2 Solved Example Apriori Algorithm to find Strong Association Rules Data Mining Machine Learning](https://www.youtube.com/watch?v=zi_ydmbWfAs) — Mahesh Huddar - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/data_mining/apriori-restaurant - Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4 ## Question Write the A-priori algorithm with its pruning principle. Find the candidate and large item sets from the following transaction in a restaurant using A-priori algorithm. (Min. support: 2) | Transaction ID | Order Combination | | --- | --- | | 1 | Beer, chicken, peanut | | 2 | Whisky, buff, coke, lemon | | 3 | Beer, buff, coke, lemon | | 4 | Buff, coke, peanut | | 5 | Beer, peanut, lemon, fish | | 6 | Peanut, coke | ## Short answer Apriori with min support 2 on restaurant orders. L1={Beer,buff,coke,lemon,peanut}. L2={Beer-lemon, Beer-peanut, buff-coke, buff-lemon, coke-lemon, coke-peanut}. L3={buff,coke,lemon} (count 2). Pruning removes candidates with infrequent subsets like lemon-peanut. Algorithm stops as no C4 possible. ## Answer #### Apriori algorithm and pruning principle **Apriori principle**: if an itemset is frequent, all its subsets are frequent; so if an itemset is infrequent, no superset of it can be frequent. This **pruning** removes candidates without counting them. ```text L1 = frequent 1-itemsets (scan database) for k = 2; L(k-1) not empty; k++: Ck = join L(k-1) with itself prune candidates having an infrequent (k-1)-subset scan database, count Ck Lk = candidates with count >= min_support return all Lk ``` #### Solution (minimum support = 2 transactions) Transactions: T1 {Beer, chicken, peanut}; T2 {Whisky, buff, coke, lemon}; T3 {Beer, buff, coke, lemon}; T4 {buff, coke, peanut}; T5 {Beer, peanut, lemon, fish}; T6 {peanut, coke}. **C₁ and L₁** | Item | Count | Frequent? | | --- | --- | --- | | Beer | 3 | Yes | | chicken | 1 | No | | peanut | 4 | Yes | | Whisky | 1 | No | | buff | 3 | Yes | | coke | 4 | Yes | | lemon | 3 | Yes | | fish | 1 | No | L₁ = {Beer, buff, coke, lemon, peanut} **C₂** (all 10 pairs of L₁) **and L₂** | Itemset | Count | Frequent? | | --- | --- | --- | | Beer, buff | 1 | No | | Beer, coke | 1 | No | | Beer, lemon | 2 | Yes | | Beer, peanut | 2 | Yes | | buff, coke | 3 | Yes | | buff, lemon | 2 | Yes | | buff, peanut | 1 | No | | coke, lemon | 2 | Yes | | coke, peanut | 2 | Yes | | lemon, peanut | 1 | No | L₂ = {Beer-lemon, Beer-peanut, buff-coke, buff-lemon, coke-lemon, coke-peanut} **C₃** (join of L₂ pairs having the same first item, then prune) | Candidate | From | All 2-subsets frequent? | Count | | --- | --- | --- | --- | | Beer, lemon, peanut | Beer-lemon + Beer-peanut | No (lemon-peanut) → pruned | - | | buff, coke, lemon | buff-coke + buff-lemon | Yes | 2 (T2, T3) | | coke, lemon, peanut | coke-lemon + coke-peanut | No (lemon-peanut) → pruned | - | **L₃** = {buff, coke, lemon} (count 2). No C₄ can be formed, so the algorithm stops. **Answer: candidate sets C₁, C₂, C₃ as above. Large (frequent) itemsets: L₁ = {Beer, buff, coke, lemon, peanut}; L₂ = the six pairs; L₃ = {buff, coke, lemon}.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does the Apriori pruning principle say? A. If an itemset is infrequent, no superset of it can be frequent B. If an itemset is frequent, all its supersets are frequent C. Only itemsets with confidence above min_conf are kept D. Infrequent items must be counted again in the next level Answer: A. Supersets cannot have more support than their subsets, so supersets of infrequent itemsets are pruned. (Key point: Apriori principle) 2. With min support 2, which items are in L1? A. Beer, chicken, peanut, fish B. Beer, buff, coke, lemon, peanut C. All 8 items D. Only peanut and coke Answer: B. Chicken, whisky and fish each appear once (< 2), so they are dropped. (Key point: Frequent 1-itemsets) 3. Why is {Beer, lemon, peanut} pruned from C3? A. Its count was found to be 1 in a scan B. Beer-peanut is infrequent C. Its subset {lemon, peanut} is not frequent (count 1) D. It contains an item not in L1 Answer: C. Pruning checks subsets before counting; lemon-peanut has count 1 < 2. (Key point: Pruning in C3) 4. What is L3 and why does the algorithm stop? A. L3 = {Beer, lemon, peanut}; C4 is empty by pruning B. L3 has three itemsets; support falls below 2 at C4 C. L3 = {coke, lemon, peanut}; no more transactions remain D. L3 = {buff, coke, lemon} with count 2; no C4 can be formed from a single 3-itemset Answer: D. Only buff-coke-lemon survives (T2, T3), and one 3-itemset cannot be joined to form a 4-itemset. (Key point: Final result) ## Related in Data Mining - [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 - [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 t1-t5 with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-t1-t5-rules) — 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 HotDogs data with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-hotdogs-rules) — 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 ## Related in other subjects - [Restaurant information system requirements](https://www.bctengineer.com/question.md?key=semester_5%2Fsoftware_engineering%3Arestaurant-requirements) — Software Engineering, chapter 1 - [Second-order non-linear kinematic wave; FDM principle](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asecond-order-nonlinear-kinematic-principle) — Computational Techniques in Civil Engineering, chapter 5 - [Triangulation principle; 1st order trilateration](https://www.bctengineer.com/question.md?key=semester_3%2Fsurveying_i%3Atriangulation-principle-first-order-trilateration) — Surveying I, chapter 8 - [Triangulation principle; third-order specifications](https://www.bctengineer.com/question.md?key=semester_3%2Fsurveying_i%3Atriangulation-principle-third-order) — Surveying I, chapter 8