Non-derivable itemset mining

ABSTRACT

All frequent itemset mining algorithms rely heavily on the monotonicity principle for pruning. This principle allows for excluding candidate itemsets from the expensive counting phase. In this paper, we present sound and complete deduction rules to derive bounds on the support of an itemset. Based on these deduction rules, we construct a condensed representation of all frequent itemsets, by removing those itemsets for which the support can be derived, resulting in the so called Non-Derivable Itemsets (NDI) representation. We also present connections between our proposal and recent other proposals for condensed representations of frequent itemsets. Experiments on real-life datasets show the effectiveness of the NDI representation, making the search for frequent non-derivable itemsets a useful and tractable alternative to mining all frequent itemsets.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
	2	Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
	3	Yves Bastide , Rafik Taouil , Nicolas Pasquier , Gerd Stumme , Lotfi Lakhal, Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.66-75, Dec. 2000 [doi>10.1145/380995.381017]
	4	Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
	5	Bonferroni C (1936) Teoria statistica della classi e calcolo della probabilitá. Publicazioni del R. Instituto Superiore di Scienze Economiche e Commerciali di Firenze 8:1-62.
	6	Jean-François Boulicaut , Artur Bykowski , Christophe Rigotti, Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries, Data Mining and Knowledge Discovery, v.7 n.1, p.5-22, January 2003 [doi>10.1023/A:1021571501451]
	7	Jean-Francois Boulicaut , Artur Bykowski, Frequent Closures as a Concise Representation for Binary Data Mining, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.62-73, April 18-20, 2000
	8	Jean-Francois Boulicaut , Artur Bykowski , Christophe Rigotti, Approximation of Frequency Queris by Means of Free-Sets, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.75-85, September 13-16, 2000
	9	Artur Bykowski , Christophe Rigotti, A condensed representation to find frequent patterns, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.267-273, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375604]
	10	Artur Bykowski , Christophe Rigotti, DBC: a condensed representation of frequent patterns for efficient mining, Information Systems, v.28 n.8, p.949-977, December 2003 [doi>10.1016/S0306-4379(03)00002-4]
	11	Calders T (2003a) Axiomatization and deduction rules for the frequency of itemsets. Ph. D. thesis, University of Antwerp, Belgium.
	12	Calders T (2003b) Deducing bounds on the support of itemsets. In: Database technologies for data mining, vol 2682 of LNCS, pp 214-233, Springer.
	13	Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
	14	Calders T, Goethals B (2003) Minimal k-free representations of frequent sets. In: Lavrac N, Gamberger D, Blockeel H, Todorovski L (eds) Proc. PKDD Int. Conf. Principles of Data Mining and Knowledge Discovery, vol 2838 of Lecture Notes in Computer Science, pp 71-82. Springer-Verlag.
	15	Calders T, Goethals B (2005a) Depth-first non-derivable itemset mining. In: Proc. SIAM Int. Conf. on Data Mining.
	16	Calders T, Goethals B (2005b) Quick inclusion-exclusion. In: Proceedings ECML-PKDD 2005 Workshop Knowledge Discovery in Inductive Databases, vol 3933 of LNCS, pp 86-103. Springer.
	17	Dexters N, Calders T (2004) Theoretical bounds on the size of condensed representations. In: Proceedings ECML-PKDD 2004 Workshop Knowledge Discovery in Inductive Databases, pp 25-36.
	18	Dobra A (2002) Statistical tools for disclosure limitation in multi-way contingency tables. Ph. D. thesis, Department of Statistics, Carnegie Mellon University.
	19	Dobra A, Fienberg S (2000) Bounds for cell entries in contingency tables given marginal totals and decomposable graphs. Proc Nat Acad Sci 97(22):11885-11892.
	20	Dobra A, Fienberg SE (2001) Bounds for cell entries in contingency tables induced by fixed marginal totals. UNECE Stat J 18:363-371.
	21	Fienberg SE (1998) Fréchet and bonferroni bounds for multi-way tables of counts with applications to disclosure limitation. In: Statistical data protection (SDP-98), pp 115-129. Eurostat.
	22	Fréchet M (1951) Sur les tableaux de correlation dont les marges sont donnés. Ann Univ Lyon Sect A, Series 3 14:53-77.
	23	Galambos J, Simonelli I (1996) Bonferroni-type inequalities with applications. Springer.
	24	Goethals B, Muhonen J, Toivonen H (2005) Nonderivable association rules. In: Proc. SIAM Int. Conf. on Data Mining.
	25	Bart Goethals , Mohammed J. Zaki, Advances in frequent itemset mining implementations: report on FIMI'03, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007744]
	26	Groth D, Robertson E (2001) Discovering frequent itemsets in the presence of highly frequent items. In: In Proceedings Workshop on Rule Based DataMining, in Conjunction with the 14th International Conference On Applications of Prolog.
	27	Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
	28	Szymon Jaroszewicz , Dan A. Simovici, Support Approximations Using Bonferroni-Type Inequalities, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.212-224, August 19-23, 2002
	29	Jaroszewicz S, Simivici DA, Rosenberg I (2002) An inclusion-exclusion result for boolean polynomials and its applications in data mining. In: Proc. of the Discrete Mathematics in Data Mining Workshop, SIAM Datamining Conference.
	30	Jordan C, (1927) The foundations of the theory of probability. Mat Phys Lapok 34:109-136.
	31	Kahn J, Linial N, Samorodnitsky A (1996) Inclusion-exclusion: Exact and approximate. Combinatorica 16:465-477.
	32	Marzena Kryszkiewicz, Concise Representation of Frequent Patterns Based on Disjunction-Free Generators, Proceedings of the 2001 IEEE International Conference on Data Mining, p.305-312, November 29-December 02, 2001
	33	Marzena Kryszkiewicz , Marcin Gajek, Concise Representation of Frequent Patterns Based on Generalized Disjunction-Free Generators, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.159-171, May 06-08, 2002
	34	Marzena Kryszkiewicz , Marcin Gajek, Why to Apply Generalized Disjunction-Free Generators Representation of Frequent Patterns?, Proceedings of the 13th International Symposium on Foundations of Intelligent Systems, p.383-392, June 27-29, 2002
	35	Mannila H, Toivonen H (1996) Multiple uses of frequent sets and condensed representations. In: Proc. KDD Int. Conf. Knowledge Discovery in Databases.
	36	Melkman AA, Shimony SE (1997) A note on approximate inclusion-exclusion. Discrete Appl Math 73:23-26.
	37	Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
	38	Jian Pei , Guozhu Dong , Wei Zou , Jiawei Han, Mining Condensed Frequent-Pattern Bases, Knowledge and Information Systems, v.6 n.5, p.570-594, September 2004
	39	Pei J, Han J, Mao R (2000) Closet: an efficient algorithm for mining frequent closed itemsets. In: ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, TX.
	40	Mohammed J. Zaki, Scalable Algorithms for Association Mining, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.372-390, May 2000 [doi>10.1109/69.846291]
	41	Zaki M, Hsiao C (1999) ChARM: an efficient algorithm for closed association rule mining. In: Technical Report 99-10, Computer Science, Rensselaer Polytechnic Institute.
	42	Zaki M, Parthasarathy S, Ogihara M, Li W(1997) New algorithms for fast discovery of association rules. In: Heckerman D, Mannila H, Pregibon D (eds), Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, pp 283-286. AAAI Press.