Let's first introduce some basic concepts: frequent patterns and association rules.
We first look at this simple transaction example.
There are five transactions,
10 to 50 are the transaction IDs,
and these are the sets of items they bought.
For example, transaction ID 10 contains beer,
nuts and diaper, which form an itemset because it is a set of items.
And, for this particular line,
it is 3-itemset because it contains three items.
And for each itemset,
you may have a concept of support.
Support means, in this transaction dataset,
how many times beer happens.
In this particular case,
there are three occurrences of beers in this transaction data,
so this support count of beer is three.
But you also can use relative support;
that means the fraction of the transactions.
For example, there are a total of five transactions,
three of them contains beers,
so the relative support is 3/5 or you can say 60 percent.
So, we may see whether an itemset X is frequent or not if X,
the support of X,
pass a minimum support threshold.
For example, if we set the minimum support threshold is 50 percent,
then we can see the frequent 1-itemset in this datasets,
you will find they're four.
Like beer, you can see they're three cases,
this absolute support is three,
the relative support is 3/5, is 60 percent.
OK. But for frequent 2-itemsets,
you may check it.
There's only one.
OK. Because it's a beer and diaper,
they happen together 3/5,
that's why we get this.
But none of the other, you know,
itemsets they pass this 50 percent threshold,
so there's only one.
And from the frequent itemsets,
we can introduce an interesting rule,
association rule that implies,
for example, X implies Y simply says if people are buying X,
what is the support and confidence people will buy the itemset Y?
OK, then S is the support,
which is a probability X and Y contained together in this rule set.
OK. Then c is a confidence,
which is conditional probability.
That means if the transaction contains X,
what is the probability it also contains Y?
So, for this probabilistic computation,
you can use support X union Y divided by support X.
That means take the whole rule support,
divide by the left-hand side.
You may see this notion X union Y.
This is a set union.
But if you look at the Venn diagram,
actually transactions containing X could be this part; transaction containing diaper,
like beer, is this part of diaper, is this part;
containing both actually is their intersection,
OK, the intersection of the events.
OK. But from the itemset point of view,
X is the transactions containing both X and Y,
both beer and diaper.
You will say this one were count,
that's why we use not X intersects Y but X union Y. OK.
If you think X is beer, Y is diaper,
X intersects Y will be empty,
X union Y means it contains both.
Then, for association rule mining is actually try to
find all such rules which pass a minimum support and a confidence threshold.
We already know if we set minimum support is 0.5,
we're find these are the frequent 1-itemsets,
these are the frequent 2-itemsets.
From here, if we set minimum confidence is 50 percent,
we're going to derive two association rules.
Because these two rules,
if you use this computation,
beer and diaper getting together is three,
in here, then it's 60 percent because 3/5.
Then, if every time beer occurs,
you can see diaper also occur.
That's why the confidence is 100 percent.
But for diaper implies beer,
you can see the diaper support is four,
beer support is three,
so that means there's only 75 percent of
probability the customer buying a diaper likely will buy beer.
Are there more rules in this one?
Actually if you check this,
because this is only frequent 2-itemset,
these two are the only associated rules that can be generated from this transaction data.
Jiawei HanAbel Bliss Professor
