Mining Non-Redundant Association Rules
Data Mining and Knowledge DiscoveryPublished 7 September 2004
Mohammed J. Zaki
Citations390
SJR quartileQ1
SJR score1.02
SNIP1.88
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new framework for associations based on the concept of closed frequent itemsets is presented, with the number of non-redundant rules produced by the new approach is exponentially smaller than the rule set from the traditional approach.
Abstract
The traditional association rule mining framework produces many redundant rules. The extent of redundancy is a lot larger than previously suspected. We present a new framework for associations based on the concept of closed frequent itemsets. The number of non-redundant rules produced by the new approach is exponentially (in the length of the longest frequent itemset) smaller than the rule set from the traditional approach. Experiments using several "hard" as well as "easy" real and synthetic databases confirm the utility of our framework in terms of reduction in the number of rules presented to the user, and in terms of time.
Keywords
Computer Science
Cambridge University Press eBooksIntroduction to Lattices and Order
4,924 Citations2002Brian Davey, H. A. Priestley
Formal Concept Analysis: Mathematical Foundations
4,282 Citations1998Bernhard Ganter, Rudolf Wille +1 more
Formal Concept Analysis
3,078 Citations1999Bernhard Ganter, Rudolf Wille
Dynamic itemset counting and implication rules for market basket data
1,954 Citations1997Sergey Brin, Rajeev Motwani +2 more
A new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling and a new way of generating “implication rules” which are normalized based on both the antecedent and the consequent.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
Lecture notes in computer scienceDiscovering Frequent Closed Itemsets for Association Rules
1,361 Citations1999Nicolas Pasquier, Yves Bastide +2 more
This paper proposes a new algorithm, called A-Close, using a closure mechanism to find frequent closed itemsets, and shows that this approach is very valuable for dense and/or correlated data that represent an important part of existing databases.
Efficiently mining long patterns from databases
1,297 Citations1998Roberto J. Bayardo
A pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern, compared with previous algorithms that scale exponentially with longest pattern length.
New algorithms for fast discovery of association rules
1,112 Citations1997Mohammed J. Zaki, Srinivasan Parthasarathy +2 more
New algorithms for fast association mining, which scan the database only once, are presented, addressing the open question whether all the rules can be efficiently extracted in a single database pass.
CHARM: An Efficient Algorithm for Closed Itemset Mining
896 Citations2002Mohammed J. Zaki, Ching-Jui Hsiao
CHARM is an efficient algorithm for mining all frequent closed itemsets that enumerates closed sets using a dual itemset-tidset search tree, using an efficient hybrid search that skips many levels, and uses a technique called diffsets to reduce the memory footprint of intermediate computations.
CLOSET : An Efficient Algorithm for Mining Frequent Closed Itemsets
829 Citations2000Jian Pei
Information SystemsEfficient mining of association rules using closed itemset lattices
739 Citations1999Nicolas Pasquier, Yves Bastide +2 more
Experiments showed that Close is very efficient for mining dense and/or correlated data such as census style data, and performs reasonably well for market basket style data.
Finding interesting rules from large sets of discovered association rules
717 Citations1994Mika Klemettinen, Heikki Mannila +3 more
It is shown how a simple formalism of rule templates makes it possible to easily describe the structure of interesting rules, and how a visualization tool interfaces with rule templates.
Exploratory mining and pruning optimizations of constrained associations rules
713 Citations1998Raymond T. Ng, Laks V. S. Lakshmanan +2 more
An architecture that opens up the black-box, and supports constraint-based, human-centered exploratory mining of associations, and introduces and analyzes two properties of constraints that are critical to pruning: anti-monotonicity and succinctness.
Mining the most interesting rules
651 Citations1999Roberto J. Bayardo, Rakesh Agrawal
It is argued that by returning a broader set of rules than previous algorithms, these techniques allow for improved insight into the data and support more user-interaction in the optimized rule-mining process.
MAFIA: a maximal frequent itemset algorithm for transactional databases
610 Citations2002Doug Burdick, Manuel Calimlim +1 more
A new algorithm for mining maximal frequent itemsets from a transactional database that integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms and combines a vertical bitmap representation of the database with an efficient relative bitmap compression schema is presented.
Computational IntelligenceINCREMENTAL CONCEPT FORMATION ALGORITHMS BASED ON GALOIS (CONCEPT) LATTICES
510 Citations1995Robert Godin, Rokia Missaoui +1 more
Empirical evidence shows that, on the average, the incremental update of the Galois lattice is done in time proportional to the number of instances previously treated, and the worst‐case analysis of the algorithm also shows linear growth with respect to thenumber of instances.
Pruning and summarizing the discovered associations
424 Citations1999Bing Liu, Wynne Hsu +1 more
The technique first prunes the discovered associations to remove those insignificant associations, and then finds a special subset of the unpruned associations to form a summary of the discovered association rules, which are then called the direction setting rules.
Lecture notes in computer scienceMining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets
326 Citations2000Yves Bastide, Nicolas Pasquier +3 more
Two new bases for association rules are defined which union is a generating set for all valid association rules with support and confidence and consist of the nonredundant exact and approximate association rules having minimal antecedents and maximal consequents.
ACM SIGKDD Explorations NewsletterMining frequent patterns with counting inference
300 Citations2000Yves Bastide, Rafik Taouil +3 more
It is shown that the support of frequent non-key patterns can be inferred from frequent key patterns without accessing the database, and PASCAL is among the most efficient algorithms for mining frequent patterns.
Lecture notes in computer sciencePincer-search: A new algorithm for discovering the maximum frequent set
279 Citations1998Dao-I Lin, Zvi M. Kedem
This work presents a new algorithm which combines both the bottom-up and top-down searches, and produces the maximum frequent set, i.e., the set containing all maximal frequent itemsets, which therefore specifies immediately all frequent itemets.
Parallel Algorithms for Discovery of Association Rules
261 Citations1997Mohammed J. Zaki, Srinivasan Parthasarathy +4 more
Pruning and Grouping Discovered Association Rules
154 Citations1995Hannu Toivonen, Mika Klemettinen +3 more
This work shows how the set of rules can be pruned by forming rule covers, and discusses grouping of association rules by clustering, and presents some experimental results of both pruning and grouping.
French digital mathematics library (Numdam)Implications partielles dans un contexte
136 Citations1991Michael Luxenburger
Mining Bases for Association Rules Using Closed Sets
43 Citations2005Rafik Taouil, N. Pasquier +2 more
Using the frequent closed itemset groundwork, this work proposes to generate bases for association rules, that are non-redundant generating sets for all association rules.