6. Frequent Itemsets

Question 1

What is the market basket model?

Answer 1

Depicts data as a large set of items which may fall into any number of a large amount of baskets. Each basket is a small subset of items

Question 2

What is the goal of the market basket model?

Answer 2

We want to find association rules.
Ex: People who bought {x, y, z} tend to buy {v, w}

Question 3

What is support?

Answer 3

The number of baskets containing all items in I for a given itemset I

Question 4

What is a frequent itemset?

Answer 4

Sets of items that appear in at least s baskets where s is the support threshold

Question 5

What is an association rule?

Answer 5

If-then rules about the contents of a basket
{i1, i2, …, ik} -> j means if a basket contains i1…ik it is likely to contain j

Question 6

How do we calculate the confidence of an association rule?

Answer 6

conf(I -> j) = support(I U j) / support(I)

Question 7

How do we calculate the interest of an association rule and when do we say a rule is interesting?

Answer 7

Interest(I -> j) = conf(I -> j) - Pr[j]
Interesting rules have high positive or negative interest values (usually above 0.5)

Question 8

What is the process for mining association rules?

Answer 8

1. Find all frequent itemsets I
2. For every subset A of I generate rule A -> I \ A
3. Output rules above the confidence threshold

The rationale behind this is that since I is frequent, A is also frequent

Question 9

What is the bottleneck for finding frequent itemsets?

Answer 9

Main memory is the bottleneck.
We need to count something within the baskets but the number of different things we can count is limited by main memory

Question 10

What is the hardest problem for finding frequent itemsets and why?

Answer 10

Finding frequent pairs is hardest because frequent pairs are common and we don’t have enough memory to store them all. The probability of being frequent drops exponentially with size.

Question 11

What is the naive algorithm for finding frequent pairs?

Answer 11

Read the file once, counting in main memory the occurrences of each pair.

From each basket of n items we generate its n(n-1)/2 pairs by two nested loops

Question 12

What is the issue with the naive algorithm for finding frequent pairs?

Answer 12

It fails if the number of items squared exceeds main memory

Question 13

What is the triangular matrix approach to counting frequent pairs?

Answer 13

We count a pair of items {i, j} if i < j
Keep pair counts in lexicographic order

Question 14

What is the triples approach to counting frequent pairs?

Answer 14

We keep a table of triples [i, j, c] where the count of the pair {i, j} is c

Question 15

How much memory is used by the triangular matrix and triples approach for counting frequent pairs?

Answer 15

Triangular matrix uses 4 bytes per pair
Triples uses 12 bytes per occurring pair but only for pairs with count > 0

Question 16

When is the triples approach for counting frequent pairs better than triangular matrix?

Answer 16

It is better if less than 1/3 of possible pairs actually occurs

Question 17

What is the issue with the triples and triangular matrix approaches to counting frequent pairs?

Answer 17

We may not have enough memory to fit the pairs. Swapping counts in and out of disk is not a good solution

Question 18

What are the 2 key ideas that they A-Priori algorithm is based on?

Answer 18

1. Monotonicity: If a set of items I appears at least s times so does every subset of I
2. Contrapositive for pairs: If item i does not appear in s baskets then no pair including i can appear in s baskets

Question 19

What happens during the first pass of the A-Priori algorithm?

Answer 19

Read baskets and count in main memory the occurrences of each individual item. Any items that appear more than s times are frequent

Question 20

What happens during the second pass of the A-Priori algorithm?

Answer 20

Read baskets again and count in main memory only the pairs where both elements are frequent

Question 21

What memory is required for each pass of the A-Priori algorithm?

Answer 21

Pass 1: Memory proportional to number of items
Pass 2: Memory proportional to square of frequent items only plus a list of frequent items so you know what needs to be counted

Question 22

How do we generalize A-Priori to work for frequent triples and above?

Answer 22

1. For each k we construct 2 sets of k-tuples
2. Ck are the candidate k-tuples that may be frequent sets based on information from the pass for k-1
3. Lk contains the set of truly frequent k-tuples
4. We start with all the items
5. Count the items to get the set of frequent items
6. Construct a new set of potential 2-tuples using results from above
7. Repeat

Question 23

What is the issue with the A-Priori algorithm?

Answer 23

In pass 1, most memory is idle. We are only storing individual item counts

Question 24

What do we do in the first pass of the PCY algorithm that is different from A-Priori?

Answer 24

We maintain a hash table with as many buckets as fit in memory in addition to item counts. We keep a count for each bucket into which pairs of items are hashed. We do not record the pair, just the count that hash to the bucket

Question 25

What does the count of a PCY bucket tell us?

Answer 25

If total count is less than s, none of its pairs can be frequent.
If a bucket contains a frequent pair then the bucket is frequent

Question 26

What do we do during the second pass of the PCY algorithm?

Answer 26

Only count pairs that hash to buckets found to be frequent

Question 27

What memory is required for each pass of the PCY algorithm?

Answer 27

Pass 1: Memory for item counts and a hash table for pairs
Pass 2: Memory for frequent items, buckets represented as a bitmap, and counts of candidate pairs