新型频繁项集快速挖掘模式树的方法

Research on new mining algorithm of frequent itemset

在FP_growth算法中,FP_tree及条件FP_tree的构造和遍历占了算法绝大部分的时间,为了能减少这方面的时间,提出了一种新型快速的方法——改进的层次频繁模式树(inproved hierarchy FP_tree,IHFP_tree)。该方法采用首先对数据库扫描一遍,产生每个项的等价类;然后去掉不频繁项,对等价类进行重新改写;最后再创建FP_tree。引入层次频繁模式的概念,在挖掘过程中大大提高了算法的时空效率。与其他频繁模式挖掘的常用算法进行了时间复杂度和空间复杂度的比较,实验表明,IHFP_tree的挖掘速度比FP_tree方法要快得多。

In FP-growth algorithm, it costs most of the time in constructing and traversing the FP-tree and conditional FP-tree. In order to constructing the FP_tree efficiently, this paper proposed a new fast algorithm called inproved hierarchy FP_tree （abbreviate IHFP_tree）. The algorithm firstly scaned the database only once for generating equivalence classes of each item. Then deleted the non-frequent items and rewrote the equivalence classes of the frequent items, and then constructed the IH FP_tree.