戴伟敏

(阳光学院 信息工程学院，福建 福州 350003 )

随着大数据时代的到来，关联规则挖掘是数据挖掘中重要的研究课题.频繁项集是数据挖掘中重要的概念.挖掘频繁项集在关联规则挖掘、序列模式挖掘、相关性挖掘等方面起到关键作用.其中，Apriori算法和频繁模式增长(FP-Growth)算法是挖掘频繁项集最常用的算法.Apriori算法采用逐层搜索的迭代策略[1]，主要弊端是，需多趟扫描数据库，并在迭代过程中产生大量的候选项集，耗费大量的I/O时间，且当数据量稍大时，该算法的执行效率降低.在此基础上，Han等提出基于FP-tree进行频繁模式挖掘的FP-Growth算法[2].与Apriori算法相比，FP-Growth算法无需生成候选项集，并且只需扫描数据库2次，即可生成频繁项集，大大提高了频繁项集的效率.但该算法也存在以下问题：①如果事务数据库的数据达到海量级别，FP-tree算法把所有事务数据中的频繁项都压缩至内存中的频繁模式树，树的高度或宽度将达到内存无法接受的规模，可能导致过程失败.②在挖掘频繁模式过程中，每次递归计算都生成一棵FP-tree，每次遍历时都会产生条件频繁模式树，并消耗大量时间和存储空间.对于大规模的数据集时，传统的Apriori算法和FP-Growth算法都是基于串行计算，其计算时间和空间复杂度较高.Hadoop平台是适合大数据的分布式存储和计算的平台[3]，有2个核心组件,分别为分布式存储系统(HDFS)和分布式计算框架(MapReduce):HDFS为分布式计算存储提供底层支持，可实现超大文件的容错和存储;MapReduce是一种分布式编……