research-article

An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets

Authors:

Michael Mitzenmacher,

Andrea Pietracaprina,

Fabio VandinAuthors Info & Claims

Journal of the ACM (JACM), Volume 59, Issue 3

Article No.: 12, Pages 1 - 22

https://doi.org/10.1145/2220357.2220359

Published: 01 June 2012 Publication History

Abstract

As advances in technology allow for the collection, storage, and analysis of vast amounts of data, the task of screening and assessing the significance of discovered patterns is becoming a major challenge in data mining applications. In this work, we address significance in the context of frequent itemset mining. Specifically, we develop a novel methodology to identify a meaningful support threshold s^* for a dataset, such that the number of itemsets with support at least s^* represents a substantial deviation from what would be expected in a random dataset with the same number of transactions and the same individual item frequencies. These itemsets can then be flagged as statistically significant with a small false discovery rate. We present extensive experimental results to substantiate the effectiveness of our methodology.

References

[1]

Aggarwal, C. and Yu, P. 1998. A new framework for itemset generation. In Proceedings of the 17th ACM Symposium on Principles of Database Systems. 18--24.

Digital Library

[2]

Agrawal, R., Imielinski, T., and Swami, A. 1993. Mining association rules between sets of items in large databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 207--216.

Digital Library

[3]

Arratia, R., Goldstein, L., and Gordon, L. 1990. Poisson approximation and the Chen-Stein method. Stat. Sci. 5, 4, 403--434.

[4]

Benjamini, Y. and Hochberg, Y. 1995. Controlling the false discovery rate. J. Roy. Stat. Soc., Ser. B 57, 289--300.

[5]

Benjamini, Y. and Yekutieli, D. 2001. The control of the false discovery rate in multiple testing under dependency. Ann. Stat. 29, 4, 1165--1188.

[6]

Bolton, R., Hand, D., and Adams, N. 2002. Determining hit rate in pattern search. In Proceedings of Pattern Detection and Discovery. Lecture Notes in Artificial Intelligence, vol. 2447, 36--48.

Digital Library

[7]

Dudoit, S., Shaffer, J. P., and Boldrick, J. C. 2003. Multiple hypothesis testing in microarray experiments. Stat. Sci. 18, 1, 71--103.

[8]

DuMouchel, W. 1999. Bayesian data mining in large frequency tables, with an application to the FDA spontaneous reporting system. Amer. Statistician 53, 177--202.

[9]

DuMouchel, W. and Pregibon, D. 2001. Empirical bayes screening for multi-item associations. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’01) 67--76.

Digital Library

[10]

Gionis, A., Mannila, H., Mielikäinen, T., and Tsaparas, P. 2006. Assessing data mining results via swap randomization. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 167--176.

Digital Library

[11]

Goethals, B., and Zaki, M. J., Eds. 2003. Proceedings of the 1st Workshop on Frequent Itemset Mining Implementations (FIMI03). Vol. 90, CEUR-WS Workshop Online Proceedings.

[12]

Goethals, B., Bayardo, R., and Zaki, M. J., Eds. 2004. Proceedings of the 2nd Workshop on Frequent Itemset Mining Implementations (FIMI04). Vol. 126, CEUR-WS Workshop Online Proceedings.

[13]

Hämäläinen, W. and Nykänen, M. 2008. Efficient discovery of statistically significant association rules. In Proceedings of the 8th IEEE International Conference on Data Mining. 203--212.

Digital Library

[14]

Han, J., and Kamber, M. 2001. Data Mining: Concepts and Techniques. Morgan Kaufmann, San Mateo, CA.

Digital Library

[15]

Han, J., Cheng, H., Xin, D., and Yan, X. 2007. Frequent pattern mining: Current status and future directions. Data Mining Knowl. Disc. 15, 1, 55--86.

Digital Library

[16]

Jaroszewicz, S. and Scheffer, T. 2005. Fast discovery of unexpected patterns in data, relative to a Bayesian. In Proceedings of the 11th International Conference on Knowledge Discovery and Data Mining. 118--127.

Digital Library

[17]

Megiddo, N. and Srikant, R. 1998. Discovering predictive association rules. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining. 274--278.

[18]

Mitzenmacher, M., and Upfal, E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge UK.

Digital Library

[19]

Pasquier, N., Bastide, Y., Taouil, R., and Lakhal, L. 1999. Discovering frequent closed itemsets for association rules. In Proceedings of the 7th International Conference on Database Theory. 398--416.

Digital Library

[20]

Purdom, P. W., Gucht, D. V., and Groth, D. P. 2004. Average case performance of the apriori algorithm. SIAM J. on Comput. 33, 5, 1223--1260.

[21]

Sayrafi, B., Gucht, D. V., and Purdom, P. W. 2005. On the effectiveness and efficiency of computing bounds on the support of item-sets in the frequent item-sets mining problem. In Proceedings of the 1st International Workshop on Open Source Data Mining. 46--55.

Digital Library

[22]

Silberschatz, A. and Tuzhilin, A. 1996. What makes patterns interesting in knowledge discovery systems. IEEE Trans. Knowl. Data Eng. 8, 6, 970--974.

Digital Library

[23]

Silverstein, C., Brin, S., and Motwani, R. 1998. Beyond market baskets: Generalizing association rules to dependence rules. Data Mining Knowl. Disc. 2, 1, 39--68.

Digital Library

[24]

Srikant, R., and Agrawal, R. 1996. Mining quantitative association rules in large relational tables. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1--12.

Digital Library

[25]

Tan, P., Steinbach, M., and Kumar, V. 2006. Introduction to Data Mining. Addison Wesley.

Digital Library

[26]

Xin, D., Han, J., Yan, X., and Cheng, H. 2005. Mining compressed frequent-pattern sets. In Proceedings of the 31st Very Large Data Base Conference. 709--720.

Digital Library

[27]

Zhang, H., Padmanabhan, B., and Tuzhilin, A. 2004. On the discovery of significant statistical quantitative rules. In Proceedings of the 10th International Conference on Knowledge Discovery and Data Mining. 374--383.

Digital Library

Cited By

C.B. AMahesh K(2023)Ontology-based data interestingness: A state-of-the-art reviewNatural Language Processing Journal10.1016/j.nlp.2023.1000214(100021)Online publication date: Sep-2023
https://doi.org/10.1016/j.nlp.2023.100021
Dalleiger SVreeken JZhang ARangwala H(2022)Discovering Significant Patterns under Sequential False Discovery ControlProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539398(263-272)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539398
Pellegrina LCousins CVandin FRiondato M(2022)MCRapper: Monte-Carlo Rademacher Averages for Poset Families and Approximate Pattern MiningACM Transactions on Knowledge Discovery from Data10.1145/353218716:6(1-29)Online publication date: 30-Jul-2022
https://dl.acm.org/doi/10.1145/3532187
Show More Cited By

Index Terms

An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

An efficient rigorous approach for identifying statistically significant frequent itemsets
PODS '09: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

As advances in technology allow for the collection, storage, and analysis of vast amounts of data, the task of screening and assessing the significance of discovered patterns is becoming a major challenge in data mining applications. In this work, we ...
An efficient pattern growth approach for mining fault tolerant frequent itemsets
Highlights
- Mining fault tolerant (FT) frequent itemsets are computationally expensive.
- ...
Abstract
Mining fault tolerant (FT) frequent itemsets from transactional databases are computationally more expensive than mining exact matching frequent itemsets. Previous algorithms mine FT frequent itemsets using Apriori heuristic. Apriori-...
Applying bit-vector projection approach for efficient mining of N-most interesting frequent itemsets
CI '07: Proceedings of the Third IASTED International Conference on Computational Intelligence

Real world datasets are sparse, dirty and contain hundreds of items. In such situations, discovering interesting rules (results) using traditional frequent itemset mining approach by specifying a user defined input support threshold is not appropriate. ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 59, Issue 3

June 2012

180 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2220357

Issue’s Table of Contents

Copyright © 2012 ACM.

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: 01 June 2012

Accepted: 01 February 2012

Revised: 01 February 2012

Received: 01 November 2009

Published in JACM Volume 59, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
805
Total Downloads

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

Reflects downloads up to 23 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

C.B. AMahesh K(2023)Ontology-based data interestingness: A state-of-the-art reviewNatural Language Processing Journal10.1016/j.nlp.2023.1000214(100021)Online publication date: Sep-2023
https://doi.org/10.1016/j.nlp.2023.100021
Dalleiger SVreeken JZhang ARangwala H(2022)Discovering Significant Patterns under Sequential False Discovery ControlProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539398(263-272)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539398
Pellegrina LCousins CVandin FRiondato M(2022)MCRapper: Monte-Carlo Rademacher Averages for Poset Families and Approximate Pattern MiningACM Transactions on Knowledge Discovery from Data10.1145/353218716:6(1-29)Online publication date: 30-Jul-2022
https://dl.acm.org/doi/10.1145/3532187
Pellegrina LCousins CVandin FRiondato MGupta RLiu YShah MRajan STang JPrakash B(2020)MCRapper: Monte-Carlo Rademacher Averages for Poset Families and Approximate Pattern MiningProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403267(2165-2174)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403267
Pellegrina LRiondato MVandin FTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Hypothesis Testing and Statistically-sound Pattern MiningProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3332286(3215-3216)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3332286
Tonon AVandin F(2019)Permutation Strategies for Mining Significant Sequential Patterns2019 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM.2019.00169(1330-1335)Online publication date: Nov-2019
https://doi.org/10.1109/ICDM.2019.00169
He ZZhang SWu J(2019)Significance-based discriminative sequential pattern miningExpert Systems with Applications10.1016/j.eswa.2018.12.046122(54-64)Online publication date: May-2019
https://doi.org/10.1016/j.eswa.2018.12.046
Kraska T(2018)NorthstarProceedings of the VLDB Endowment10.14778/3229863.324049311:12(2150-2164)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3240493
McCauley SMikkelsen JPagh RVan den Bussche JArenas M(2018)Set Similarity Search for Skewed DataProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196985(63-74)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196985
Henriques RMadeira S(2018)BSigData Mining and Knowledge Discovery10.1007/s10618-017-0521-232:1(124-161)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s10618-017-0521-2
Show More Cited By

View Options

Get Access

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents