Abstract
In this paper, we propose an efficient algorithm, called TD-FP-Growth (the shorthand for Top-Down FP-Growth), to mine frequent patterns. TD-FP-Growth searches the FP-tree in the top-down order, as opposed to the bottom-up order of previously proposed FP-Growth. The advantage of the top-down search is not generating conditional pattern bases and sub-FP-trees, thus, saving substantial amount of time and space. We extend TD-FP-Growth to mine association rules by applying two new pruning strategies: one is to push multiple minimum supports and the other is to push the minimum confidence. Experiments show that these algorithms and strategies are highly effective in reducing the search space.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Reference
R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. ACM-SIGMOD 1993, 207–216.
H. Toivonen. Sampling large databases for association rules. VLDB 1996, 134–145.
R. Agrawal and S. Srikant. Mining sequential patterns. ICDE 1995, 3–14.
J. Han, J. Pei and Y. Yin. Mining Frequent patterns without candidate generation. SIGMOD 2000, 1–12.
R. Srikant and R. Agrawal. Mining generalized association rules. VLDB 1995, 407–419.
R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. VLDB 1996, 134–145.
B. Liu, W. Hsu, and Y. Ma. Mining association rules with multiple minimum supports. KDD 1999, 337–341
K. Wang, Y. He and J. Han. Mining frequent patterns using support constraints. VLDB 2000, 43–52.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, K., Tang, L., Han, J., Liu, J. (2002). Top Down FP-Growth for Association Rule Mining. In: Chen, MS., Yu, P.S., Liu, B. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2002. Lecture Notes in Computer Science(), vol 2336. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47887-6_34
Download citation
DOI: https://doi.org/10.1007/3-540-47887-6_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43704-8
Online ISBN: 978-3-540-47887-4
eBook Packages: Springer Book Archive