Top down FP-growth for association rule mining

Ke Wang; Liu Tang; Jiawei Han; Junqiang Liu

doi:10.1007/3-540-47887-6_34

Top down FP-growth for association rule mining

Ke Wang, Liu Tang, Jiawei Han, Junqiang Liu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 topdown 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.

Original language	English (US)
Title of host publication	Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings
Editors	Ming-Syan Chen, Philip S. Yu, Bing Liu
Publisher	Springer
Pages	334-340
Number of pages	7
ISBN (Print)	9783540437048
DOIs	https://doi.org/10.1007/3-540-47887-6_34
State	Published - 2002
Externally published	Yes
Event	6th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2002 - Taipei, Taiwan, Province of China Duration: May 6 2002 → May 8 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2336
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2002
Country/Territory	Taiwan, Province of China
City	Taipei
Period	5/6/02 → 5/8/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/3-540-47887-6_34

Library availability

Discover UIUC Full Text

Cite this

Wang, K., Tang, L., Han, J., & Liu, J. (2002). Top down FP-growth for association rule mining. In M.-S. Chen, P. S. Yu, & B. Liu (Eds.), Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings (pp. 334-340). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2336). Springer. https://doi.org/10.1007/3-540-47887-6_34

Top down FP-growth for association rule mining. / Wang, Ke; Tang, Liu; Han, Jiawei et al.
Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings. ed. / Ming-Syan Chen; Philip S. Yu; Bing Liu. Springer, 2002. p. 334-340 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2336).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Wang, K, Tang, L, Han, J & Liu, J 2002, Top down FP-growth for association rule mining. in M-S Chen, PS Yu & B Liu (eds), Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2336, Springer, pp. 334-340, 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2002, Taipei, Taiwan, Province of China, 5/6/02. https://doi.org/10.1007/3-540-47887-6_34

Wang K, Tang L, Han J, Liu J. Top down FP-growth for association rule mining. In Chen MS, Yu PS, Liu B, editors, Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings. Springer. 2002. p. 334-340. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-47887-6_34

Wang, Ke ; Tang, Liu ; Han, Jiawei et al. / Top down FP-growth for association rule mining. Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings. editor / Ming-Syan Chen ; Philip S. Yu ; Bing Liu. Springer, 2002. pp. 334-340 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{340424111f344cb48c90be5020f5f2f0,

title = "Top down FP-growth for association rule mining",

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 topdown 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.",

author = "Ke Wang and Liu Tang and Jiawei Han and Junqiang Liu",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2002 ; Conference date: 06-05-2002 Through 08-05-2002",

year = "2002",

doi = "10.1007/3-540-47887-6_34",

language = "English (US)",

isbn = "9783540437048",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "334--340",

editor = "Ming-Syan Chen and Yu, {Philip S.} and Bing Liu",

booktitle = "Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Top down FP-growth for association rule mining

AU - Wang, Ke

AU - Tang, Liu

AU - Han, Jiawei

AU - Liu, Junqiang

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - 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 topdown 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.

AB - 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 topdown 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.

UR - http://www.scopus.com/inward/record.url?scp=84945313061&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945313061&partnerID=8YFLogxK

U2 - 10.1007/3-540-47887-6_34

DO - 10.1007/3-540-47887-6_34

M3 - Conference contribution

AN - SCOPUS:84945313061

SN - 9783540437048

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 334

EP - 340

BT - Advances in Knowledge Discovery and Data Mining - 6th Pacific-Asia Conference, PAKDD 2002, Proceedings

A2 - Chen, Ming-Syan

A2 - Yu, Philip S.

A2 - Liu, Bing

PB - Springer

T2 - 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2002

Y2 - 6 May 2002 through 8 May 2002

ER -

Top down FP-growth for association rule mining

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this