Compact Representations of Frequent Itemset

Introduction

The number of frequent itemsets can be very large for instance let us say that you are dealing with a store that is trying to find the relationship between over 100 items. According to the Apriori Principle, if an itemset is frequent, all of its subsets must be frequent so for frequent 100-itemset has
100 frequent 1-itemset and
1002 frequent 2-itemset and
1003 frequent 3-itemset and
the list goes on, if one was to calculate all the frequent itemsets that are subsets of this larger 100-itemset they will be close to 2100. Now I don’t know about you but this number isn’t the sort of data you want to store on the average computer or try and find the support of and so it is for this reason  that alternative representations have been derived which reduce the initial set but can be used to generate all other frequent itemsets.  The Maximal and Closed Frequent Itemsets are two such representations that are subsets of the larger frequent itemset that will be discussed in this section. The table below provides the basic information about these two representations and how they can be identified.

Maximal and Closed Frequent Itemsets

Relationship between Frequent Itemset Representations

In conclusion to this section it is important to point out the relationship between frequent itemsets, closed frequent itemsets and maximal frequent itemsets. As mentioned earlier closed and maximal frequent itemsets are subsets of frequent itemsets but maximal frequent itemsets are a more compact representation because it is a subset of closed frequent itemsets. The diagram to the right shows the relationship between these three types of itemsets. Closed frequent itemsets are more widely used than maximal frequent itemset because when efficiency is more important that space, they provide us with the support of the subsets so no additional pass is needed to find this information.