Approximation of frequency queries by means of free-sets
Principles of Data Mining and Knowledge Discovery, Springer, (2000)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., set 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 representation 10.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 run on
real dense data sets show a significant reduction of the size of the
output when compared with standard frequent itemsets extraction.
Furthermore, the experiments show that the extraction of frequent
free-sets is still possible when the extraction of frequent itemsets
becomes intractable. Finally, we show that the error made when
approximating frequent itemset support remains very low in practice.
1
Links and resources
Tags
community
@francesco.k's tags highlighted