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 a large number of 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 condensed, smaller data structure, FP-tree 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.

Jiawei Han

Jian Pei

Yiwen Yin

Runying Mao

Data Mining and Knowledge Discovery

数据收集、存储和分发方面的进步已经产生了对帮助数据分析的计算工具和技术的需求。数据库中的数据挖掘和知识发现 (KDD) 是一个快速发展的研究和应用领域，它建立在许多领域的技术和理论之上，包括统计学、数据库、模式识别和学习、数据可视化、不确定性建模、数据仓库和 OLAP，优化和高性能计算。

With advancements in data collection, storage, and distribution technologies, there is a growing demand for tools and techniques that assist in data analysis. Data Mining and Knowledge Discovery (KDD) is a rapidly evolving field of research and application that builds upon technologies and theories from various disciplines, including statistics, databases, pattern recognition and learning, data visualization, uncertainty modeling, data warehousing and OLAP, optimization, and high-performance computing.

随着数据收集、存储和分发技术的进步，市场对数据分析工具和技术的需求日益增长。数据挖掘与知识发现（Data Mining and Knowledge Discovery，KDD）是一个快速发展的研究与应用领域，融合了统计学、数据库、模式识别与学习、数据可视化、不确定性建模、数据仓库与OLAP、优化以及高性能计算等多个学科的技术和理论。

Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach

A novel frequent-pattern tree (FP-tree) structure is proposed, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and an efficient FP-tree-based mining method, FP-growth, is developed for mining the complete set of frequent patterns by pattern fragment growth.

Category	Quartile
计算机科学	3
计算机科学, 计算机人工智能	3
计算机科学, 计算机信息系统	3

Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
COMPUTER SCIENCE, INFORMATION SYSTEMS	2