Further pruning for efficient association rule discovery

Songmao Zhang; Geoffrey Ian Webb

doi:10.1007/3-540-45656-2_52

Further pruning for efficient association rule discovery

Songmao Zhang, Geoffrey Ian Webb

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

4 Citations (Scopus)

Abstract

The Apriori algorithm’s frequent itemset approach has become the standard approach to discovering association rules. However, the computation requirements of the frequent itemset approach are infeasible for dense data and the approach is unable to discover infrequent associations. OPUS_AR is an efficient algorithm for association rule discovery that does not utilize frequent itemsets and hence avoids these problems. It can reduce search time by using additional constraints on the search space as well as constraints on itemset frequency. However, the effectiveness of the pruning rules used during search will determine the efficiency of its search. This paper presents and analyses pruning rules for use with OPUS_AR. We demonstrate that application of OPUS_AR is feasible for a number of datasets for which application of the frequent itemset approach is infeasible and that the new pruning rules can reduce compute time by more than 40%.

Original language	English
Title of host publication	AI 2001: Advances in Artificial Intelligence
Subtitle of host publication	14th Australian Joint Conference on Artificial Intelligence Adelaide, Australia, December 10-14, 2001 Proceedings
Editors	Markus Stumptner, Dan Corbett, Mike Brooks
Place of Publication	Berlin Germany
Publisher	Springer
Pages	605-618
Number of pages	14
ISBN (Print)	3540429603
DOIs	https://doi.org/10.1007/3-540-45656-2_52
Publication status	Published - 2001
Externally published	Yes
Event	Australasian Joint Conference on Artificial Intelligence 2001 - Adelaide, Australia Duration: 10 Dec 2001 → 14 Dec 2001 Conference number: 14th https://link.springer.com/book/10.1007/3-540-45656-2 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2256
ISSN (Print)	0302-9743

Conference

Conference	Australasian Joint Conference on Artificial Intelligence 2001
Abbreviated title	AI 2001
Country/Territory	Australia
City	Adelaide
Period	10/12/01 → 14/12/01
Internet address	https://link.springer.com/book/10.1007/3-540-45656-2 (Proceedings)

Access to Document

10.1007/3-540-45656-2_52

Cite this

Zhang, S., & Webb, G. I. (2001). Further pruning for efficient association rule discovery. In M. Stumptner, D. Corbett, & M. Brooks (Eds.), AI 2001: Advances in Artificial Intelligence: 14th Australian Joint Conference on Artificial Intelligence Adelaide, Australia, December 10-14, 2001 Proceedings (pp. 605-618). (Lecture Notes in Computer Science; Vol. 2256). Springer. https://doi.org/10.1007/3-540-45656-2_52

Zhang, Songmao ; Webb, Geoffrey Ian. / Further pruning for efficient association rule discovery. AI 2001: Advances in Artificial Intelligence: 14th Australian Joint Conference on Artificial Intelligence Adelaide, Australia, December 10-14, 2001 Proceedings. editor / Markus Stumptner ; Dan Corbett ; Mike Brooks. Berlin Germany : Springer, 2001. pp. 605-618 (Lecture Notes in Computer Science).

@inproceedings{e5ed7fd912244908afce29b8a4717c7c,

title = "Further pruning for efficient association rule discovery",

abstract = "The Apriori algorithm{\textquoteright}s frequent itemset approach has become the standard approach to discovering association rules. However, the computation requirements of the frequent itemset approach are infeasible for dense data and the approach is unable to discover infrequent associations. OPUS_AR is an efficient algorithm for association rule discovery that does not utilize frequent itemsets and hence avoids these problems. It can reduce search time by using additional constraints on the search space as well as constraints on itemset frequency. However, the effectiveness of the pruning rules used during search will determine the efficiency of its search. This paper presents and analyses pruning rules for use with OPUS_AR. We demonstrate that application of OPUS_AR is feasible for a number of datasets for which application of the frequent itemset approach is infeasible and that the new pruning rules can reduce compute time by more than 40%.",

author = "Songmao Zhang and Webb, {Geoffrey Ian}",

year = "2001",

doi = "10.1007/3-540-45656-2_52",

language = "English",

isbn = "3540429603",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "605--618",

editor = "Markus Stumptner and Dan Corbett and Mike Brooks",

booktitle = "AI 2001: Advances in Artificial Intelligence",

note = "Australasian Joint Conference on Artificial Intelligence 2001, AI 2001 ; Conference date: 10-12-2001 Through 14-12-2001",

url = "https://link.springer.com/book/10.1007/3-540-45656-2",

}

Zhang, S & Webb, GI 2001, Further pruning for efficient association rule discovery. in M Stumptner, D Corbett & M Brooks (eds), AI 2001: Advances in Artificial Intelligence: 14th Australian Joint Conference on Artificial Intelligence Adelaide, Australia, December 10-14, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2256, Springer, Berlin Germany, pp. 605-618, Australasian Joint Conference on Artificial Intelligence 2001, Adelaide, South Australia, Australia, 10/12/01. https://doi.org/10.1007/3-540-45656-2_52

Further pruning for efficient association rule discovery. / Zhang, Songmao; Webb, Geoffrey Ian.
AI 2001: Advances in Artificial Intelligence: 14th Australian Joint Conference on Artificial Intelligence Adelaide, Australia, December 10-14, 2001 Proceedings. ed. / Markus Stumptner; Dan Corbett; Mike Brooks. Berlin Germany: Springer, 2001. p. 605-618 (Lecture Notes in Computer Science; Vol. 2256).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Further pruning for efficient association rule discovery

AU - Zhang, Songmao

AU - Webb, Geoffrey Ian

N1 - Conference code: 14th

PY - 2001

Y1 - 2001

N2 - The Apriori algorithm’s frequent itemset approach has become the standard approach to discovering association rules. However, the computation requirements of the frequent itemset approach are infeasible for dense data and the approach is unable to discover infrequent associations. OPUS_AR is an efficient algorithm for association rule discovery that does not utilize frequent itemsets and hence avoids these problems. It can reduce search time by using additional constraints on the search space as well as constraints on itemset frequency. However, the effectiveness of the pruning rules used during search will determine the efficiency of its search. This paper presents and analyses pruning rules for use with OPUS_AR. We demonstrate that application of OPUS_AR is feasible for a number of datasets for which application of the frequent itemset approach is infeasible and that the new pruning rules can reduce compute time by more than 40%.

AB - The Apriori algorithm’s frequent itemset approach has become the standard approach to discovering association rules. However, the computation requirements of the frequent itemset approach are infeasible for dense data and the approach is unable to discover infrequent associations. OPUS_AR is an efficient algorithm for association rule discovery that does not utilize frequent itemsets and hence avoids these problems. It can reduce search time by using additional constraints on the search space as well as constraints on itemset frequency. However, the effectiveness of the pruning rules used during search will determine the efficiency of its search. This paper presents and analyses pruning rules for use with OPUS_AR. We demonstrate that application of OPUS_AR is feasible for a number of datasets for which application of the frequent itemset approach is infeasible and that the new pruning rules can reduce compute time by more than 40%.

U2 - 10.1007/3-540-45656-2_52

DO - 10.1007/3-540-45656-2_52

M3 - Conference Paper

SN - 3540429603

T3 - Lecture Notes in Computer Science

SP - 605

EP - 618

BT - AI 2001: Advances in Artificial Intelligence

A2 - Stumptner, Markus

A2 - Corbett, Dan

A2 - Brooks, Mike

PB - Springer

CY - Berlin Germany

T2 - Australasian Joint Conference on Artificial Intelligence 2001

Y2 - 10 December 2001 through 14 December 2001

ER -

Zhang S, Webb GI. Further pruning for efficient association rule discovery. In Stumptner M, Corbett D, Brooks M, editors, AI 2001: Advances in Artificial Intelligence: 14th Australian Joint Conference on Artificial Intelligence Adelaide, Australia, December 10-14, 2001 Proceedings. Berlin Germany: Springer. 2001. p. 605-618. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45656-2_52