Mining Large Itemsets for Association Rules.
Published 1 January 1998
Charų C. Aggarwal, Philip S. Yu
Citations61
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 survey of the itemset method for association rule generation and other formulations of associations which can be viable alternatives to the traditional association rule ge neration method are discussed.
Abstract
This paper provides a survey of the itemset method for association rule generation. The paper discusses past research on the topic and also studies the relevance and importance of the itemset method in generating association rules. We discuss a number of variations of the association rule problem which have been proposed in the literature and their practical applications. Some inherent weaknesses of the large itemset method for association rule generation have been explored. We also discuss some other formulations of associations which can be viable alternatives to the traditional association rule generation method. 1 Introduction Association rules find the relationships between the different items in a database of sales transactions. Such rules track the buying patterns in consumer behavior eg. finding how the presence of one item in the transaction affects the presence of another and so forth. The problem of association rule generation has recently gained considerable prominence in ...
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.
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Mining sequential patterns
5,115 Citations2002R. K. Agrawal, Ramakrishnan Srikant
Three algorithms are presented to solve the problem of mining sequential patterns over databases of customer transactions, and empirically evaluating their performance using synthetic data shows that two of them have comparable performance.
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.
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.
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.
An effective hash-based algorithm for mining association rules
1,412 Citations1995Jong Soo Park, Ming-Syan Chen⋆ +1 more
The number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck, and allows us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly.
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.
Sampling Large Databases for Association Rules
1,079 Citations1996Hannu Toivonen
New algorithms that reduce the database activity considerably by picking a Random sample, to find using this sample all association rules that probably hold in the whole database, and then to verify the results with the rest of the database.
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.
Knowledge Discovery and Data MiningEfficient algorithms for discovering association rules
630 Citations1994Heikki Mannila, Hannu Toivonen +1 more
An improved algorithm for the problem of mining association rules from large collections of data based on careful combinatorial analysis of the information obtained in previous passes is given, which makes it possible to eliminate unnecessary candidate rules.
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.
Cyclic association rules
404 Citations2002B. Ozden, Sridhar Ramaswamy +1 more
This work devise a new technique called cycle pruning, which reduces the amount of time needed to find cyclic association rules by studying the interaction between association rules and time, and presents two new algorithms for discovering such rules.
Clustering association rules
376 Citations2002Brian Lent, A. Swami +1 more
The authors present a geometric-based algorithm, BitOp, for performing the clustering, embedded within an association rule clustering system, ARCS, and measure the quality of the segmentation generated by ARCS using the minimum description length (MDL) principle of encoding the clusters on several databases.
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.
Scalable parallel data mining for association rules
264 Citations1997Eui-Hong Han, George Karypis +1 more
The experimental results on a Cray T3D parallel computer show that the Hybrid Distribution algorithm scales linearly and exploits the aggregate memory better and can generate more association rules with a single scan of database per pass.
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.
Parallel data mining for association rules on shared-memory multi-processors
130 Citations1996Mohammed J. Zaki, Mitsunori Ogihara +2 more
This paper presents parallel algorithms for data mining of association rules, and studies the degree of parallelism, synchronization, and data locality issues on the SGI Power Challenge shared-memory multi-processor.
Online generation of association rules
124 Citations2002Charų C. Aggarwal, Philip S. Yu
This work investigates the problem of online mining of association rules in a large database consisting of sales transactions and shows how to preprocess the data effectively in order to make it suitable for repeated online queries.
Mining optimized association rules with categorical and numeric attributes
82 Citations2002R. Rastogi, Kyuseok Shim
The generalized association rules enable us to extract more useful information about seasonal and local patterns involving multiple attributes and present effective techniques for pruning the search space when computing optimized association rules for both categorical and numeric attributes.
Mining association rules: anti-skew algorithms
82 Citations2002Jun-Lin Lin, Margaret H. Dunham
This work proposes several techniques which overcome the problem of data skew in the basket data, and employs prior knowledge collected during the mining process and/or via sampling, to further reduce the number of candidate itemsets and identify false candidate itemset at an earlier stage.
A localized algorithm for parallel association mining
77 Citations1997Mohammed J. Zaki, Srinivasan Parthasarathy +1 more
This paper describes a new parallel association mining algorithm that uses simple intersection operations to compute frequent itemsets and doesn’t have to maintain or search complex hash structures.