Quiz 3

Question 1

1. How does the A-priori algorithm work? In particular, how does A-priori generate candidate itemsets and prune non-frequent itemsets? You can choose to explain with an example or explain it with an algorithm.

Answer 1

With shelf management we look at:
-items purchased by customers

A-Priori Steps:
-Count the occurrences
-Record the item counts
-Record the frequent items
-Generate Pairs
-Candidate pairs + occurrences (C2)
-Prune non frequent pairs (L2)

Question 2

2. How does the Park-Chen-Yu algorithm improve the A-priori algorithm? Explain your answer. [Hint: Explain how does they PCY discard non-frequent itemsets].

Answer 2

PCY uses hash tables in which can be more efficient. It counts pairs that hash to frequent buckets.

Pass 1:
-Counts items
-Creates hash
-hash pairs items into buckets and count

Pass 2:
-Converts count to bit-vector = frequent buckets
-Counts pairs that hash to frequent buckets

Pass 3:
-Generate triplets
-Prune non frequent

Question 3

3. Consider a transactional database where milk and diapers are bought together 25 times. If milk alone (the only item in a basket/receipt) is bought at least 5 times, what is the least number of transactions in the database?
   A. 15
   B. 25
   C. 30
   D. 35

Answer 3

C. 30

Question 4

4. What is the main goal of the market-based model for frequent itemset mining in supermarket shelf management?
   a. Maximize the number of items on the shelf
   b. Identify items that are bought together by sufficiently many customers
   c. Minimize the sales data collected with barcode scanners
   d. Reduce the variety of products in the supermarket

Answer 4

b. Identify items that are bought together by sufficiently many customers

Question 5

5. What is the key concept exploited by the Apriori algorithm to efficiently mine frequent itemsets?
   A. Association rule generation
   B. Monotonicity
   C. Support count pruning
   D. Non-binary data handling

Answer 5

C. Support count pruning

Question 6

6. Which Data structure is used for storing item set counts in the PCY algorithm?
   A. Hash table
   B. Priority Queues
   C. Stack
   D. Double array (Matrix)

Answer 6

A. Hash table

Question 7

7. What is the main memory requirement for the A-Priori algorithm?
   A. Proportional to the number of frequent items
   B. Proportional to the square of frequent items
   C. Proportional to the size of the dataset
   D. Proportional to the number of baskets

Answer 7

A. Proportional to the number of frequent items

Question 8

8. True | False The Park-Chen-Yu (PCY) algorithm can eliminate potential candidate pairs even if the candidate pair consists of two frequent items.

Answer 8

True

Question 9

9. True | False If item I does not appear in s baskets, then no pair including i can appear in s baskets.

Answer 9

True

Question 10

10. True | False A-priori algorithm is more efficient in mining frequent itemsets from large datasets.

Answer 10

True

Question 11

11. True | False An item can be part of a frequent itemset even if it is individually not a frequent item.

Answer 11

False

Question 12

12. True | False The PCY algorithm exploits idle memory on the first pass to reduce memory required in the second pass.

Answer 12

True

Question 13

13. True | False Pairs that hash to a bucket with total count less than support threshold can be eliminated as candidates in PCY algorithm.

Answer 13

True