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.