Article

A probability analysis for candidate-based frequent itemset algorithms

Authors:

Nele Dexters,

Paul W. Purdom,

Dirk Van GuchtAuthors Info & Claims

SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

Pages 541 - 545

https://doi.org/10.1145/1141277.1141404

Published: 23 April 2006 Publication History

Get Access

Abstract

This paper explores the generation of candidates, which is an important step in frequent itemset mining algorithms, from a theoretical point of view. Important notions in our probabilistic analysis are success (a candidate that is frequent), and failure (a candidate that is infrequent). For a selection of candidate-based frequent itemset mining algorithms, the probabilities of these events are studied for the shopping model where all the shoppers are independent and each combination of items has its own probability, so any correlation between items is possible. The Apriori Algorithm is considered in detail; for AIS, Eclat, FP-growth and the Fast Completion Apriori Algorithm, the main principles are sketched. The results of the analysis are used to compare the behaviour of the algorithms for a variety of data distributions.

References

[1]

R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proc. ACM SIGMOD Int. Conf. Management of Data, pages 207--216, 1993.

Digital Library

Google Scholar

[2]

R. Agrawal and R. Srikant. Fast algorithms for mining association rules. Proc. of VLDB Conference, pages 487--499, 1994.

Digital Library

Google Scholar

[3]

R. Agrawal and R. Srikant. Mining sequential patterns. Proc. IEEE ICDE Int. Conf. on Data Engineering, pages 3--14, 1995.

Digital Library

Google Scholar

[4]

R. J. Bayardo. Efficiently mining long patterns from databases. Proc. ACM SIDMOD Int. Conf. on Management of Data, pages 85--93, 1998.

Digital Library

Google Scholar

[5]

R. J. Bayardo, B. Goethals, and M. J. (co-chairs) Zaki. Workshop on frequent itemset mining implementations (fimi '04). Brighton, UK, 2004.

Google Scholar

[6]

T. Calders. Computational complexity of itemset frequency satisfiability. Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pages 143--154, 2004.

Digital Library

Google Scholar

[7]

H. Chernoff. A measure of asymptotic efficiency for test of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493--507, 1942.

Crossref

Google Scholar

[8]

F. Geerts, B. Goethals, and J. Van den Bussche. A tight upper bound on the number of candidate patterns. Proc. of the first IEEE Int. Conf. on Data Mining, 2001.

Digital Library

Google Scholar

[9]

B. Goethals. Efficient frequent pattern mining. PhD thesis, transnational University of Limburg, Diepenbeek, Belgium, December 2002.

Google Scholar

[10]

J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. Proc. ACM SIGMOD Int. Conf. Management of Data, pages 1--12, 2000.

Digital Library

Google Scholar

[11]

W. A. Kosters and W. Pijls. Apriori, a depth first implementation. Proc. of the Workshop on Frequent Itemset Mining Implementations, 2003.

Google Scholar

[12]

P. W. Purdom, D. Van Gucht, and D. P. Groth. Average case performance of the apriori algorithm. SIAM J. Computing, 33 (5): 1223--1260, 2004.

Crossref

Google Scholar

[13]

M. J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12 (3):372--390, 2000.

Digital Library

Google Scholar

[14]

Z. Zheng, R. Kohavi, and L. Mason. Real world performance of association rule algorithms. Proc. of the 7th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 401--406, 2001.

Digital Library

Google Scholar

Cited By

View all

Leung CHao BBrajczuk DShin SOssowski SSchumacher MPalakal MHung C(2010)Mining uncertain data for frequent itemsets that satisfy aggregate constraintsProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774305(1034-1038)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774305
Chester SSandler IThomo A(2009)Scalable APRIORI-Based Frequent Pattern DiscoveryProceedings of the 2009 International Conference on Computational Science and Engineering - Volume 0110.1109/CSE.2009.51(48-55)Online publication date: 29-Aug-2009
https://dl.acm.org/doi/10.1109/CSE.2009.51
Calders T(2007)The complexity of satisfying constraints on databases of transactionsActa Informatica10.1007/s00236-007-0060-144:7(591-624)Online publication date: 9-Nov-2007
https://dl.acm.org/doi/10.1007/s00236-007-0060-1
Show More Cited By

Index Terms

A probability analysis for candidate-based frequent itemset algorithms

Recommendations

Fast Algorithms for Frequent Itemset Mining Using FP-Trees

Efficient algorithms for mining frequent itemsets are crucial for mining association rules as well as for many other data mining tasks. Methods for mining frequent itemsets have been implemented using a prefix-tree structure, known as an FP-tree, for ...
An Analytical Study on Frequent Itemset Mining Algorithms
MIKE 2013: Proceedings of the First International Conference on Mining Intelligence and Knowledge Exploration - Volume 8284

Data mining is the process of collecting, extracting and analyzing large data set from different perspectives. Fundamental and important task of data mining is the mining of frequent itemsets. Frequent itemsets play an important role in association rule ...
Based on Frequent Itemset for Maximal Frequent Itesets
ICECE '10: Proceedings of the 2010 International Conference on Electrical and Control Engineering

This paper proposes a maximal frequent itemsets mining algorithm BFI-MFI(Based on Frequent Itemset for maximal frequent itemsets). A maximal frequent itemset in frequent itemsets can be confirmed through detecting whether exiting their superset. This ...

Comments

Information & Contributors

Information

Published In

SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

April 2006

1967 pages

ISBN:1595931082

DOI:10.1145/1141277

Conference Chair:
Hisham M. Haddad
Kennesaw State University, Kennesaw, Georgia

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SAC06

Sponsor:

SIGAPP

SAC06: The 2006 ACM Symposium on Applied Computing

April 23 - 27, 2006

Dijon, France

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Leung CHao BBrajczuk DShin SOssowski SSchumacher MPalakal MHung C(2010)Mining uncertain data for frequent itemsets that satisfy aggregate constraintsProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774305(1034-1038)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774305
Chester SSandler IThomo A(2009)Scalable APRIORI-Based Frequent Pattern DiscoveryProceedings of the 2009 International Conference on Computational Science and Engineering - Volume 0110.1109/CSE.2009.51(48-55)Online publication date: 29-Aug-2009
https://dl.acm.org/doi/10.1109/CSE.2009.51
Calders T(2007)The complexity of satisfying constraints on databases of transactionsActa Informatica10.1007/s00236-007-0060-144:7(591-624)Online publication date: 9-Nov-2007
https://dl.acm.org/doi/10.1007/s00236-007-0060-1
Dexters NPurdom PVan Gucht D(2006)Peak-Jumping Frequent Itemset Mining AlgorithmsKnowledge Discovery in Databases: PKDD 200610.1007/11871637_47(487-494)Online publication date: 2006
https://doi.org/10.1007/11871637_47

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Fast Algorithms for Frequent Itemset Mining Using FP-Trees

An Analytical Study on Frequent Itemset Mining Algorithms

Based on Frequent Itemset for Maximal Frequent Itesets

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations