Efficient mining of both positive and negative association rules
ACM Transactions on Information SystemsPublished 1 July 2004
Xindong Wu, Chengqi Zhang, Shichao Zhang
Citations469
SJR quartileQ1
SJR score1.54
SNIP2.78
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
This paper presents an efficient method for mining both positive and negative association rules in databases, and extends traditional associations to include association rules of forms A ⇒ ¬ , which indicate negative associations between itemsets.
Abstract
This paper presents an efficient method for mining both positive and negative association rules in databases. The method extends traditional associations to include association rules of forms A ⇒ ¬ B , ¬ A ⇒ B , and ¬ A ⇒ ¬ B , which indicate negative associations between itemsets. With a pruning strategy and an interestingness measure, our method scales to large databases. The method has been evaluated using both synthetic and real-world databases, and our experimental results demonstrate its effectiveness and efficiency.
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.
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +1 more
IEEE Transactions on Knowledge and Data EngineeringData mining: an overview from a database perspective
2,221 Citations1996Ming-Syan Chen⋆, Jiawei Han +1 more
This article provides a survey, from a database researcher's point of view, on the data mining techniques developed recently, a classification of the available data mining Techniques, and a comparative study of such techniques is presented.
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.
IEEE Transactions on Knowledge and Data EngineeringDatabase mining: a performance perspective
1,488 Citations1993R. K. Agrawal, Tomasz Imieliński +1 more
The authors' perspective of database mining as the confluence of machine learning techniques and the performance emphasis of database technology is presented and an algorithm for classification obtained by combining the basic rule discovery operations is given.
Mining quantitative association rules in large relational tables
1,484 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
This work deals with quantitative attributes by fine-partitioning the values of the attribute and then combining adjacent partitions as necessary and introduces measures of partial completeness which quantify the information lost due to partitioning.
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.
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.
IEEE Transactions on Knowledge and Data EngineeringUsing a hash-based method with transaction trimming for mining association rules
443 Citations1997Jong Soo Park, Ming-Syan Chen⋆ +1 more
An effective algorithm for the candidate set generation is developed that is a hash-based algorithm and is especially effective for the generation of a candidate set for large 2-itemsets, thus resolving the performance bottleneck.
Mining for strong negative associations in a large database of customer transactions
271 Citations2002Ashoka Savasere, Edward Omiecinski +1 more
An algorithm is described that efficiently finds all such negative associations by combining previously discovered positive associations with domain knowledge to constrain the search space such that fewer but more interesting negative rules are mined.
A new framework for itemset generation
244 Citations1998Charų C. Aggarwal, Philip S. Yu
An algorithm is provided which provides very good computational efficiency, while maintaining statistical robuetneas, which implies that the method can be applied to find association rules in datasets in which items may appear in a sizeable percentage of the transactions (dense datasets), dataset in which the items have varying density, or even negative association rules.
A belief-driven method for discovering unexpected patterns
243 Citations1998Balaji Padmanabhan
This paper proposes a new method of discovering unexpected patterns that takes into consideration prior background knowledge of decision makers and uses these beliefs to seed the search for patterns in data that contradict the beliefs.
Query flocks
159 Citations1998Dick Tsur, Jeffrey D. Ullman +5 more
The general idea, called “query flocks,” is a generate-and-test model for data-mining problems and is shown how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers.
Small is beautiful
146 Citations2000Balaji Padmanabhan, Alexander Tuzhilin
New methods for discovering a minimal set of unexpected patterns that discover orders of magnitude fewer patterns and yet retain most of the truly interesting ones are proposed.
Lecture notes in computer scienceException Rule Mining with a Relative Interestingness Measure
115 Citations2000Farhad Hussain, Huan Liu +2 more
This paper presents a method for mining exception rules based on a novel measure which estimates interestingness relative to its corresponding common sense rule and reference rule and shows through the experiments how this proposed relative measure can give an unbiased estimate of relative interestingness in a rule considering already mined rules.
Knowledge Discovery and Data MiningAutonomous discovery of reliable exception rules
113 Citations1997Einoshin Suzuki
A probabilistic estimation approach in which an exception rule associated with a common sense rule in the form of a ride pair is obtained, based on the normal approximations of the multinomial distributions, rule pairs which satisfy, with high confidence, all the specified conditions.
Lecture notes in computer scienceIndirect Association: Mining Higher Order Dependencies in Data
85 Citations2000Pang‐Ning Tan, Vipin Kumar +1 more
This paper proposes an algorithm for deriving indirectly associated itempairs and demonstrates the potential application of these patterns in the retail, textual and stock market domains.
Lecture notes in computer scienceEfficient Search of Reliable Exceptions
60 Citations1999Huan Liu, Hongjun Lü +2 more
This paper addresses the problem of finding weak patterns (i.e., reliable exceptions) from databases using deviation analysis to identify interesting exceptions and explore reliable ones, and demonstrates the effectiveness of the proposed approach through a set of real-life data sets.
Parallel mining algorithms for generalized association rules with classification hierarchy
56 Citations1998Takahiko Shintani, Masaru Kitsuregawa
The new parallel algorithms for mining association rules with classification hierarchy on a shared-nothing parallel machine to improve its performance and minimizes interprocessor communication by considering the hierarchy are proposed.
Lecture notes in computer scienceShare based measures for itemsets
48 Citations1997Colin L. Carter, Howard J. Hamilton +1 more
The measures share, coincidence and dominance are introduced as alternatives to the standard itemset methodology measure of support, which has the advantage over support of reflecting accurately how many units are being moved by a business.
Mining exception instances to facilitate workflow exception handling
45 Citations2003San‐Yih Hwang, Sun-Fa Ho +1 more
This work proposes a novel approach to facilitating users in proposing solutions for resolving a given exception, which scans through the previous records in handling exceptions, looking for those that are close to the current exception.
Knowledge Discovery and Data MiningExceptional knowledge discovery in databases based on information theory
43 Citations1996Einoshin Suzuki, Masamichi Shimura
An information-theoretic approach in which exceptional knowledge associated with general knowledge is obtained in the form of a rule pair using a depth-first search method and the product of the ACEs of the rule pair is introduced as the criterion for evaluating the interestingness of exceptional knowledge.
Lecture notes in computer scienceMining Indirect Associations in Web Data
41 Citations2002Pang‐Ning Tan, Vipin Kumar
A new data mining technique called indirect association is applied to the Web click-stream data to find pairs of pages that are negatively associated with each other, but are positively associated with another set of pages called the mediator.