Also, any data set that anybody would actually care about would have more than one transaction, probably thousands, if not millions or billions. This explosion of complexity that comes from all of the possible patterns that can be found in data is the motivation for ways of compressing the possible patterns/combinations. That is what closed itemsets are all about.
In our example above, an example of this "super-pattern" notion would be like saying that ABC is a super-pattern of AB. The notation Y ⊃ X is a fancy mathematical way of saying the same thing. The way I think about a closed pattern is that it's the biggest, most complex, pattern I can find at various levels of support. It isn't exactly like that, but it will become clearer with an example.
Let's suppose we have a simple set of transactions like this
CLOSED ITEMSETS
Now I'm going to have to get a little technical here, but I'm going to translate for you too so don't worry. The definition of a closed pattern goes like this, "A pattern (itemset) X is closed if X is frequent, and there exists no super-pattern Y ⊃ X, with the same support as X" (J. Han, Pattern Discovery in Data Mining, Coursera Lecture Material)
Let's break this definition down. "itemset" is just a group of items. It could be one item (A), 2 items (AB), 3-items (ABC)... k-items. People sometimes refer to itemset size by telling you what k equals. k is just a variable that represents the size/complexity of the pattern you're looking at. By, "frequent", the definition is saying that this itemset, X, you're looking at meets the minimum support requirements, so it might be interesting. The whole bit in the definition about "super-pattern Y ⊃ X" Basically means that all of X is contained in Y. In Venn diagram world, if Y is a super-pattern of X then it looks like this
supper-pattern Venn diagram
Let's suppose we have a simple set of transactions like this
Simple transaction table
If you are looking for patterns that have support greater than or equal to 1, there would be a lot of combinations possible for just 2 transactions. Based on the work we already did above, there are 15 combinations for the first transaction. Transaction 20 also has the 15 combinations, but there is some overlap in possible combinations in transaction 10 and 20. To visualize this, lets list them out in a table.
Combination Table
If you look closely at the combination table above, you can find some repeats if you compare transaction 10 and 20. To make this easier to see, I've rearranged the entries a little bit here.
Expanded Combination Table
The green highlighted combinations are found in both transactions. Based on this, there is support of 1 for every combination in the expanded combination table, except for C, D, and CD which have support of 2. This is where closed itemsets come in handy. If you remember the Apriori Principle, if a more complex combination meets the minimum support requirements, then the subset, or simpler patterns, will also meet those requirements. In this example, if I make the statement that I know that CD has support of 2, then I automatically know that C, and D also have support of at least 2. In this case C and D have a support of exactly 2 so CD is one of my closed patterns in this data. Let's revisit the definition of a closed pattern to make sure that's true. There are 2 requirement for a pattern to be a closed pattern
- It's frequent; yep CD meets that criteria
- No super-pattern with the same support as CD; There are bigger patterns in the data, but none of them have support of 2 so we're good here too
What's so awesome about this is that I can say I have closed pattern CD with support of 2, and I automatically know that C and D also have support of 2 because of the apriori principle. We can use this one close pattern to compress three patterns without losing any information!
Now let's look for some other closed patterns in the data, so you can get the hang of it. The way I explained closed data sets before was that they are normally the most complicated patterns that are frequent. In our table above we've got ABCD and CDEF to work with that seem to fit that criteria. So which one is a closed pattern? Both actually. Let's look at the 2 rules for ABCD
- It's frequent; in our example we only need frequency of 1, so we're good here
- No super-pattern with the same support as ABCD; CDEF has the same support as ABCD, but CDEF is not a supper pattern of ABCD.
Closed pattern Venn diagram
If you use the Apriori principle, and these 3 closed patterns, you can reconstruct the entire data table we started with without losing any information. Pretty awesome right?
MAX-PATTERN ITEMSETS
There is another way to compress pattern data called max-patterns. They are almost exactly the same as closed patterns, except that we don't care about whether other patterns have the same support. A max-pattern still has to satisfy the minimum support threshold though. The easiest way to explain this is by using the example above for closed patterns. In that example we have closed patterns ABCD, CD, and CDEF. CD is a distinct closed pattern because it has a support of 2 and the others only have support of 1. This is despite that fact that it is actually a subset, or part of, ABCD and CDEF. If you're looking for max-patterns you don't care about this distinction so you only get ABCD and CDEF as max-patterns; that's because CD is part of the larger patterns ABCD and/or CDEF. A max-pattern will give you more pattern compression, but you can see that even in this very simple example, you're losing some of the information that was originally contained in the raw data because now we don't know how much support CD, C, or D had.
Thanks Jed for the clear explanation. Just a question, Why do you say that the I
ReplyDelete"....automatically know that C and D also have support of 2 because of the apriori principle...".
It seems that this is true because {C,D} has a support with maximum value amongst all the possible supports.
Look at this example:
1) The full item set is: I={A,B,C,D}
2) The transactions database is: {C}, {D}, {C,D}
3) the threshold is 1.
Clearly
=======
a) {C},{D}, {C,D} are the only frequent itemsets of I,
b) {C},{D}, {C,D} are all closed, support({C}) = 2, support({D}) = 2 and support({C,D}) = 1
c) any other itemset has support 0 and then not frequent.
But {C} or {D} are subset of {C,D} but they do not have the same support.
I understand your argument if E has maximal support amongst all supports values
because by Apriori, any subset must have a support greater or equal but cannot be greater...
What do I miss?
Regards
Franco
The comment I made earlier in the post was that "I automatically know that C and D also have a support of at least 2". The fact that C and D have support of exactly 2 is based on the example I chose. You showed another example where this is not true. You're right, I could have been clearer in my explanation in the section you quoted. Thanks for the feedback!
DeleteAwesome explanation
ReplyDeleteThank you for your explanation. I have just a question: What about the empty set, is it closed or not?
ReplyDeleteIf you have any non-empty closed sets, then I would say that the empty set is not a closed set because it is technically contained within all of the non-empty closed sets. If there are no other closed sets, then the only closed set is the empty set.
Delete