基于FP-tree的快速构建算法

Fast construction algorithm based on FP-tree

数据库的访问频度是影响关联规则挖掘性能的关键因素之一。通过研究FP-tree算法,提出了一种基于FP-tree的快速构建算法,使FP-tree的构建过程仅需一次数据库扫描。该算法通过动态调整项头表中各项的顺序,同时动态修正FP-tree中项的出现顺序与项头表中各项出现顺序不一致的节点。最后,通过对项头表中非频繁项的剔除与FP-tree中对应项节点的清理,完成FP-tree的构建过程。实验结果证明了该算法的有效性。

Access frequency of database is one of the key factors to affect association rule mining performance.With the analysis of FP-tree,a fast construction algorithm based on FP-tree was proposed in this paper to scan database only one time.It dynamically adjusted not only the order of items in Item Entry Table（IET）,but also the order of nodes in FP-tree whose order was not consistent with the order of nodes in IET.Finally,it removed the un-frequent items in the IET with related nodes in FP-tree,and completed the construction of FP-tree.The experimental results validate the efficiency of the new algorithm.