张心静，于嘉威，王红梅

(长春工业大学 计算机科学与工程学院，吉林 长春 130012)



基于回溯的最大频繁项集挖掘算法

张心静，于嘉威，王红梅

(长春工业大学 计算机科学与工程学院，吉林 长春 130012)

针对Apriori类算法多次扫描数据库和FP-tree类算法需要构建大量条件模式树的问题，文中提出了挖掘最大频繁项集的GBMFI算法。采用垂直格式存储事务数据库，以枚举树为基础，利用子集非频繁性质和父子节点支持度信息在搜索过程中对枚举树进行剪枝，最终得到最大频繁项集。通过实验对比，结果证明了算法的有效性，尤其适用于稀疏数据集。

数据挖掘；最大频繁项集；关联规则；回溯法；剪枝

随着大数据时代的发展，数据挖掘技术在这个领域发挥的作用变得不可小觑[1]。发现关联规则是数据挖掘工作的重点。而挖掘频繁项集又是寻找关联规则的重要步骤之一。但在通常情况下得到的频繁项集数量庞大，且彼此之间存在项重复的现象，这就导致了信息冗余的问题。由于最大频繁项集隐含了所有频繁项集的信息，大幅缩减了频繁项集的数量，因此挖掘最大频繁项集的任务应运而生。挖掘最大频繁项集的算法通常基于Apriori[2]和FP-tree[3]思想。一方面，基于Apriori改进的算法自底向上逐渐产生所有频繁项集，但在这一过程中也会因连接操作生成大量的候选项集，同时为了削减候选项集，导致算法多次扫描整个事务数据库，耗费了时间与资源。尤其是针对大数据进行处理时，产生的项集规模过大使得计算机难以对其进行存储与计算，高效得到价值密度高的数据更加困难。……