research-article

Fast approximation of probabilistic frequent closed itemsets

Authors:

Erich A. Peterson,

Peiyi TangAuthors Info & Claims

ACMSE '12: Proceedings of the 50th annual ACM Southeast Conference

Pages 214 - 219

https://doi.org/10.1145/2184512.2184563

Published: 29 March 2012 Publication History

Get Access

Abstract

In recent years, the concept of and algorithm for mining probabilistic frequent itemsets (PFIs) in uncertain databases, based on possible worlds semantics and a dynamic programming approach for frequency calculations, has been proposed. The frequentness of a given itemset in this scheme can be characterized by the Poisson binomial distribution. Further and more recently, others have extended those concepts to mine for probabilistic frequent closed itemsets (PFCIs), in an attempt to reduce the number and redundancy of output. In addition, work has been done to accelerate the computation of PFIs through approximation, to mine approximate probabilistic frequent itemsets (A-PFIs), based on the fact that the Poisson distribution can closely approximate the Poisson binomial distribution---especially when the size of the database is large. In this paper, we introduce the concept of and an algorithm for mining approximate probabilistic frequent closed itemsets (A-PFCIs). A new mining algorithm for mining such concepts is introduced and called A-PFCIM. It is shown through an experimental evaluation that mining for A-PFCIs can be orders of magnitude faster than mining for traditional PFCIs.

References

[1]

T. Bernecker, H.-P. Kriegel, M. Renz, and F. Verhein. Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report). arXiv.org, cs.DB, Aug. 2010.

Google Scholar

[2]

T. Bernecker, H.-P. Kriegel, M. Renz, F. Verhein, and A. Zuefle. Probabilistic frequent itemset mining in uncertain databases. KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 119--127, June 2009.

Digital Library

Google Scholar

[3]

T. Calders, C. Garboni, and B. Goethals. Approximation of Frequentness Probability of Itemsets in Uncertain Data. In Data Mining (ICDM), 2010 IEEE 10th International Conference on, pages 749--754, 2010.

Digital Library

Google Scholar

[4]

C. Chui and B. Kao. A decremental approach for mining frequent itemsets from uncertain data. PAKDD'08: Proceedings of the 12th Pacific-Asia conference on Advances in knowledge discovery and data mining, pages 64--75, Jan. 2008.

Digital Library

Google Scholar

[5]

C. Chui, B. Kao, and E. Hung. Mining frequent itemsets from uncertain data. Advances in Knowledge Discovery and Data Mining, pages 47--58, 2007.

Digital Library

Google Scholar

[6]

K. Geurts, G. Wets, T. Brijs, and K. Vanhoof. Profiling High Frequency Accident Locations Using Association Rules. Proceedings of the 82nd Annual Transportation Research Board, Washington DC. (USA), January 12-16, pages 1--18, 2003.

Google Scholar

[7]

P. Tang and E. A. Peterson. Mining Probabilistic Frequent Closed Itemsets in Uncertain Databases. In ACM-SE 49: Proceedings of the 49th Annual ACM Southeast Regional Conference, pages 86--91. ACM, 2011.

Digital Library

Google Scholar

[8]

L. Wang, R. Cheng, S. D. Lee, and D. Cheung. Accelerating probabilistic frequent itemset mining: a model-based approach. In CIKM '10: Proceedings of the 19th ACM international conference on Information and knowledge management, pages 429--438. ACM Request Permissions, Oct. 2010.

Digital Library

Google Scholar

Cited By

View all

Chon KKim C(2024)GMiner++: Boosting GPU-based frequent itemset mining by reducing redundant computationsExpert Systems with Applications10.1016/j.eswa.2024.123928250(123928)Online publication date: Sep-2024
https://doi.org/10.1016/j.eswa.2024.123928
Malipatil SHanumantha Reddy T(2023)Discovery of interesting frequent item sets in an uncertain database using ant colony optimizationInternational Journal of Computers and Applications10.1080/1206212X.2023.226368945:11(673-679)Online publication date: 9-Oct-2023
https://doi.org/10.1080/1206212X.2023.2263689
Chen SNie LTao XLi ZZhao L(2020)Approximation of Probabilistic Maximal Frequent Itemset Mining Over Uncertain Sensed DataIEEE Access10.1109/ACCESS.2020.29974098(97529-97539)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2997409
Show More Cited By

Index Terms

Fast approximation of probabilistic frequent closed itemsets
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Probability and statistics
    1. Distribution functions

Recommendations

Mining probabilistic frequent closed itemsets in uncertain databases
ACMSE '11: Proceedings of the 49th annual ACM Southeast Conference

This paper defines probabilistic support and probabilistic frequent closed itemsets in uncertain databases for the first time. It also proposes a probabilistic frequent closed itemset mining (PFCIM) algorithm to mine probabilistic frequent closed ...
Probabilistic frequent itemset mining in uncertain databases
KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

Probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. The consideration of existential uncertainty of item(sets),...
A method for mining top-rank-k frequent closed itemsets
Collective intelligent information and database systems

Mining frequent closed itemsets (FCIs) is important in mining non-redundant (minimal) association rules. Therefore, many algorithms have been developed for mining FCIs with reduced mining time and memory usage. For mining FCIs, algorithms use the minimum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACMSE '12: Proceedings of the 50th annual ACM Southeast Conference

March 2012

424 pages

ISBN:9781450312035

DOI:10.1145/2184512

Conference Chair:
Randy K. Smith
University of Alabama
,
Program Chair:
Susan V. Vrbsky
University of Alabama

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: 29 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ACM SE '12

Sponsor:

ACM SE '12: ACM Southeast Regional Conference

March 29 - 31, 2012

Alabama, Tuscaloosa

Acceptance Rates

ACMSE '12 Paper Acceptance Rate 28 of 56 submissions, 50%;

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
102
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chon KKim C(2024)GMiner++: Boosting GPU-based frequent itemset mining by reducing redundant computationsExpert Systems with Applications10.1016/j.eswa.2024.123928250(123928)Online publication date: Sep-2024
https://doi.org/10.1016/j.eswa.2024.123928
Malipatil SHanumantha Reddy T(2023)Discovery of interesting frequent item sets in an uncertain database using ant colony optimizationInternational Journal of Computers and Applications10.1080/1206212X.2023.226368945:11(673-679)Online publication date: 9-Oct-2023
https://doi.org/10.1080/1206212X.2023.2263689
Chen SNie LTao XLi ZZhao L(2020)Approximation of Probabilistic Maximal Frequent Itemset Mining Over Uncertain Sensed DataIEEE Access10.1109/ACCESS.2020.29974098(97529-97539)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2997409
Nie LLi ZQi HLiu WQu W(2017)Probabilistic Frequent Itemsets Mining Based on Expectation Bound over Uncertain Database2017 14th International Symposium on Pervasive Systems, Algorithms and Networks & 2017 11th International Conference on Frontier of Computer Science and Technology & 2017 Third International Symposium of Creative Computing (ISPAN-FCST-ISCC)10.1109/ISPAN-FCST-ISCC.2017.92(14-19)Online publication date: Jun-2017
https://doi.org/10.1109/ISPAN-FCST-ISCC.2017.92
Li HZhang YZhang N(2017)Discovering Top-k Probabilistic Frequent Itemsets from Uncertain DatabasesProcedia Computer Science10.1016/j.procs.2017.11.482122(1124-1132)Online publication date: 2017
https://doi.org/10.1016/j.procs.2017.11.482
Li HZhang N(2016)Probabilistic Maximal Frequent Itemset Mining Over Uncertain DatabasesDatabase Systems for Advanced Applications10.1007/978-3-319-32025-0_10(149-163)Online publication date: 25-Mar-2016
https://doi.org/10.1007/978-3-319-32025-0_10
Raju VSaradhi Varma G(2014)An approach for mining weighted closed sequential patterns2014 First International Conference on Networks & Soft Computing (ICNSC2014)10.1109/CNSC.2014.6906722(158-161)Online publication date: Aug-2014
https://doi.org/10.1109/CNSC.2014.6906722
Liu CChen LZhang CGrossman RUthurusamy RDhillon IKoren Y(2013)Summarizing probabilistic frequent patternsProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2487575.2487618(527-535)Online publication date: 11-Aug-2013
https://dl.acm.org/doi/10.1145/2487575.2487618

View Options

Login options

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

Cited By

Index Terms

Recommendations

Mining probabilistic frequent closed itemsets in uncertain databases

Probabilistic frequent itemset mining in uncertain databases

A method for mining top-rank-k frequent closed itemsets