顾军华 李如婷 张亚娟* 董彦琦

1(河北工业大学人工智能与数据科学学院 天津 300401)2(河北省大数据计算重点实验室 天津 300401)

0 引 言

在当今大数据时代，如何从海量的数据中去粗存精，挖掘出隐藏的、有价值的信息，为各行各业的管理者提供决策支持具有十分重要的意义[1]。关联规则挖掘是数据挖掘中一个十分重要的研究方向，其主要任务是发现数据库中项集之间隐藏的关系，且广泛应用于商店营销、库存控制、农作物选择和生物信息学等多个领域[2]。关联规则挖掘主要包括挖掘频繁项集和发现强关联规则两部分，挖掘频繁项集是其中很重要的一步。因此许多用于挖掘频繁项集的算法被提出，这些算法主要分为两类：Apriori类算法和FP-growth类算法[3]。

Apriori算法最初是由Agrawal等[4]提出来的，该算法先通过自连接(k-1)-项集产生候选k-项集，然后根据最小支持度和Apriori先验定理对候选项集进行剪枝，从而获得频繁k-项集。Apriori算法简单且易于理解，但是面对庞大的数据时，该算法存在以下两个问题：(1) 产生大量的候选项集；(2) 需要重复多次扫描数据库，造成了巨大的I/O负载。与Apriori类算法不同，FP-growth算法只需要两次扫描数据库且没有候选项集生成，挖掘效率较Apriori算法有很大提升[5]。然而FP-growth算法在挖掘过程中需要频繁构建条件模式树(Frequent Pattern tree,FP-tree)和条件模式基，带来了巨大的时间和空间消耗。

利用FP-growth算法的思想，Deng等提出了PrePost算法[6]，该算法通过前序和后序遍历FP-tree，构建了一棵基于前序和后序编码的树(Pre-order and Post-order Code tree,PPC-tree)，从中得到1-项集的N-list，然后通过迭代连接两个项集的N-list得到新的项集，减少了时间和空间的消耗。……