Mining frequent patterns without candidate generation
By Jiawei Han, Jian Pei, Yiwen Yin. 2000
7,980 citations recorded by the source corpus.
Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist prolific patterns and/or long patterns. In this study, we propose a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth. Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a highly condensed, much smaller data structure, which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts a pattern fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns, and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported new frequent pattern mining methods.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Charu C. Aggarwal
- Philip S. Yu
- Cynthia Rudin
- Jiawei Han
- Francisco Herrera
- Tong Wang
- George Karypis
- Mohammed J. Zaki
In Computational Theory and Mathematics
- Jiawei Han
- Cynthia Rudin
- George Karypis
- Mohammed J. Zaki
- Tong Wang
- Xifeng Yan
- Hong Cheng
- Jianyong Wang
In Information Systems
- Jiawei Han
- Cynthia Rudin
- Mohammed J. Zaki
- George Karypis
- Philip S. Yu
- Charu C. Aggarwal
- Xifeng Yan
- Michihiro Kuramochi
Citations in the corpus
- An optimization approach to learning falling rule lists (2017, methodology): “Besides the FPgrowth algorithm, there is a vast literature on rule mining algorithms (e.g. Agrawal and Srikant, 1994; Han et al., 2000; Landwehr et al., 2005), and any of these can be used to produce antecedents for our algorithms.”
- Learning Optimized Or's of And's (2015, methodology): “There are many frequently used pattern mining methods such as FP-growth (Han, Pei, and Yin, 2000), Apriori (Agrawal, Srikant, and others, 1994), Eclat (Zaki et al., 1997), etc.”
- CPAR: Classification based on Predictive Association Rules (2003, methodology): “It uses association rule mining algorithm, such as Apriori [1] or FPgrowth [5], to generate the complete set of association rules.”
- Big data for cyber physical systems in industry 4.0: a survey (2019, methodology): “Other classical methods in this type include FP-Tree (Han, Pei, and Yin 2000), which uses an extended pre fi x-tree structure for storing compressed information, and ECLAT (Zaki 2000) which store transaction information in a vertical data layout for fast support counting.”
- The role mining problem: finding a minimal descriptive set of roles (2007, background): “The key idea behind the algorithm is that all large tiles containing a permission i ∈ PRMS, but not containing any permission lower than i (according to the canonical order) can be found in the so-called i-conditional database [7].”
- Differential Privacy for Deep and Federated Learning: A Survey (2022, methodology): “…noisy dataset for frequent itemset learning; first, the algorithm takes an integer k and distinguish the top k most frequent items by running frequent itemset mining algorithm [103], after that, the algorithm builds an (cid:15) -differentially private FP-tree [104] that is released to the analyzer.”
- On the tradeoff between privacy and utility in data publishing (2009, methodology): “We use the FPtree [11] algorithm for discovering large populations.”
- Foundations and Advances in Data Mining (2005, methodology): “We presented an algorithm for extracting rules from linear formulas and extended it to the continuous domain[24].”
- MacroBase: Prioritizing Attention in Fast Data (2016, methodology): “To produce explanations, MacroBase runs FPGrowth on the prefix tree.”
- An overview on subgroup discovery: foundations and applications (2011, methodology): “– SD-Map [10] is an exhaustive subgroup discovery algorithm that uses the well-known FP-growth method [56] for mining association rules with adaptations for the subgroup discovery task.”
- Interpretable Companions for Black-Box Models (2020, methodology): “At the initilization step, we first apply FPGrowth [20] to the data set D, and find both the frequent positive rules and the frequent negative rules with the minimum support bounded by γ, and construct the set of rules Γ.”
- An implementation of the FP-growth algorithm (2005, methodology): “One of the currently fastest and most popular algorithms for frequent item set mining is the FP-growth algorithm [8].”
- Effective Pattern Discovery for Text Mining (2012, methodology): “A variety of efficient algorithms such as Apriori-like algorithms [2], [31], [49], PrefixSpan [32], [53], FP-tree [10], [11], SPADE [56], SLPMiner [42], and GST [12] have been proposed.”
- A Machine Learning Framework to Identify Students at Risk of Adverse Academic Outcomes (2015, methodology): “Identify all frequent patterns in the data using the FP-growth technique [14].”
- Free for All! Assessing User Data Exposure to Advertising Libraries on Android (2016, methodology): “Mining application co-installation patterns: Our implementation of Pluto’s CIP module uses FPGrowth [20], the state of the art frequent pattern matching (FPM) algorithm for finding association rules.”
- Constraint programming for itemset mining (2008, positive): “This example illustrates a key point: by using reified constraints, a CP system behaves very similar to other wellknown depth-first itemset miners such as Eclat [16] and FPGrowth [11].”
- A data clustering algorithm for mining patterns from event logs (2003, methodology): “Firstly, Apriori algorithm is expensive in terms of runtime [19, 20], since the candidate generation and testing involves exponential complexity.”
- Efficiently Using Prefix-trees in Mining Frequent Itemsets (2003, methodology): “In [6], the original FPgrowth method has been shown to be an efficient and scalable algorithm for mining frequent itemsets.”