洪 炎，张 磊，严加琪

（安徽理工大学电气与信息工程学院，安徽淮南 232001）

关联规则学习（associate rule learning）是指从一定数据或其他信息载体中挖掘项目及对象之间的相关性，其结果可以揭示数据中隐藏的关联模式。通常关联规则挖掘过程主要包含两个阶段：第一阶段必须从资料集合中找出所有的高频项目组，第二阶段在这些高频项目组中产生关联规则[1]。

1994年Agrawal等提出了Apriori算法[2]，采用先连接后剪枝的方法处理选出的候选集来获取频繁项集，该方法需要两次扫描全局事务数据库而生成大量候选集。为了克服Apriori算法的局限性，2000年Han等提出了基于树型的频繁模式增长（FP-Growth）算法[3]，将提供频繁项集的数据库压缩到一棵频繁模式树中，占用了更大内存。以上方法均适用于处理静态数据。为处理动态数据的挖掘问题，Leung等提出了基于自然序树CAN-tree结构构建算法[4]，该算法克服了FP-tree构建算法占用内存大的不足，但在处理大数据集时的挖掘效率却会降低。

CAN-tree 利用树型存储了所有数据，可以在改变数据量或最小支持度下多次挖掘。Sadat 等[5]在2015年将CAN-tree算法和FP-Growth算法相比，发现在最小支持度较高时，CAN-tree算法的效率更好，但在最小支持度较低时，CAN-tree算法效率低于FP-Growth算法。2008年邹力鹍等[6]提出用子父节点指针替代原父子节点指针，可快速生成条件模式树。2014年陈刚等[7]提出一种基于CAN-tree的快速构造算法，通过增加基于hash表的辅助存储结构、减少项目的查找时间来提高算法效率。Roul等[8]在2014年提出了生成和归并树。但是以上方法均未改变CAN-tree存储规模，导致不同数据量对算法的效率影响过大。……