An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
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 thresholds*for a dataset, such that the number of itemsets with support at leasts*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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2012
- Source ID
- 10.1145/2220357.2220359
Entities
People
- Adam Kirsch
- Andrea Pietracaprina
- Eli Upfal
- Fabio Vandin
- Geppino Pucci
- Michael Mitzenmacher
Organizations
- Brown University
- Division of Computer and Network Systems
- Division of Computing and Communication Foundations
- Division of Information and Intelligent Systems
- Harvard University
- National Science Foundation
- Office of Naval Research
- Seventh Framework Programme
- University of Padua