A Fast Algorithm for Constructing FP_Tree

Recently, most of the studies on mining frequent patterns focus on improving the efficiency of frequent itemtsets generations, but the I/O cost of database scanning has been a bottle-neck problem in data mining. Many algorithms proposed recently are based on apriori and FP tree, and the FP growth algorithm based on FP tree is more efficient than Apriori because the candidates are not generated. But the construction of FP tree may spend much time. Therefore, the goal of our research is to propose a fast algorithm. In this paper, Level FP_tree that is constructed level by level (abbreviate LFP tree) is proposed. The algorithm contains two main parts. The first is to scan the database only once for generating equivalence classes of each item. The second is to delete the non-frequent items and rewrite the equivalence classes of the frequent items, and then construct the LFP tree. Experimental results have proved that LFP tree is more efficient and scalable than FP tree.