A New Algorithm for Mining Frequent Pattern

Mining frequent pattern in transaction database,time-series databases,and many other kinds of databases have been studied popularly in data mining research.Most of the previous studies adopt Apriori-like candidate set generation-and-test approach.However,candidate set generation is very costly.Han J.proposed a novel algorithm FP-growth that could generate frequent pattern without candidate set.Based on the analysis of the algorithm FP-growth,this paper proposes a concept of equivalent FP-tree and proposes an improved algorithm,denoted as FP-growth,which is much faster in speed,and easy to realize,FP-growth adopts a modifeid structure of FP-tree and header table,and only generates a header table in each recursive operation and projects the tree to the original FP-tree,The two algorithms get the same frequent pattern set in the same transaction database,but the performance study on computer shows that the speed of the improved algorithm,FP-growth,is at least two times as fast as that of FP-growth.

A New Algorithm for Mining Frequent Pattern

Mining frequent pattern in transaction database, time-series databases, and many other kinds of databases have been studied popularly in data mining research. Most of the previous studies adopt Apriori-like candidate set generation-and-test approach. However, candidate set generation is very costly. Han J. proposed a novel algorithm FP-growth that could generate frequent pattern without candidate set. Based on the analysis of the algorithm FP-growth, this paper proposes a concept of equivalent FP-tree and proposes an improved algorithm, denoted as FP-growth*, which is much faster in speed, and easy to realize. FP-growth* adopts a modified structure of FP-tree and header table, and only generates a header table in each recursive operation and projects the tree to the original FP-tree. The two algorithms get the same frequent pattern set in the same transaction database, but the performance study on computer shows that the speed of the improved algorithm, FP-growth*, is at least two times as fast as that of FP-growth.