Title: Fast estimation of the pattern frequency spectrum
Authors: van Leeuwen, Matthijs ×
Ukkonen, Antti #
Issue Date: 2014
Publisher: Springer
Host Document: 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
Conference: The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD) location:Nancy, France date:15-19 September 2014
Abstract: 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.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
freqcurve-camready.pdfPre-print Published 1427KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.