Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) 2015 vol:2 pages:114 -129
The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD) location:Nancy, France date:15-19 September 2014
Both exact and approximate counting of the number of frequent
patterns for a given frequency threshold are hard problems. Still,
having even coarse prior estimates of the number of patterns is useful, as
these can be used to appropriately set the threshold and avoid waiting
endlessly for an unmanageable number of patterns. Moreover, we argue
that the number of patterns for different thresholds is an interesting
summary statistic of the data: the pattern frequency spectrum.
To enable fast estimation of the number of frequent patterns, we adapt
the classical algorithm by Knuth for estimating the size of a search tree.
Although the method is known to be theoretically suboptimal, we demonstrate
that in practice it not only produces very accurate estimates, but
is also very efficient. Moreover, we introduce a small variation that can
be used to estimate the number of patterns under constraints for which
the Apriori property does not hold. The empirical evaluation shows that
this approach obtains good estimates for closed itemsets.
Finally, we show how the method, together with isotonic regression, can
be used to quickly and accurately estimate the frequency pattern spectrum:
the curve that shows the number of patterns for every possible
value of the frequency threshold. Comparing such a spectrum to one
that was constructed using a random data model immediately reveals
whether the dataset contains any structure of interest.