Mining All Non-derivable Frequent Itemsets

By Toon Calders, Bart Goethals. European Conference on Principles of Data Mining and Knowledge Discovery, 2002

368 citations recorded by the source corpus.

Recent studies on frequent itemset mining algorithms resulted in significant performance improvements. However, if the minimal support threshold is set too low, or the data is highly correlated, the number of frequent itemsets itself can be prohibitively large. To overcome this problem, recently several proposals have been made to construct a concise representation of the frequent itemsets, instead of mining all frequent itemsets. The main goal of this paper is to identify redundancies in the set of all frequent itemsets and to exploit these redundancies in order to reduce the result of a mining operation. We present deduction rules to derive tight bounds on the support of candidate itemsets. We show how the deduction rules allow for constructing a minimal representation for all frequent itemsets. We also present connections between our proposal and recent proposals for concise representations and we give the results of experiments on real-life datasets that show the effectiveness of the deduction rules. In fact, the experiments even show that in many cases, first mining the concise representation, and then creating the frequent itemsets from this representation outperforms existing frequent set mining algorithms.

Subfields: Computational Theory and Mathematics, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/ce53c548fe59cf733dfeea7dd56dd9bd155e8b5b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Information Systems

In Signal Processing

Citations in the corpus

Frequent pattern mining: current status and future directions (2007, background): “Mining all non-derivable frequent sets proposed by Calders and Goethals (2002) belongs to this category as well since the set of result patterns and their support information generated from these methods can be used to derive the whole set of frequent patterns.”
Survey on Frequent Pattern Mining (2003, background): “Recently, Calders and Goethals presented a generalization of all these techniques resulting in a system of deduction rules that derive tight bounds on the support of candidate itemsets [15].”
Constraint-based Data Mining (2005, background): “, 2003), the disjunction-free sets (Bykowski and Rigotti, 2003), the non-derivable itemsets (Calders and Goethals, 2002), the frequent pattern bases (Pei et al.”
The Chosen Few: On Identifying Valuable Patterns (2007, background): “Subsets that allow for the reconstruction of both syntactic makeup and support information while at the same time decreasing the size of the set of patterns to be considered include the sets of closed, free, and non-derivable patterns [12, 2, 4].”
Weighted Association Rule Mining using weighted support and significance framework (2003, methodology): “Given a threshold of minimum support and confidence, methods of discovering association rules [4, 5, 6, 9] have become active research topics since the publication of Agrawal, Imielinski and Swami and Agrawal and Srikant papers [2, 3].”
One in a million: picking the right patterns (2009, background): “Subsets that allow for the reconstruction of both syntactic makeup and support information while at the same time decreasing the size of the set of patterns to be considered include the sets of closed, free, and non-derivable patterns [1,3,5,15].”
Frequent item set mining (2012, background): “Alternative lossless compressions of the set of frequent item sets, which can reduce the output even more, are, for example, nonderivable item sets 31 and closed nonderivable item sets .”
Krimp: mining itemsets that compress (2011, background): “Krimp : mining itemsets that compress To address this problem, closed (Pasquier et al. 1999) and non-derivable (Calders and Goethals 2002) itemsets have been proposed, which both provide concise lossless representations of the original collection of frequent itemsets.”
Association mining (2006, background): “Tree dEclat Candidate gener Agrawal et al. Pijls Agrawal et al. Zaki Zaki Zaki Goulbourne et al. Zaki & Gouda ation algorithms: Hybrid 1999 1999 2000 2000 2000 2000 2000 2001 HL VV VV VV VV HV HL VV Trie Trie Trie Lattice Lattice Lattice Trie Lattice 1 V1 - 1 1 2 2 2 1 2 Projection, matrix ac”