4. Assume you are given the following collection of twelve baskets, each of whic

Question

4. Assume you are given the following collection of twelve baskets, each of which containing three of the six items 1 through 6:

{1, 2, 3} {2, 3, 4} {3, 4, 5} {4, 5, 6}
{1, 3, 5} {2, 4, 6} {1, 3, 4} {2, 4, 5}
{3, 5, 6} {1, 2, 4} {2, 3, 5} {3, 4, 6}

Suppose the support threshold is 4. On the first pass of the PCY Algorithm we use a hash table with 11 buckets, and the set {i, j} is hashed to bucket i×j mod 11.

a) By any method, compute the support for each item and each pair of items.
b) Which pairs hash to which buckets?
c) Which buckets are frequent?
d) Which pairs are counted on the second pass of the PCY Algorithm?

Explanation / Answer

The original application of the market-basket model was in the analy

sis of true

market baskets. That is, supermarkets and chain stores record

the contents

of every market basket (physical shopping cart) brought to the

register for

checkout. Here the “items” are the different products that the s

tore sells, and

the “baskets” are the sets of items in a single market basket. A maj

or chain

might sell 100,000 different items and collect data about millions of mark

et

baskets.

By finding frequent itemsets, a retailer can learn what is commonly bo

ught

together. Especially important are pairs or larger sets of items tha

t occur much

more frequently than would be expected were the items bought inde

pendently.

We shall discuss this aspect of the problem in Section 6.1.3, but for th

e moment

let us simply consider the search for frequent itemsets. We will disco

ver by this

analysis that many people buy bread and milk together, but that is of

little

interest, since we already knew that these were popular items individ

ually. We

might discover that many people buy hot dogs and mustard togethe

r. That,

again, should be no surprise to people who like hot dogs, but it offers t

he

supermarket an opportunity to do some clever marketing. They ca

n advertise

a sale on hot dogs and raise the price of mustard. When people come t

o the

store for the cheap hot dogs, they often will remember that they

need mustard,

and buy that too. Either they will not notice the price is high, or they

reason

that it is not worth the trouble to go somewhere else for cheaper mu

stard.

The famous example of this type is “diapers and beer.” One would hard

ly

expect these two items to be related, but through data analysis on

e chain store

discovered that people who buy diapers are unusually likely to buy bee

r.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.