Article,
Free-sets: a condensed representation of boolean data for the approximation of frequency queries
Data Mining and Knowledge Discovery, 7 (1): 5--22 (2003)
Abstract
Given a large collection of transactions containing items, a basic
common data mining problem is to extract the so-called frequent
itemsets (i.e., sets of items appearing in at least a given number of
transactions). In this paper, we propose a structure called free-sets,
from which we can approximate any itemset support (i.e., the number of
transactions containing the itemset) and we formalize this notion in
the framework of -adequate representations (H. Mannila and H.
Toivonen, 1996. In Proc. of the Second International Conference on
Knowledge Discovery and Data Mining (KDD'96), pp. 189-194). We show
that frequent free-sets can be efficiently extracted using pruning
strategies developed for frequent itemset discovery, and that they can
be used to approximate the support of any frequent itemset.
Experiments on real dense data sets show a significant reduction of
the size of the output when compared with standard frequent itemset
extraction. abriged
