Finding the True Frequent Itemsets
  Frequent Itemsets (FIs) mining is a fundamental primitive in data mining. It
requires to identify all itemsets appearing in at least a fraction $\theta$ of
a transactional dataset $\mathcal{D}$. Often though, the ultimate goal of
mining $\mathcal{D}$ is not an analysis of the dataset \emph{per se}, but the
understanding of the underlying process that generated it. Specifically, in
many applications $\mathcal{D}$ is a collection of samples obtained from an
unknown probability distribution $\pi$ on transactions, and by extracting the
FIs in $\mathcal{D}$ one attempts to infer itemsets that are frequently (i.e.,
with probability at least $\theta$) generated by $\pi$, which we call the True
Frequent Itemsets (TFIs). Due to the inherently stochastic nature of the
generative process, the set of FIs is only a rough approximation of the set of
TFIs, as it often contains a huge number of \emph{false positives}, i.e.,
spurious itemsets that are not among the TFIs. In this work we design and
analyze an algorithm to identify a threshold $\hat{\theta}$ such that the
collection of itemsets with frequency at least $\hat{\theta}$ in $\mathcal{D}$
contains only TFIs with probability at least $1-\delta$, for some
user-specified $\delta$. Our method uses results from statistical learning
theory involving the (empirical) VC-dimension of the problem at hand. This
allows us to identify almost all the TFIs without including any false positive.
We also experimentally compare our method with the direct mining of
$\mathcal{D}$ at frequency $\theta$ and with techniques based on widely-used
standard bounds (i.e., the Chernoff bounds) of the binomial distribution, and
show that our algorithm outperforms these methods and achieves even better
results than what is guaranteed by the theoretical analysis.
