The study of how we find
frequent itemsets was one of
the earliest directions taken
by data mining researchers.
And the A-Priori algorithm is probably the
most sited work in the data mining field.
The motivation for this study
was to determine unusual sets of
items that people purchase
together in supermarkets.
No discussion of finding frequent
itemsets would be complete without
mentioning the possibly
apocryphal story of beer and
diapers, and
we'll tell that one soon enough.
but, in rough outline,
we're going to start with a model of
data called The Market-Basket Model,
where data consists of sets of items,
the sets are called baskets for
a reason we'll discuss.
And a set of items is called
frequent if it appears in some large
number of baskets.
We'll talk about association rules which
are statements that when a certain set of
items are found in a basket then it is
unusually likely that another items will
also be found there.
And finally we'll give A-Priori algorithm
for finding frequent item sets.
This algorithm while it has been
improved upon over the years
is the fundamental starting point for
all of these improvements.
The Market-Basket model is essentially
a representation of the many,
many relationships between two concepts,
which we'll call items in baskets.
On one hand, there's a large set of items.
An example is all the different
items Wal-Mart sells.
Of which there are hundreds of thousands.
This was the original
purpose of the model,
analyzing the things
people bought at a store.
However the model has many
other applications, a,
a few of which we'll talk about shortly.
And then on the other hand,
there's a large set of baskets.
Each basket contains a small set of items.
The original picture was that
a market basket was a shopping cart,
a physical, that is not electronic.
And customer's would wheel their
market basket up to the check-out.
The cash register would group all the
items in the basket together in one bill,
and that bill would be stored
in the store's computer system.
Plus by mining the contents of
the various market baskets.
The store can learn what
people bought together.
A hamburger and ketchup for example.
And that in turn would let the store
figure out some ploys to increase sales.
Think about what a store might
do to exploit this information.
We're going to return
to the subject shortly.
The most useful, and
also the most basic question to ask about
data in the form of market baskets is to
find those sets of items that appear
in some minimum number of baskets.
Define the support for
an itemset to be the number of baskets
of which that itemset is a subset.
We can give the support either
as an absolute number or
as a percentage of all the baskets.
Data mining problem called frequent
itemsets involve a number or
percentage s called the support threshold.
Any set of items with support at
least s is called a frequent itemset
'Kay, here's a very simple example
of data in the market basket model.
Okay, there are five items, milk,
Coke, Pepsi, beer and juice.
The support threshold will be three,
it's an absolute number not
a percentage of the baskets.
Here are the baskets.
We're using M for milk; C for coke; and
you can probably figure out the rest.
Now, what are the frequent itemsets?
Well, almost all
the singletons are frequent.
Each of the items except Pepsi
appears in at least three baskets For
example, beer appears in b1,
b3, b5, b7, b6 and b8.
'Kay.
Pepsi itself is not frequent because
it appears only in B2 and B5.
There are also some frequent doubletons.
For example, milk and beer appear
together in the four baskets shown.
And beer and
Coke also appear in four baskets.
And finally, Coke and ju-
juice appear together in three baskets.
But no other doubletons are frequent.
For example, milk and
juice appear together in B2 and B6.
But in no other baskets, okay?
Also, there are no sets with three or
more items that are frequent.
So we're done.
We have found all the frequent items sets.
One might have included the empty set,
that is surely a subset
of all eight baskets.
But the fact is uninteresting and
we usually ignore the empty set.
As I mentioned, the,
the original application for
this sort of analysis was looking at the
things people bought together in a store.
In this case the items really
are the items one might buy, and
the baskets are sets of items
bought together by one purchaser.
There's a story that the first
interesting discovery of
a frequent item set was that diapers and
beer were frequently bought together.
And once you think about
it it makes sense.
If you're buying diapers you
probably have a baby at home.
If you have a baby at home you probably
aren't going out to a bar to drink.
So you bring the beer home.
I have heard several people claim that
they themselves discovered this, so
I suspect that really nobody did and it's
just an illustration of something that you
wouldn't think of without a way to
analyze massive amounts of data but
which proves to be true and
explainable rationally once you see it.
Okay.
The first thing marketers did
with information like this was to
reorganize their shelves.
They would put the diapers and
beer near each other, but
put another item that made sense
between them, like potato chips.
But there is a more subtle way to
exploit the data mining discovery.
Suppose we want a, a sale on diapers,
but we raise the price of beer.
People will come in to buy
the cheap diapers, and
while they are there in store,
they are likely to pick up some beer,
not noticing the price is too high,
or even if they do.
Figuring it doesn't make sense to drive
to another store just to buy beer.
Everybody wins.
The customer doesn't lose money.
And the store gets more customers and
on average receives the same
amount from each customer.
Only the competitors of the store
who don't have their own
data mining experts lose.
Incidentally, a subtle point here is
that there is causality operating.
And it's very hard to
deduce causality from data.
That is, if you don't think about
the causes underlying the data,
you might imagine that you could
just as well run a sale on beer and
raise the price of diapers.
But people who come in for
the sale on beer are not going to buy
diapers if they don't have a baby.
I just want to point out that these
techniques are appropriate mainly for
brick and mortar stores.
A brick and mortar store needs to know
that lots of people buy diapers and
beer, or else they're wasting time and
money optimizing the sale of something
that is rarely bought anyway.
That viewpoint matches well with
the idea that we're looking for
high frequency rather than correlation
between rarely purchased sets of items.
Online stores, on the other hand, do not
need to rely on high frequencies since
they can tailor their store
differently for each customer.
Thus, entirely different forms
of analysis are leaded, are,
are needed for online stores, and
we'll cover that as a separate topic.
Here's another problem that
uses the same data model with
an entirely different interpretation.
Suppose our data is
a collection of documents.
Think of the sentences that appear in
one or more documents as a basket.
The items are the documents themselves,
and the basket corresponding to
a sentence contains all the documents
in which that sentence appears.
Now what does it mean if a set of items
appears together in many baskets?
The item set is a set of documents.
And these documents or
items appear in a lotta baskets together.
That means there's a collection
of documents in which a lot of
the same sentences appear.
Documents that look like that may
well be an instance of plagiarism.
It is interesting to note
that in this case the items,
the documents are not in
the baskets which are sentences.
In, in fact it's the other way around.
But as we mentioned, items in baskets
form a many to many relationship, and
you can always view such
a relationship from either side.
However, when it comes to the algorithms
we'll discuss there is an asymmetry.
We assume that baskets contain
small numbers of items,
while items can be in very very
large number of, of baskets.
The algorithms would take too much time if
baskets contain large numbers of items,
because the work done processing
each basket is normally quadratic in
the number of items it contains.
Here's another application
involving documents.
Let the baskets now be the documents and
let the items be words.
We can think of a basket, a document
that is as the set of words it contains.
But remember what we just said we have to
be careful that the average basket doesn't
contain too many items.
If documents are books for
example it would contain thousands of
different words but if documents
are tweets or emails we're okay.
Because these are typically short in the
case of tweets they're necessarily short.
We can cut down on the number
of words in the document by
ignoring stop words as well the common,
these are the common little words that
usually don't carry any
significant meaning.
Now what does it mean if
a set of items is frequent.
That means, we have a set of
words that appear together in
a large number of documents.
By the way, that's another reason
to get rid of all the words that
are not pretty rare.
Or we'll just discover
the words like the and,
and, appear together in many documents.
That's a big deal, right?
On the other hand,
if rare words are, are relatively,
frequently found in the same documents.
And there might be some
connection between the words.
Supposing say that Brad and Angelina might
be two such words or is that old news?
Probably is.
Anyway just to remind you of the scale of
the sort of problem we're thinking about.
If we're dealing with real market
baskets a big store like Wal-Mart will
sell a hundred thousand different items,
and
stores billions of baskets in
its database for analysis.
On the other hand,
the web has billions of different words,
most of them by the way are misspellings,
and many billions of pages
Often the problem of finding frequent item
sets is characterized is the problem of
discovering association rules.
These are rules that say, if a basket
contains some collection of items,
then it is also likely to
contain another particular item.
The notation for association
rules that we use, is shown here.
Informally if we assert an association
rule that says, i1 through ik, implies j.
We mean that if a basket
contains all of i1 through ik,
then it is likely to contain j as well.
The degree to which this event is likely
is called the confidence of the rule.
It's the fraction of the baskets
containing i1 through ik that
also contain j.
For example,
here are the eight baskets we saw earlier.
A possible association rule is this.
Milk and beer imply Coke.
Let's focus on the four baskets
that have both milk and beer.
We see that B1 and B6 do have Coke.
While B3 and B5 do not.
Plus two out of the four
baskets with milk and
beer do have Coke and
the confidence of this rule is 50%.
[SOUND] One reasonable thing to
do with market basket data is
to find all association rules
that have a minimum support s.
And in minimum confidence c.
For some values of s and c that you
decide on before you run the algorithms.
The support of an association rules
the support side to the left of the arrow.
That is it is the number of baskets
containing all the items on the left.
The hard part of finding association rules
is really finding the frequent itemsets.
If an association rule like
this has support s, then
the set on the left will be frequent with
support s, that is the set i1 through ik.
But if the confidence of
the rule is also high.
That is the confidence c is close to 1,
then the set of items with j,
the item on the right thrown
in will have support cs.
Now if c is large then cs would be
close to s, say perhaps, one-half of s.
Okay, and here's a recipe for
finding all the association rules
that support s in confidence c.
Start by finding all the item
sets with support at least cs.
Also find the item sets
with support at least s.
Now that will be a subset of
the first set of item sets.
Lets focus on an item set in the first
collection that is one with support at
least cs.
Suppose it has k plus
one items as members.
There are k plus one subsets of size k
each formed by removing one of the items.
I've abused the notation abit by
singling out one of them as j.
The item to be removed,
leaving i 1 through i k.
But in fact we have to do this k plus
1 times, one for each of the items.
Having removed j, look at the support
of the remaining set i 1 through i k.
If it is at least s.
We might have an association rule
with the set that set on the left and
the first item j on the right.
Now suppose this set without j.
Has support as 1.
And with j the support goes down to s2.
[SOUND] And the confidence with the rule
is the ration S2 over S1, because
that is the fraction of the baskets
with I1 through IK that also contain J.
If that confidence is at least C, then
we have an acceptable association rule.
We're gong to look at finding frequent
item sets in a setting where the basket
data is kept in a flat file,
not any sort of database system.
As I tried to argue in the previous
slides, it is finding frequent item
sets that is the hard part of
finding association rules.
So even if our goal is to get association
rules and in many cases we really
want only the frequent item sets anyway,
not the association rules.
We're going to talk from this
point only about the problem of,
of identifying the frequent item sets.
We assume the data is so
big that it has to be stored on disk.
Since reading data from disk often
takes more time than what you
do with the data once
it is in main memory.
Our primary goal will be to minimize
the number of times each disk block has to
be read into main memory.
We're also going to assume the data is
stored basket-by-basket rather than by
item or in any stranger way.
And we're going to have to find for
each basket,
all it's subsets of a particular size.
We can do that in main memory
once the basket itself is there.
We can use K nested loops to
generate all subsets of size K.
Since we assume baskets are small and
often k will be only 1 or 2 anyway.
We're not going to worry about
the cost of doing this generation.
However you should be
alert to the possibility.
That if you're asked to generate
all subsets of size 100,000
from a basket with a million
items you just couldn't do it.
Okay.
So here's a picture of what we
imagine the file looks like.
Items have been coded as integers, so
the file is a sequence of integers.
We need to, a way to indicate
where one basket ends and
the next begins so
we might use an integer like -1.
Which we suppose can't represent
an item as the separator for baskets.
As we mentioned, we can focus on
the number of times that this block
has moved between disc and main memory.
Turns out that the algorithms we
will study each operate in passes.
During a pass, the entire file
is read block by block in order.
A surrogate for the, the cost of the
algorithm is thus the number of passes.
The number of disk I/O's is,
is that number, number of passes,
times the number of blocks that
the file of the basket, occupies.
Another non-obvious point is that,
for the algorithms we consider,
the limiting factor is usually how
much main memory is available.
So for example, it is common to have a
pass where the file of baskets is red, and
as we read the baskets, we count.
All the pairs of items
contained within that basket.
We need to have a place in main
memory to count each pair.
So that means at least
a few bytes per pair.
If we have 100,000 items then
there are 5 billion pairs.
At 4 bytes per count that's
20 gigs of main memory.
Okay we can do that.
Buy a little extra for our machine.
Or use several processors.
But if we have a million items.
That's a half a trillion pairs.
And we can't really manage all
the counts in main memory.
And if it isn't obvious using
disks to store the counts.
WIll not work, the counts have, we have
to increment are essentially random,
so if even half the counts need
to be on disk at any time,
we have a 50% chance of needing
two disk IOs with every increment.
I'm going to concentrate on how
you find frequent pairs of items.
Often finding frequent items,
that is sets of size one or,
or, s, or singletons, is not too hard
because there aren't so many items that we
can't count them all in main memory as
we make a pass through the baskets.
But it's also common for
the pairs to be too large to
count them all in main memory.
You might think that there are even more
triples of items than there are pairs.
You'd be right.
However, the algorithms we'll cover
exploit the fact that once you have
the frequent pairs, you can eliminate most
of the triples and not count them at all.
One might ask why there shouldn't be
lots and lots of frequent triples.
The reason is that if we're going
to bother to do a frequent item
sets analysis,.
We don't want so many answers that
we can't even think about them all.
As a result it is normal to set
the support threshold high enough that it
is hard for a large item set
to be sufficiently frequent.
As a result most of the sets
that we meet that will meet
the threshold will be singletons or
doubletons.
The bottom line is that we're going
to concentrate on algorithms for
finding pairs.
The extension to larger item
sets will be given once and
can be used with any of
the algorithms we discussed.
Let's start by talking about what
we might call the Naive Algorithm.
We want to read the baskets in some number
of passes so why not use just one pass and
count all the pairs in main memory?
We mention this briefly.
But just to make sure we understand what
happen, happens when we process a basket.
We use a double loop to generate all
the pairs of items in the basket.
And for
each pair we add one to it's count.
This algorithm actually works
provided there's enough space in main
memory to count all the pairs of items.
The number of bytes we need is roughly the
square of the number of items in our data.
That is, the number of pairs of items
is the number of items choose two or
approximately half the square
of the number items.
And if we can count
each pair in two bytes,
which is possible if the threshold
is no more than two to the sixteenth
then the number of bytes we need is
exactly the square of the number of items.
If we need four byte integers to
count then we need twice that square.
And just to recall, the typical
number of items if you're Wal-Mart.
The number of items is about 100,000,
so you might be okay.
But if you're dealing with items as
webpages, then you're definitely not okay.
Before we proceed, I need to talk
a little more detail about how you
organize main memory to
do the counting of pairs.
There are actually two approaches, and
which is better depends on whether it
is likely or unlikely that two given
items ever appear together in a basket.
One approach is to maintain
a triangular matrix.
I'll, I'll talk about this
on the next slide, but
the idea is to maintain
a two dimensional ray.
Where A of I and
J is only there if I is
strictly less than J.
The second approach is to keep
records with three components,
I, J, and C, meaning that the count for
the set of items I and J is currently C.
You organize this collection of
records by indexing on i and j.
So given a pair i,j, you're going
to quickly find its record and
increment its count, or just read
its count, if that's what you want.
The triangular matrix approach,
requires four bytes per pair of items.
I'm going to assume from here on that
integers require four bytes, even though,
if as we just mentioned,
it is okay to keep them small, and
fewer bytes could be okay.
It is even possible in some circumstances
there can be more than four bytes but
I'm not going to worry
about that case either.
On the other hand,
if we keep a table of triples and
we need 12 bytes per pair,
four each for i, j, and c.
But the advantage is that a pair only
needs a record that appears in at
least one basket.
As a result the space requirement for
the tabular approach is 12 bytes per
existing pair, but not per possible pair.
Here's a picture of the difference.
For the triangular matrix, you need four
bytes per unit area of the triangle.
For the tabular method,
you need 12 bytes times the fraction of
the area that represents
pairs actually present.
So if more than one-third of possible
pairs are present in at least one basket,
you prefer the triangular matrix.
If you expect fewer than a third of the
possible pairs to be present in the data,
then you should go for
the tabular approach.
Now let's look at how we construct
a triangular matrix given the,
given that this structure is not exactly
built into most programming languages.
First of all we'll assume the items
are represented by consecutive integers
starting at one.
If items in your data
are represented by their names, or
by integers that are not consecutive,
then you need to build a table to
translate from an items name
in the data to its integer.
A hash table whose key is
the original name of the item in
the data will do just fine.
Okay.
We're counting sets of two items, so
we can think of each set as
an ordered list of length two.
In other words, we'll count all i and
js such that i is less than j.
I want to use an order for
the pairs that look like this.
If there are n items in total.
Then first come the n minus one
pairs whose smaller member is one.
That's these.
These pairs are in order
of their larger member.
Then come the n minus two pairs
whose smaller member is two.
Again, these are ordered
by the larger member.
And the n minus 3 pairs with
3 as the smaller and so on.
What we really have is
a one dimensional ray and
we need a function that takes i and
j, where i is less than j.
And turns it into the into the position
in the array belonging to this pair.
Here's the magic formula.
I'll let you figure out why it works,
but for example,
if n equals 10,
let's look at the pair, (3,5).
I claim it is at postion two,
that's i minus 1, i is 3 of course,
times 10, that's n, minus i over 2,
that's three halves, plus 5, that's j.
Remember j is 5.
And then minus 3 which is i.
You work that out it's 19.
'Kay?
That makes sense because there are nine
pairs ahead of the, the pair 3,
5 that have a 1.
As the lowest the lowest
member of the pair.
Another eight pairs that
have Two as the lowest and
then there's one more pair three
four that comes ahead of three five.
The total number of pairs
that are represented
as N choose two or about N squared over
two and we used four bytes per pair.
So the number of bytes
needed is about 2n squared.
If we use a table of existing pairs,
then we need space 12p for
the triples, where p is the number
of pairs that occur in the data.
As we mentioned, this amount of space
is less than that of the triangular
matrix as long as p is at most
one third of the possible pairs,
or about p less than n squared over six
However, for this method, we also need
an index of the pairs of integers so
that we can quickly find the record for
that pair.
This structure also requires space
depending on how we implement it.
For example, we might implement
the hash table in which case we
need pointers to link.
A list for the, for each bucket.
So let's say here's the hash table,
here's a pointer to the first elements.
We'll have an i, a j, and a c.
And then a pointer to the next element.
And so on.
That would add another
four bytes per pair.
In particular not counted in the 12p is
all the space for the, the bucket headers.
That's probably not too much.
But then another integer at least for
each of the links.
That.
Is going to lead to a cost of about 16 p,
rather than the the 12 p.
and, and in addition again is the,
the cost for
the bucket headers which
is probably negligible.