document: Approximating a collection of frequent sets One of the most well-studied problems in data mining is computing the collection of frequent item sets in large transactional databases . One obstacle for the applicability of frequent-set mining is that the size of the output collection can be far too large to be carefully examined and understood by the users . Even restricting the output to the border of the frequent item-set collection does not help much in alleviating the problem . In this paper we address the issue of overwhelmingly large output size by introducing and studying the following problem : What are the k sets that best approximate a collection of frequent item sets ? Our measure of approximating a collection of sets by k sets is defined to be the size of the collection covered by the the k sets , i.e. , the part of the collection that is included in one of the k sets . We also specify a bound on the number of extra sets that are allowed to be covered . We examine different problem variants for which we demonstrate the hardness of the corresponding problems and we provide simple polynomial-time approximation algorithms . We give empirical evidence showing that the approximation methods work well in practice .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O