基于单向增长链表的关联规则挖掘算法研究

董 辉 (亳州职业技术学院信息工程系，安徽 亳州 236800)

基于单向增长链表的关联规则挖掘算法研究

董 辉 (亳州职业技术学院信息工程系，安徽 亳州 236800)

分析研究关联规则挖掘经典算法Apriori和FP-Growth算法，发现其不足之处在于构建和遍历各自数据结构的时间长、内存消耗巨大，降低了算法在时间和空间方面的效率。针对2种算法的缺陷，提出了LK-Growth算法，该算法不再构建FP-Tree，而是构建单向线性链表组结构，能有效地缩短发现频繁模式的时间和节省内存空间开支。研究结果表明，LK-Growth算法的实用性强且挖掘效率更高。

数据挖掘；关联规则；线性增长链表；LK-Growth算法

关联规则挖掘是数据挖掘众多知识类型中一种典型代表，也是数据挖掘中最活跃的研究领域之一，其首要任务就是发现频繁项目集。长期以来，人们对关联规则频繁项目集的挖掘主要采用Apriori算法和FP-Growth算法或者它们的有关改进算法。但是，无论是Apriori算法还是FP-Growth算法，都要多次扫描事务数据库，I/O负载大，导致算法的时间开销增大；在空间需求上，Apriori算法要产生大量的候选频繁项目集、FP-Growth算法构造结构复杂的FP-Tree树，对内存开销要求都很高[1]。针对上述情况，笔者提出基于单项线性链表的关联规则挖掘优化算法，该算法构建多个单向链表结构做成链表组，通过该结构的遍历发现所有的频繁模式，在挖掘效率上比Apriori和FP-Growth算法都要高。

1 优化算法设计

1.1优化算法的思路

从对关联规则挖掘的2种经典算法的分析可知，要想提高挖掘效率，可从2方面考虑[2]：第1方面是优化重构算法操作对象的数据结构；……