Each of the algorithms we covered in the previous discussion,
PCY, multi stage and multi hash,
can be extended to find frequent item sets of size greater than two.
The extension is just like we discussed for apiary.
We therefore need one more pass each time we increase the size of item sets by 1.
That can be really painful if there are some really large and frequent item sets.
An alternative is to compress all the work into one or two passes.
But we have to give up something.
We'll start with a simple algorithm that is approximate.
It may have both, both false positives and false negatives.
But if the data cooperates there will not be too many of either.
In the algorithm which we will abbreviate as SON, I’ll let you read the name of
the authors does a little better.
It needs only two passes but it works only if the number of candidates that it
creates can be counted in main memory.
Then we'll talk about Toivonen's Algorithm.
This algorithm works in two passes.
In fact it's on, on, it's only one full pass and, and a little more.
It has neither false positives nor false negatives.
But what happens is that there is some probability it will throw up
it's hands and not give any answer at all.
In that case, we can re run the algorithm and eventually get the right answer.
The expected number of passes is low, but there is no guarantee of ever finishing.
What we'll refer to as the simple algorithm is nothing more than
random sampling.
We choose some set of the baskets,
not more than we'll fill perhaps half the main memory.
Then we run one of the algorithms we just discussed on the sample.
But we do everything in main memory.
We can make any number of passes over the sample without using any
disk I/Os because the sample is in main memory.
And we'd use the available main memory to count the candidate pairs for
each size of item set.
The problem with this algorithm, is that we may not be able to
afford much main memory to hold the sample baskets or else we will not be able to st,
st, store all the counts that we need in, in main memory as well and
the smaller the sample the less accurate the results will be.
because there needs to be an adjustment to the threshold.
If we state the threshold as a percentage,
then we can simply use that percentage on the sample.
But, if the threshold is an absolute number s,
then we have to scale it back as in proportion to the size of the sample.
So, if the sample is 1% of the baskets.
And the proper threshold to use is s divided by 100.
It should be apparent that whenever we use a sample we'll get some item sets that
are frequent in the sample but not in the whole.
And we'll get some item sets that are frequent in the whole but
not in the sample.
The larger the sample the less likely that is.
And no matter what the sample size, the most likely errors will be for
item sets whose support is very close to s.
Thus the errors are less important than they would be a very frequent item
sets would be declared infrequent or very rare item set were declared frequent.
And this is sort of a, a waste of a slide.
But I think it helps you to visualize main memory.
One part is the space for the counts.
The list of frequent items and so on.
That's this.
It is used exactly as the entire main memory would be used
in whatever algorithm you're running.
Say a-priorri.
But, it is only a fraction of the total available memory.
The rest of the memory is used to hold the sample of the baskets.
By keeping the sample in main memory we can read them as many times as we want.
But the reads in main memory reads and
once the sample is loaded from disk we never again need to do a disk I/O.
Notice that when we sample, we don't even have to look at the entire data set.
So in a sense the simple algorithm is less than one pass.
However, we can eliminate false positives by making an additional full pass.
In that pass we count all the item sets that were found frequent in the sample.
And we describe those that are not frequent in the whole.
This pass will not catch false negatives, since we don't know to count them.
One way we can avoid most false negatives is to lower the threshold on
the initial pass.
For example, if the sample is 1%, use s over 125, rather than s over 100.
So that it is easier for items to be regarded as frequent in the sample.
But then on the full pass,
you use the correct threshold s when counting in from the entire set.
The disadvantage of lowering the, of lowering the,
the support threshold is that then you have to count more sets and
there may not be enough main memory to do so.
The SON algorithm is an improvement on the simple algorithm.
It uses two full passes and it doesn't have to sample.
Rather, we divide the entire set of baskets into small groups,
each group small enough to be a sample in the simple algorithm.
We read one group into main memory and
run the simple algorithm to get the item sets that are frequent in this sample.
The threshold is reduced only proportionately and, and not below that.
For each group we generate the list of item sets that are frequent in the sample.
And these item sets all become candidate item sets for the next pass.
Then on a second pass,
we count all the candidate sets, hoping that all the counts fit in main memory.
Okay. This trick works because of a variant of
the idea of monotonicity.
An item set that is not frequent in
any of the groups surely is not frequent in the whole.
So there are no false negatives.
A phrase then contrapositive form.
Any item set that is frequent in the home must be
declared a candidate by analysis of at least one of the groups.
The SON algorithm is especially good if you have multiple processors.
You can implement it in a two ma, in two map reduced jobs, for example.
The idea is that you break the file containing the baskets into many groups,
one at each processor.
That would naturally be the case if your data reside in a,
in a distributed file system, for example.
The groups are each the portion of the file existing at
one of the participating processors.
So each processor finds the local frequent item sets using the scaled down support.
It then broadcast to each other processor its list of local frequent item sets.
The union of all these lists is the candidate item sets.
Now each processor knows the list of candidate itemvsets and
counts them locally.
Then, each processor broadcasts its counts to all the other processor.
Now each processor knows the total count for
each candidate set and can discover which of them are truly frequent.
Next we'll discuss Toivonen's Algorithm which has an entirely different
approach to saving passes.
It does however start out just like the simple algorithm.
We take a sample and find the item sets that are frequent in the sample.
It is necessary, not optional, that we lower the threshold some what so
that there is little chance of a false negative.
For example, we might as we discussed earlier, use a 1% sample of the baskets.
But divide the threshold by 125, and consider any item set that met or
exceeded the reduced support threshold to be a candidate set.
It is important that the candidate item sets include all
those that are truly frequent in the full data set, and
it will really hope there will be no false negatives.
Because after computing the frequent item sets which become candidates for
counting on the full pass that follow.
We add the list of candidate, to the list of candidates that is.
Certain other item sets that were not deemed frequent in the sample.
These additional item sets called the negative border are the item sets that
are not frequent in the sample.
But each subset that is formed by dropping exactly one item from the set.
What we call the immediate subsets are frequent in the sample.
The purpose of counting the negative border is to act as canaries.
Okay, none of them should be frequent in the whole data set because we
picked the support threshold for
the sample that is significantly below a proportional threshold.
But if one or more, of the,
items sets in the negative order turned out to be frequent in the hold,
then we have to believe that the sample was not representative.
And we need to repeat the entire process.
That's why we say there's no limit on how many passes Toivonen's Algorithm might
take in rare cases.
Here are some examples of when sets are in the negative border.
A set of four items for
A,B,C,D is in the negative border if it satisfies two conditions.
First, it must not itself be frequent in the sample.
No set that is frequent in the sample can be in the negative border.
But all of the immediate subsets the sets that we get by deleting one of A B C or
D that's, that's these guys.
Are frequent in the sample.
[SOUND] For another example, the single set containing only
item A is in the negative border, if and only if it is not frequent.
This set has only one immediate subset, the empty set.
Now the empty set is a subset of every basket, so
the only way the empty set could not be frequent is if the support
threshold is higher than the number of baskets.
But that means nothing would be frequent and why are we bothering anyway.
Okay, now this is my pathetic attempt to draw a picture of the negative border,
which is actually pretty hard to visualize.
And the vertical dimension is the size of item sets, and the horizontal dimension
somehow represents all the item sets of a given size.
The frequent item sets are the green region.
This region is closed downwards because of monotonicity,
a subset of the frequent item set is always frequent.
Then the negative border is those sets above the green region,
that have only green below them.
The negative border may consist of sets of different sizes, and
its items tend to have widely varying frequencies.
Now the second pass of Toivonen's Algorithm, the first full pass really,
has us count all the candidate item sets including the negative border.
We hope no item set from the negative border turns out to
be frequent in the whole.
As long as there are no frequent item sets in the negative border, then whatever item
sets are found to be frequent in the whole, are the true frequent item sets.
There are no false negatives, and no false positives.
And the sucky part, is what happens if there is something in the negative border,
that is it's frequent in the whole.
In that case we must start over again with another sample.
We really don't want that to happen.
So we need to engage in a balancing act.
We want the support threshold for the sample to be as small as possible so
it is unlikely anything in the negative border is frequent in the whole.
But the smaller we make the threshold the more candidate items there will be and
the larger the negative border will be.
If we make the threshold too small we won't be able to fit the counts for
all these sits, sets, in, in main memory.
Here's a picture that suggests why it is such a disaster if something in
the negative border is frequent.
If it were just the item set found frequent itself, that is this guy,
we could just call it frequent and be done with it.
But what about all the super sets of this item set.
They could also be frequent in the whole and we didn't count them.
So, we don't know how far up the problem goes and
we have no way to find out, without starting over.
I want to close the discussion of Toliman's algorithm by proving that what I
said about the negative border makes sense.
That is, we want to know that if there's any item set at
all that is frequent in the whole.
But not frequent in the sample, then there is some member of
the negative border that is frequent in the whole but not frequent in the sample.
Okay. That means if we find no members of
the negative border to be frequent in the whole, then we know that there are no
sets at all that are frequent in the whole but that we did not count.
So here's the proof.
We'll do a proof by contradiction.
Suppose what I claimed is false.
That is there is an itemset S that is frequent in the whole but
not in the sample and in addition,
nothing in the negative border was found to be frequent in the whole.
Okay. Let T be one of the smallest subsets of
S that is not frequent in the sample.
In principle, T could be S itself, if it,
if, if it has no proper subsets that are not frequent in the sample.
All we care about is that all the subsets of T are frequent in the sample.
I claim T is frequent in the whole.
The proof is that S is frequent in the whole and
therefore by monotonicity each of S's subsets are frequent in the whole.
And T is one of those subsets.
But I also claim that T is in the negative border.
If it is not frequent in the sample, but
it had a proper subset that was not frequent in the sample,
then T would not be the smallest subset of S with that property.
That's a contradiction, because we started out assuming that nothing in
the negative border was frequent in the whole, and now we
see that T is both frequent in the whole and is a member of the negative border.
We conclude that if nothing in the negative border is frequent,
then nothing at all that is not counted can be frequent.
So the answer Toivonen's Algorithm gives is the truth