一种基于裁剪FP-Tree 的频繁项集挖掘算法

罗 芳

(宁德师范学院 计算机系，福建 宁德 352100)

关联规则挖掘是数据挖掘技术的重要内容之一，在金融、教育、销售等行业得到了越来越广泛的应用。在Apriori 算法［1，2］被AgrawalR 等人提出以后，许多学者对其进行了改进，如FP－Growth［3］，它比Apriori 算法快一个数量级。FP－Growth 算法通过建立FP 树来挖掘数据库中频繁项集。首先扫描一次数据库，算出各项集的支持度计数，通过与用户设定的最小支持度计数相比，得出频繁1－项集，对频繁1－项集按支持度计数进行从大到小排序插入频繁项头表中;其次，再扫描一次数据库，删除数据库中非频繁1－项集的元素，构造FP 树，并挖掘出频繁k(k ＞1)－项集。FP－Growth 算法在挖掘过程中，需要产生条件FP 树，当最小支持度较小时，将产生大量的条件FP 树，占用的存储空间会非常庞大。由于FP 树和条件FP 树都需要自顶向下、自底向上两次遍历，遍历占用时间也大大增加。

针对FP－Growth 算法的不足之处，吴倩等提出了压缩FP－tree 的改进搜索算法，［4］张中平等提出了基于矩阵的频繁项集挖掘算法，［5］王利钢等提出了基于FP－tree 的项约束关联规则挖掘算法，［6］宋威等提出了基于动态裁剪频繁模式树的频繁项集并发挖掘算法，［7］郭伟等提出了基于数组的FP－tree 频繁项集挖掘算法，［8］付冬梅等提出了基于FP－tree 和约束概念格的关联规则挖掘算法及应用研究。［9］其中文献［7］裁剪FP 树的方法存在缺陷，可能会误删树中结点，导致挖掘出的频繁项集不正确。为此本文提出了一种新的基于数组的频繁模式树裁剪算法PruneFP－tree(简称F_ FP)，利用数组存储所有的2－项集的支持度计数，对FP 树中的叶子结点进行有效裁剪，减少条件FP 树的生成，减少算法的递归次数。……