Abstract Mining frequent patterns is plagued by the problem of pattern explosion making pattern reduction techniques a key challenge in pattern mining. In this talk we propose a theoretical framework for pattern reduction. We do this by measuring the robustness of a property of an itemset such as closedness or non-derivability. The robustness of a property is the probability that this property holds on random subsets of the original data. We study four properties: closed, free, non-derivable and totally shattered itemsets, demonstrating how we can compute the robustness analytically without actually sampling the data. Our concept of robustness has many advantages: Unlike statistical approaches for reducing patterns, we do not assume a null hypothesis or any noise model and the patterns reported are simply a subset of all patterns with this property as opposed to approximate patterns for which the property does not really hold. If the underlying property is monotonic, then the measure is also monotonic, allowing us to efficiently mine robust itemsets. We further derive a parameter-free technique for ranking itemsets that can be used for top-k approaches.
Bio Nikolaj Tatti is a postdoctoral researcher at the Advanced Database Research and Modelling group of the University of Antwerp, Belgium. He received his PhD in 2009 from Department of Information and Computer Science, Helsinki University of Technology, Finland. Major part of Nikolaj's work focuses on discovering efficiently statistically significant non-redundant patterns from binary and sequential data. Other topics include using patterns as a surrogate for the original data in various tasks such as computing queries or determining the distance between two data sets. Nikolaj Tatti's research interests are algorithms, statistics, statistical analysis of the algorithms, algorithms involved with computing statistics, and mathematics in general.