Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets
Lecture notes in computer sciencePublished 1 January 2000
Yves Bastide, Nicolas Pasquier, Rafik Taouil, Gerd Stumme, Lotfi Lakhal
Citations326
SJR quartileQ2
SJR score0.35
SNIP0.55
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
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.
Abstract
The problem of the relevance and the usefulness of extracted association rules is of primary importance because, in the majority of cases, real-life databases lead to several thousands association rules with high confidence and among which are many redundancies. Using the closure of the Galois connection, we define two new bases for association rules which union is a generating set for all valid association rules with support and confidence. These bases are characterized using frequent closed itemsets and their generators; they consist of the non-redundant exact and approximate association rules having minimal antecedents and maximal consequents, i.e. the most relevant association rules. Algorithms for extracting these bases are presented and results of experiments carried out on real-life databases show that the proposed bases are useful, and that their generation is not time consuming.
Keywords
Computer Science
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
IEEE ExpertData mining and knowledge discovery: making sense out of data
4,643 Citations1996U.M. Feyyad
Find loads of the data mining and knowledge discovery making sense out of data book catalogues in this site as the choice of you visiting this page.
Formal Concept Analysis: Mathematical Foundations
4,282 Citations1998Bernhard Ganter, Rudolf Wille +1 more
Formal Concept Analysis
3,078 Citations1999Bernhard Ganter, Rudolf Wille
Future Generation Computer SystemsMining generalized association rules
1,617 Citations1997Ramakrishnan Srikant, Rakesh Agrawal
A new interest-measure for rules which uses the information in the taxonomy is presented, and given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules.
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.
Beyond market baskets
1,287 Citations1997Sergey Brin, Rajeev Motwani +1 more
This work develops the notion of mining rules that identify correlations (generalizing associations), and proposes measuring significance of associations via the chi-squared test for correlation from classical statistics, enabling the mining problem to reduce to the search for a border between correlated and uncorrelated itemsets in the lattice.
Discovery of Multiple-Level Association Rules from Large Databases
920 Citations1995Jiawei Han, Yongjian Fu
A top-down progressive deepening method is developed for mining multiplelevel association rules from large transaction databases by extension of some existing association rule mining techniques.
Mining association rules with item constraints
769 Citations1997Ramakrishnan Srikant, Quoc Vu +1 more
This work considers the problem of integrating constraints that are Boolean expressions over the presence or absence of items into the association discovery algorithm and presents three integrated algorithms for mining association rules with item constraints and discusses their tradeoffs.
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.
IEEE Transactions on Knowledge and Data EngineeringWhat makes patterns interesting in knowledge discovery systems
675 Citations1996Abraham Silberschatz, Alexander Tuzhilin
The focus of the paper is on studying subjective measures of interestingness, which are classified into actionable and unexpected, and the relationship between them is examined.
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.
ACM Transactions on Database SystemsComputational problems related to the design of normal form relational schemas
459 Citations1979Catriel Beeri, Philip A. Bernstein
It is shown that most interesting algorithmic questions about Boyce-Codd normal form and keys are NP-complete and are therefore probably not amenable to fast algorithmic solutions.
Data Mining and Knowledge DiscoveryBeyond Market Baskets: Generalizing Association Rules to Dependence Rules
374 Citations1998Craig Silverstein, Sergey Brin +1 more
This work develops the notion of dependence rules that identify statistical dependence in both the presence and absence of items in itemsets in the lattice and develops pruning strategies based on the closure property that lead to an efficient algorithm for discovering dependence rules.
Constraint-based rule mining in large, dense databases
359 Citations1999Roberto J. Bayardo, R. K. Agrawal +1 more
The interestingness of deviations
214 Citations1994Gregory Piatetsky-Shapiro, Christopher J. Matheus
It is argued that related deviations should be grouped together in a finding and that the interestingness of a finding is the estimated benefit from a possible action connected to it, and methods for determining the Estimated benefit from the impact of the deviations and the success probability of an action are discussed.
French digital mathematics library (Numdam)Implications partielles dans un contexte
136 Citations1991Michael Luxenburger
Journal of the ACMMinimum Covers in Relational Database Model
131 Citations1980David Maier
Numerous algonthms concernmg relahonal databases use a cover for a set of funcUonal dependencies as all or part of their input Examples are Been and Bernsteln's synthesis algorithm and the tableau modtfication algorithm of Aho et al.
Pruning Closed Itemset Lattices for Association Rules
76 Citations1998Nicolas Pasquier, Yves Bastide +2 more
An efficient algorithm, called Close, based on a new mining method: pruning of the closed set lattice (closed itemset lattice), which is closely related to Wille's concept lattice in formal concept analysis.
Closed Set Based Discovery of Small Covers for Association Rules.
71 Citations1999Nicolas Pasquier, Yves Bastide +2 more
New algorithms based on the Galois closed sets are proposed to limit the extraction to small informative covers for exact and approximate rules, and small structural covers for approximate rules.