Krimp: mining itemsets that compress

By Jilles Vreeken, Matthijs van Leeuwen, Arno Siebes. Data mining and knowledge discovery, 2011

329 citations recorded by the source corpus.

One of the major problems in pattern mining is the explosion of the number of results. Tight constraints reveal only common knowledge, while loose constraints lead to an explosion in the number of returned patterns. This is caused by large groups of patterns essentially describing the same set of transactions. In this paper we approach this problem using the MDL principle: the best set of patterns is that set that compresses the database best. For this task we introduce the Krimp algorithm. Experimental evaluation shows that typically only hundreds of itemsets are returned; a dramatic reduction, up to seven orders of magnitude, in the number of frequent item sets. These selections, called code tables, are of high quality. This is shown with compression ratios, swap-randomisation, and the accuracies of the code table-based Krimp classifier, all obtained on a wide range of datasets. Further, we extensively evaluate the heuristic choices made in the design of the algorithm.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/2b88e93072cfd1afe49aa9983182f9c7a9e89251

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Summarizing Significant Changes in Network Traffic Using Contrast Pattern Mining (2017, unknown): “The Krimp algorithm [9] encodes high quality patterns by mining candidate sets of frequent item-sets, and accepting a candidate if it improves compression.”
Frequent item set mining (2012, methodology): “To ﬁnd such pattern sets, various approaches have been devised, for example, ﬁnding pattern sets with which the data can be compressed well 81 , 82 or pattern sets in which all patterns contribute to partitioning the data.”
Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns (2015, methodology): “This approach has a proven track record in the domain of transaction data mining [32, 24] and has also been suc-”
Summarizing categorical data by clustering attributes (2011, methodology): “Alternatively, the KRIMP algorithm (Vreeken et al, 2011; Siebes et al, 2006) selects those itemsets that provide the best lossless compression of the database, i.e., the best description.”