Deducing Bounds on the Frequency of Itemsets
Toon Calders · 2002
Abstract. Mining Frequent Itemsets is the core operation of many data mining algorithms. This operation however, is very data intensive and sometimes produces a prohibitively large output. In this paper we give a complete set of rules for deducing tight bounds on the frequency of an itemset if the frequencies of all its subsets are known. These rules allow for reducing data access and providing a more compact output. Based on the derived bounds [l, u] of a candidate itemset C, we can decide not to access the database to count its frequency if l is larger than the support threshold (C will certainly be frequent), or if u is smaller than the threshold (C will certainly fail the frequency test). In this way, the number of runs through the database and the number of sets to count can be reduced significantly. We can also use the rules to reduce the size of an adequate representation of the collection of frequent sets; all itemset frequencies that can be deduced do not need to be stored explicitly. To assess the usability in practice, we implemented the deduction rules and we present experiments on a real-life dataset. 1