\invitedTalkHeaderTwoAuthors
{Ten-Year Award Talk: Non-Derivable\break Frequent Itemsets}
{Toon Calders}
{Eindhoven University of Technology, The Netherlands}
%{t.calders@tue.nl}
{http://wwwis.win.tue.nl/~tcalders/}
{Bart Goethals}
{University of Antwerp, Belgium}
%{bart.goethals@ua.ac.be}
{http://adrem.ua.ac.be/~goethals/}
{Wednesday 09:00--10:00}
{Room: Chem, LT1}
%{Wednesday}


\section*{Abstract}
In 1993, in their ACM SIGMOD'93 paper, Agrawal et al.\ proposed the frequent itemset mining problem.
For many years following the introduction of this problem, numerous studies on algorithms for this problem 
had resulted in significant performance improvements for mining all frequent itemsets. At the same time, however, 
it also became clear that problem definition in itself, was problematic: regardless of the 
algorithm being used, if the minimal support threshold is set too low, or the data is highly correlated, the
number of frequent itemsets itself becomes prohibitively large. Furthermore, typically the collection of frequent itemsets
contains a lot of redundancy. 

To overcome this problem, several proposals were made to construct
concise representations of the frequent itemsets, instead of mining all frequent itemsets; the most well-known being
the \emph{closed sets} proposed by Pasquier et al.\ at ICDT 1999. It is in this context that our ECML PKDD 2002 paper
\emph{Mining All Non-Derivable Frequent Itemsets} was written. The main goal of our paper was to identify redundancies
in the set of all frequent itemsets and to exploit these redundancies in order to reduce the result of a mining operation. 
Deduction rules to derive tight bounds on the support of candidate itemsets were proposed, and it was shown how the 
deduction rules allow for constructing a minimal representation for all frequent itemsets. 

In our presentation we
present the most important properties and algorithms for mining non-derivable itemsets from our 2002 paper and
follow-up works. We will also position the non-derivable itemsets as part of a much larger program of
understanding the interactions of itemset frequencies as a special case of probabilistic reasoning, and end with
the recently developed statistically based itemset interestingness measures as a natural next step in this 
endeavor to make pattern mining more meaningful.

%\section*{Bio}

