We're now going to learn
the basic A-Priori Algorithm.
Later we'll see some improvements
to this basic idea, but
the fundamental inside is monotonicity.
The idea that an itemset
cannot be frequent unless all
its subsets are frequent.
The A-Priori Algorithm uses one pass for
finding the frequent items,
then another pass through the data for
finding frequent pairs.
And if we want frequent triples we
need another pass and, and so on.
Each pass after the first can be thought
of as having identified a small number of
sets with a relevent size that might be
frequent, and therefore require a count.
But the power of our priority
comes from the fact that for
many data sets we can eliminate
almost all sets from candidacy and
thus greatly reduce the number of counts
we need to maintain in main memory.
When you think of the a-priori
algorithm as a two pass algorithm,
since that what it needs
to find frequent pairs, but
as we just said if you want to go
pass pairs to larger item sets,
then you need k passes, define
frequent items that's of size up to K.
A monotonicity property which
A-Priori exploits, says that
if a set of items appears in at least S
baskets, then so does each of its subsets.
That should be obvious,
since there are S baskets that
contain all members of the set.
And so, surely these s baskets
also contain any of it's subsets.
And there may be more baskets that
contain the subset but not the full set.
Now, we actually use this definition
in it's contrapositive form.
For example, when we're looking for
frequent pairs,
the key observation is that is an item
i does not appear s times by itself,
then no set containing
I could be frequent.
Because if, say the set of I and
J appears in S baskets,
then surely I appears in all
those baskets and maybe others.
This is all rea, really obvious,
but it's also essential and
I want to make sure everyone is onboard.
On the first pass, we count
the number of times each item occurs.
We want to do this in main memory un,
and unless the number of
items is beyond billions.
We can set up an integer count for
each item in main memory.
After the first pass, we see which
items appear at least s times.
These are the frequent items.
Incidentally, if all we want is to tell
whether or not an item appears s or
more times, then it is sufficient to count
up to s and not add ones beyond that.
So, if say s is 10,000, then we only
need to keep 2 bytes per count,
regardless of how many times
items might appear in the data.
Now, let's look at pass two, where we
read all the baskets from disk again.
And as in the naive algorithm, we're going
to try to count pairs in main memory.
But now we use monotonicity, so we only
have to count those pairs of items both of
which are among the frequent items.
So, for example,
if only half the items are frequent, we
need to count only a quarter of all pairs.
Okay.
The main memory we need depends on
the square of the number
of frequent items only, but
there's a small amount of
additional main memory we need for
a table that lets us know which of
the items are, in fact, frequent.
As we read a basket from disk,
we look at all its items and
ignore any that are not in
the table of frequent items.
From what remains, we generate all pairs
and increment each of their counts.
So, here's a picture,
the first of the series we're going to
use to compare different algorithms.
The rectangles each represent main
memory and how it is used on each pass.
On the left, we see the first
pass of the A-Priori algorithm.
We need space in main memory,
only for the counts of the items and
we show it as occupying only
a small fraction of main memory,
because typically we will need much
more main memory for the second pass.
In the second pass we distilled the item
count from the first pass down to
a list of frequent items.
This list is probably implemented as
a hash table or similar structure.
So, given an item, we can quickly
tell whether it is frequent.
The rest of main memory is available for
counting all the pairs of frequent items.
For a-priori to work in
a reasonable amount of time,
these counts must all be
able to fit in main memory.
If there's still too many counts
to maintain in main memory,
we need to try something else,
a different algorithm,
splitting the task among different
processors, or even buying more memory.
You might suppose that when you're
counting only pairs of frequent items you
have to use the tabular
method to store counts,
since we hope that only a small fraction
of the possible pairs need to be counted.
Since the numbers associated with
the frequent items are not likely to
be consecutive.
It looks like we can't use
the triangular matrix with counts for
only the pairs of frequent items.
Or if we did, we'd use just as much space
as if we were counting all pairs, and
we might not have that much space.
fortunately, there's a,
a simple trick we can use.
We re-number the frequent items,
starting at one.
And on the second pass, we store
a table that translates the original
integers used for all items into the new
numbers for the frequent items only.
This table also tells you
whether an item is frequent or
not, since it will not appear in
the table if it is not frequent.
[SOUND] So,
here's the picture of A-Priori again.
We show the table on the second pass
as taking more space than before,
since it stores two
numbers per frequent item.
And needs to store each item,
even those that are not frequent.
So, we can index into the table given
an old number, and find either its number
among the frequent items, like 1,
which has new frequent, number 1.
3 has new number 2.
or, as in this case,
we can find it's not frequent.
There are better ways to organize
the table that save space,
if the fraction of items
that are frequent is small.
For example, we could use a hash table in
which we stored only the frequent items
with the key being the old number and
the associated value being the new number.
What we're, we're not showing as a table
that all algorithms may need, one
that translates from the representation of
items in the raw data, to the old numbers,
that is the consecutive integers
that we used for all the items.
The idea used on the second pass
extends to later passes that
construct larger sets.
Let's use the term k-set for
an item set with k members.
Then there are two collections of
k-sets associated with our effort to
find all the frequent k-sets.
C sub k is the candidate case sets.
These are the sets that based on what
information we have from previous passes,
might be frequent.
At least we can't rule out the possibility
they're being frequent by using
monotonicity, so we have to count them.
And then, the result of the kth
pass we'll call L sub k.
This is the subset of C sub k consisting
of those k sets that are found on
the kth facts to be really frequent.
And here's a picture of the full A-Priori
algorithm including not only pairs, but
a suggestion of the process for
larger item sets.
In fact, this is the picture for
a whole family of related algorith,
algorithms where each algorithm is
characterized by a different way to
construct the set of candidate pair C2.
Each pass consists of a filter step,
where we look at the candidate sets for
the pass and
select only the frequent sets.
That is CK is turned into LK.
Each pass also has a construction
step where the candidates for
the next pass are constructed from
the frequent sets for the current pass.
That is on the K pass,
CK is constructed from L sub K minus one.
We start with C1,
the set of candidate singleton item sets.
These are all items,
since we have no way of eliminating
any items without looking at the data.
The filter step for
the first pass counts the items and
finds those that are frequent.
So, the set L1 is just the frequent items.
From L1, we construct C2, the set of
candidate pairs for the second pass.
In this case we don't
actually do anything.
The set C2 is defined implicitly from the
lists of, the list of items in the set L1.
Okay.
The filter step for the second
pass counts all the pairs in C2,
and the result is the truly
frequent pairs of items.
We can proceed like this
from the frequent pairs.
We construct C3,
the candidate triples by a technique
we’ll describe on the next slide.
Then we filter C3 to get L3,
from that we construct C4, and so on.
We can describe the apriori algorithm for
item sets of all sizes an as,
as an induction on k.
And the size of the item
sets we construct.
There, there is one pass for each k.
The basis is that C1 is
the set of all items.
Strictly speaking C1 consists
of all the singleton sets,
each of those sets
containing one of the items.
Given the set CK, we can construct L K
by making a path through the data and
counting each set in CK.
Those sets whose counts get up to
the threshold S, become members of LK.
The other part of the induction is
how we construct CK plus one from LK.
We look for sets of size K plus one,
each of whose subsets are size K,
those you get by dropping one element,
or in LK.
You have to be a little careful
how you organize the search.
For example, you wouldn't want to
enumerate all sets of size four.
And for each one, tested if each of
its four subsets of size 3 are in L 3.
A better idea is to start with some set,
set in LK.
For example, assume k equals 3.
We might find the set let's say 1,
3, 5 is in L k.
Now, look at each item who's number is
higher than any in the set, say, six.
Okay.
This set might be in C 4.
We already know its subset.
That is a subset of well, so it's about,
talking about really 1, 3, 5, 6.
Now, we already know that its
subset 1,3,5 is is in L3.
So, we have to test three other sets.
We have to test well, 3, 5, 6 and 1,
5, 6, and I guess 1, 3, 6.
And if all three of these are in L3,
then we would put this guy,
1, 3, 5, 6 in C4.
Then we're not done with
starting again with 1, 3, 5.
We might the, then throw in the element
seven an so on and eight and, and nine
all the time searching for
sets of size four,
each of whose subsets of size three are,
are known to be frequent.
The space needed on the,
on the kth pass is proportional
to the number of sets in CK.
In principle there could
be as many as n choose k.
Candidate sets of size k.
If there are k, if there are, are n items.
So the space requirement could grow
painfully each time k increased, but
in cases where this method
is used in practice,
the support threshold is high enough
that as k increases beyond two,
the number of candidate sets that could
be formed from the frequent sets on
the previous pass,
actually decreases, doesn't increase.
Thus the memory requirements,
peak at k equals 2,
and that's why we concentrate
on finding frequent pairs.
And why the more advanced algorithms
we'll see in the next unit,
different from A-Priory, and
how they handle the pairs.