Association mining
ACM Computing SurveysPublished 25 July 2006
Aaron Ceglar, John F. Roddick
Citations322
SJR quartileQ1
SJR score5.80
SNIP11.03
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 association mining fundamentals is presented, detailing the evolution of associationmining algorithms from the seminal to the state-of-the-art, that is, itemset identification, rule generation, and their generic optimizations.
Abstract
The task of finding correlations between items in a dataset, association mining, has received considerable attention over the last decade. This article presents a survey of association mining fundamentals, detailing the evolution of association mining algorithms from the seminal to the state-of-the-art. This survey focuses on the fundamental principles of association mining, that is, itemset identification, rule generation, and their generic optimizations.
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
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.
Machine LearningSPADE: An Efficient Algorithm for Mining Frequent Sequences
1,802 Citations2001Mohammed J. Zaki
SPADE is a new algorithm for fast discovery of Sequential Patterns that utilizes combinatorial properties to decompose the original problem into smaller sub-problems, that can be independently solved in main-memory using efficient lattice search techniques, and using simple join operations.
IEEE Transactions on Knowledge and Data EngineeringScalable algorithms for association mining
1,717 Citations2000Mohammed J. Zaki
Efficient algorithms for the discovery of frequent itemsets which forms the compute intensive phase of the association mining task are presented and the effect of using different database layout schemes combined with the proposed decomposition and traverse techniques are presented.
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.
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.
Journal of Computational and Applied MathematicsDepartment of Computer Science
1,211 Citations1993Dr. P. Subashini, Ms. M. Krishnaveni
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.
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.
ACM SIGKDD Explorations NewsletterAlgorithms for association rule mining — a general survey and comparison
960 Citations2000Jochen Hipp, Ulrich Güntzer +1 more
The fundamentals of asso iation rule mining are explained and a general framework is derived and it turns out that the runtime behavior of the algorithms is more similar as to be expe ted.
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.
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.
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.
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.
ACM SIGMOD RecordDynamic itemset counting and implication rules for market basket data
611 Citations1997Sergey Brin, Rajeev Motwani +2 more
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.
CLOSET+
582 Citations2003Jianyong Wang, Jiawei Han +1 more
Journal of Parallel and Distributed ComputingA Tree Projection Algorithm for Generation of Frequent Item Sets
506 Citations2001Ramesh C. Agarwal, Charų C. Aggarwal +1 more
This paper provides an implementation of the tree projection method which is up to one order of magnitude faster than other recent techniques in the literature and has a well-structured data access pattern which provides data locality and reuse of data for multiple levels of the cache.
IEEE ConcurrencyParallel and distributed association mining: a survey
476 Citations1999Mohammed J. Zaki
The author surveys the state of the art in parallel and distributed association-rule-mining algorithms and uncovers the field's challenges and open research problems.
Efficiently Using Prefix-trees in Mining Frequent Itemsets.
450 Citations2003Gösta Grahne, Jianfei Zhu
A novel array-based technique is presented that greatly reduces the need to traverse FP-trees, thus obtaining significantly improved performance for FPtree based algorithms, and works especially well for sparse datasets.
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.
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.
Efficiently mining maximal frequent itemsets
391 Citations2002Karam Gouda, Mohammed J. Zaki
GenMax is a backtracking search based algorithm for mining maximal frequent itemsets that uses a novel technique called progressive focusing to perform maximality checking, and diffset propagation to perform fast frequency computation.
Data Mining and Knowledge DiscoveryMining Non-Redundant Association Rules
390 Citations2004Mohammed J. Zaki
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.
On subjective measures of interestingness in knowledge discovery
357 Citations1995Avi Silberschatz, Alexander Tuzhilin
The purpose of this paper is to lay the groundwork for a comprehensive study of subjective measures of interestingness and classify these measures into actionable and unexpected, and examine the relationship between them.
HAL (Le Centre pour la Communication Scientifique Directe)Proceedings of the 19th International Conference on Extending Database Technology, EDBT
337 Citations2016Evaggelia Pitoura, Sofian Maabout +5 more
ScholarlyCommons (University of Pennsylvania)Search through systematic set enumeration
334 Citations1992Ron Rymon
The Set-Enumerations (SE)tree is presented as a vehicle for representing sets and/or enumerating them in a best-first fashion and its usefulness as the basis for a unifying search-based framework for domains where minimal (maximal) elements of a power set are targeted.
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.
Mining frequent itemsets with convertible constraints
324 Citations2002Jian Pei, Jiawei Han +1 more
A notion of convertible constraints is developed and systematically analyzed, classify, and characterize this class and techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining are developed.
Depth first generation of long patterns
322 Citations2000Ramesh C. Agarwal, Charų C. Aggarwal +1 more
An algorithm for mining long patterns in databases by using depth first search on a lexicographic tree of itemsets achieves more than one order of magnitude speedup over the recently proposed MaxMiner algorithm.
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.
ACM SIGKDD Explorations NewsletterMining frequent patterns by pattern-growth
275 Citations2000Jiawei Han, Jian Pei
It is shown that frequent pattern growth is efficient at mining large databases and its further development may lead to scalable mining of many other kinds of patterns as well.
ACM SIGMOD RecordTurbo-charging vertical mining of large databases
254 Citations2000Pradeep Shenoy, Jayant R. Haritsa +4 more
Data Mining and Knowledge DiscoveryFree-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries
253 Citations2003Jean‐François Boulicaut, Artur Bykowski +1 more
The experiments show that the extraction of frequent free-sets can be efficiently extracted using pruning strategies developed for frequent itemset discovery, and that they can be used to approximate the support of any frequent item set.
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.
Knowledge-Based SystemsOn rule interestingness measures
236 Citations1999Alex A. Freitas
This article aims at drawing attention to several factors related to rule interestingness that have been somewhat neglected in the literature, and introducing a new criterion to measure attribute surprisingness, as a factor influencing the interestingness of discovered rules.
Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports
233 Citations2001Phillip B. Gibbons
This work presents an approach, called distinct sampling, that collects a specially tailored sample over the distinct values in the input, in a single scan of the data, and shows how it can provide fast, highlyaccurate approximate answers for “report” queries in high-volume, session-based event recording environments, such as IP networks, customer service call centers, etc.
A FAST APRIORI IMPLEMENTATION
227 Citations2003Ferenc Bodon
A practical implementation of the interferometer proposed here has the potential to provide translational and rotational test-mass tracking with state-of-the-art sensitivity and is suitable for employment in torsion pendulum setups.
Mining frequent item sets by opportunistic projection
189 Citations2002Junqiang Liu, Yunhe Pan +2 more
This paper presents a novel algorithm Opportune Project for mining complete set of frequent item sets by projecting databases to grow a frequent item set tree, and proposes novel methods to build tree-based pseudo projections and array-based unfiltered projections for projected transaction subsets.
Overcoming limitations of sampling for aggregation queries
157 Citations2002Surajit Chaudhuri, Gautam Das +3 more
It is demonstrated that a combination of outlier indexing with weighted sampling can be used to answer aggregation queries with a significantly reduced approximation error compared to either uniform sampling or weighted sampling alone.
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 scienceTop Down FP-Growth for Association Rule Mining
136 Citations2002Ke Wang, Tang Liu +2 more
An efficient algorithm, called TD-FP-Growth (the shorthand for Top-Down FP-G growth), to mine frequent patterns by applying two new pruning strategies: one is topush multiple minimum supports and the other is to push the minimum confidence.
Turbo-charging vertical mining of large databases
125 Citations2000Pradeep Shenoy, Jayant R. Haritsa +4 more
This work presents a new vertical mining algorithm called VIPER, which is general-purpose, making no special requirements of the underlying database, and analyzes the performance of VIPER for a range of synthetic database workloads.
A condensed representation to find frequent patterns
122 Citations2001Artur Bykowski, Christophe Rigotti
This paper shows that a condensed representation of the frequent patterns called disjunction-free sets can be used to regenerate all frequent patterns and their exact frequencies, and this regeneration can be performed without any access to the original data.
University Libraries (University of Maryland)Fast sequential and parallel algorithms for association rule mining: a comparison
121 Citations1995Andreas Mueller
The performance results show that, while both algorithms parallelize easily and obtain good speedup and scale-up results, the parallel SEAR version performs better than parallel SPEAR, despite the fact that it uses more communication.
Lecture notes in computer scienceEvaluation of Interestingness Measures for Ranking Discovered Knowledge
113 Citations2001Robert J. Hilderman, Howard J. Hamilton
This work theoretically and empirically evaluate thirteen diversity measures used as heuristic measures of interestingness for ranking summaries generated from databases, and describes five principles that any measure must satisfy to be considered useful forranking summaries.
A new two-phase sampling based algorithm for discovering association rules
112 Citations2002Bin Chen, Peter J. Haas +1 more
This paper introduces FAST, a novel two-phase sampling-based algorithm for discovering association rules in large databases that was able to achieve 90--95% accuracy using a final sample having a size of only 15--33% of that of a comparable random sample.
Lecture notes in computer scienceEnhancing the Apriori Algorithm for Frequent Set Counting
111 Citations2001Raffaele Perego, Salvatore Orlando +1 more
DCP, a new algorithm for solving the Frequent Set Counting problem, which enhances Apriori by using an innovative method for storing candidate set of items and counting their support, and the exploitation of effective pruning techniques which significantly reduce the size of the dataset as execution progresses.
The power of sampling in knowledge discovery
105 Citations1994Jyrki Kivinen, Heikki Mannila
Upper and lower bounds for the sample sizes required for having a high probability that all the sentences with error at least &egr; can be detected as false by considering the sample are given.
Interestingness via what is not interesting
100 Citations1999Sigal Sahar
This work presents a simple and short process of eliminating a substantial portion of uninteresting association rules in a list outputted by a data-mining algorithm, and presents representative results of executions of the algorithm over three real databases.
Lecture notes in computer scienceInterestingness of discovered association rules in terms of neighborhood-based unexpectedness
97 Citations1998Guozhu Dong, Jinyan Li
One of the central problems in knowledge discovery is the development of good measures of interestingness of discovered patterns, which means a user needs to manually examine only the more interesting rules, instead of each of a large number of mined rules.
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.
Lecture notes in computer scienceConcise Representations of Association Rules
81 Citations2002Marzena Kryszkiewicz
This paper overviews the following lossless representations: representative rules, Duquenne-Guigues basis, proper basis, Luxenburger basis, structural basis, minimal non-redundant rules, generic basis, informative basis and its transitive reduction and examines whether it is sound and informative.
Mining Frequent Itemsets using Patricia Tries.
78 Citations2003Andrea Pietracaprina, Dario Zandolin
A depth-first algorithm that discovers all frequent itemsets in a dataset, for a given support threshold, is presented and several experimental results are reported, which assess the effectiveness of the implementation and show the better performance attained by PatriciaMine with respect to other prominent algorithms.
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.
kDCI: a Multi-Strategy Algorithm for Mining Frequent Sets.
71 Citations2003Salvatore Orlando, Claudio Lucchese +3 more
The implementation of kDCI is presented, an enhancement of DCI, a scalable algorithm for discovering frequent sets in large databases, based on a novel counting inference strategy, inspired by previously known results by Basted et al.
An efficient approach to discovering knowledge from large databases
68 Citations2002Show-Jane Yen, A.L.P. Chen
Graph based algorithms construct an association graph to indicate the associations between items and then traverse the graph to generate large itemsets and large sequences, respectively are presented.
Knowledge-Based SystemsAlgorithms for computing association rules using a partial-support tree
64 Citations2000Graham Goulbourne, Frans Coenen +1 more
This method uses a single pass of the database to perform a partial computation of support for all sets encountered in the database, storing this in the form of a set enumeration tree.
Data organization and access for efficient data mining
62 Citations1999Brian Dunkel, Nandit Soparkar
Generating an informative cover for association rules
51 Citations2003Laurentiu Cristofor, Dan A. Simovici
The notion of association rules cover is defined as a minimal set of rules that are non-redundant with respect to this new rule of inference that is comparable to the classic Apriori algorithm for generating rules.
Lecture notes in computer scienceHeuristic Measures of Interestingness
44 Citations1999Robert J. Hilderman, Howard J. Hamilton
This paper presents and empirically compares sixteen heuristic measures that evaluate the structure of a summary to assign a single real-valued index that represents its interestingness relative to other summaries generated from the same database.
Lecture notes in computer scienceMining Association Rules: Deriving a Superior Algorithm by Analyzing Today’s Approaches
37 Citations2000Jochen Hipp, Ulrich Güntzer +1 more
This paper identifies the fundamental strategies of association rule mining and presents a general framework that is independent of any particular approach and its implementation, and achieves remarkably better runtimes than the previous algorithms.
Australasian Database ConferenceCT-ITL: efficient frequent item set mining using a compressed prefix tree with pattern growth
34 Citations2003Yudho Giri Sucahyo, Raj P. Gopalan
The performance study shows that the new algorithm significantly reduces the processing time for mining complete sets of frequent item sets from dense data sets that contain relatively long patterns.
Basic Association Rules
33 Citations2004Guichong Li, Howard J. Hamilton
The concept of a restricted conditional probability distribution is used to explain an association rule, and a new type of association rules, called basic associationrules, is defined using the GenBR algorithm to generate the set of classes of basic association rules.
Mining Non-Derivable Association Rules
30 Citations2005Bart Goethals, Juho Muhonen +1 more
This work introduces efficient methods for deriving tight bounds for confidences of association rules, given their subrules, if the lower and upper bounds of a rule coincide, and gives absolute bounds for the confidence instead of relying on point estimates or heuristics.
Lecture notes in computer scienceFast Discovery of Representative Association Rules
29 Citations1998Marzena Kryszkiewicz
In this paper, properties of representative association rules are investigated and a new efficient algorithm computing such rules are offered and offered.
BDABitmap based algorithms for mining association rules.
27 Citations1998Georges Gardarin, Philippe Pucheral +1 more
A simple approach to identifying barriers to change and tailor an intervention to improve pharmacological management of hypertension and hypercholesterolaemia appears to have been adequate and efficient.
ACM SIGKDD Explorations NewsletterWhat's interesting about Cricket?
26 Citations2001John F. Roddick, Sally Rice
The lessons that may be learned from analysing the (largely manual) selection of interesting statistics for cricket (or any other data rich sport) by experts are investigated and the effect of thresholds on the interestingness of rules describing events in the sporting arena is discussed.
arXiv (Cornell University)Mining All Non-Derivable Frequent Itemsets
24 Citations2002Toon Calders, Bart Goethals
Data Archiving and Networked Services (DANS)Apriori, A Depth First Implementation.
22 Citations2003Walter A. Kosters, Wim Pijls
The algorithm that builds a trie in memory that contains all frequent itemsets, i.e., all sets that are contained in at least minsup transactions from the original database is described.
ITL-MINE: Mining Frequent Itemsets More Efficiently.
11 Citations2002Raj P. Gopalan, Yudho Giri Sucahyo
A new data structure is presented and a more efficient algorithm for mining frequent itemsets from typical data sets is presented by scanning the database just once and by reducing item traversals within transactions.
RePub (Erasmus University, Rotterdam)Mining frequent intemsets in memory-resident databases
9 Citations2000Wim Pijls, Jan C. Bioch
A new algorithm, based upon depth-first search in a set-enumeration tree, is proposed, which turns out to be superior to breadth- first search for memory-resident databases.
Towards data mining benchmarking
4 Citations2000Jian Pei, Runying Mao +2 more
This work has constructed an open test bed for performance study of a set of recently developed, popularly used methods for mining frequent patterns in transaction databases and mining sequential patterns in sequence databases, with different data characteristics.
…