杨 勇, 张 磊, 曲福恒, 刘俊杰, 陈 强

(1. 长春理工大学 计算机科学技术学院, 长春 130022； 2. 长春师范大学 教育学院, 长春 130032)

关联规则挖掘技术是数据挖掘[1]领域最常用的技术之一, 其可从复杂的数据中得到不同项集之间的隐藏规律, 从而为各行业的发展提供辅助决策, 目前关联规则挖掘技术已得到广泛关注.

目前, 对关联规则增量挖掘算法的研究相对较少, 其主要分为两类： 第一类是以Apriori算法[2]为基础的基于迭代的增量算法, 如FUP(fast update algorithm)[3],FUP2[4],IUA(incremental updating algorithm)[5]等; 第二类是以FP-growth[6]为基础的基于树结构的增量算法, 如Cat-tree[7]和Can-tree[8]等, 该类算法以树结构[9]为基础, 挖掘过程不会生成候选集, 也不需要扫描数据库, 但过于依赖事物的顺序, 并且当数据集过大时, 生成的树结构太复杂, 对内存消耗较大, 不适合大数据集环境下的规则挖掘. 因此, 本文主要考虑基于迭代的关联规则增量算法. 除FUP算法外, 针对增量规则挖掘问题, 目前基于FUP算法已提出了很多改进算法, 如黄德才等[10]提出了Pruning FUP算法, 通过减少对数据库的扫描次数提高算法效率; 闫仁武等[11]提出了基于时间权值的增量更新算法, 通过对不同时期数据加权[12]以控制效率和规则的准确性； 朱晓峰等[13]提出了基于MapReduce[14]的FUP算法, 利用并行化提高了运算效率; 尹艳红[15]提出了IUTS算法, 结合FUP和IUA算法的思想, 从支持度和数据库两个角度解决了挖掘问题； 张步忠等[16]对已有的增量算法进行了详细综述； 耿志强等[17]提出了基于矩阵的关联规则增量算法(MFUP), 利用矩阵避免了数据库的重复扫描；……