apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

2017/3/4 19:20:45

(哈尔滨华德学院计算机系 黑龙江哈尔滨 150025)

摘要:在关联规则理论的基础上,通过对现有算法的效率分析,在原有Apriori关联规则挖掘算法的基础上,从减少事务数据库中扫描记录量入手,提出一个改进的快速关联规则挖掘算法Fast_Apriori。利用候选项集和频繁项集中的结果对数据库中的记录进行筛选,对不包含候选项集中任何项集的记录和不包含在候选项集中的事物记录直接删除,减少扫描的记录数,提高整个算法的效率。

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

关键词:关联规则 Apriori算法 候选项集

频繁项集中图分类号:TP311.13文献标识码:A文章编号:1007-9416(2014)04-0133-02

在关联规则的各种挖掘算法研究中,主要集中在产生频繁项集的这一挖掘步骤。在众多算法中,Apriori算法最为著名,它是

Agrawal等人在1994年提出的,该算法首次将关联规则挖掘理论运

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

用在现实应用系统中。Apriori算法使用了一种逐层迭代的宽度优先搜索策略,由满足一定频度的项集来构造可能是下一个满足频度的项集的候选项集,根据设定的最小支持度计数筛选出频繁项集。

Apriori算法基本思想就是发现频繁项集,然后找出频繁项集中的关联性更强的规则。找到频繁项集的方法是先找出所有可能是频繁项集的候选项集。最简单的方法是穷举法,把所有的项集都作为候选项集,然后对它在事务数据库中出现的次数计数,计数满足设定的支持度的阈值时,则为频繁项集。但是穷举法开销较大,通过观察,发现了如下性质。

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

Apriori性质:一个频繁项集的任一子集也一定是频繁项集[1]。根据Apriori性质,如果一个项集是非频繁的,则它的超集也是非频繁的,将不作为候选项集。Apriori算法采用逐层迭代的搜索方法,由频繁k-项集来构造可能是频繁的(k 1)-项集的候选项集。在算法实现过程中还需要进一步明确两个问题:第一个是如何计算每个项集的频率,并验证其是否频繁;第二个是如何由Lk产生Ck 1。第一个问题实现方式比较简单。对于给定的候选项集Ck,可以通过对数据库的一次扫描来计算出其中每个候选项集的频率。通常在内存中为每一个候选项集设一个计数器,扫描结束时计算器的值记为候选项集的频度。第二个问题采用先连接后验证的方法解决。主要包含两个步骤:自连接和消减。自连接将大小为k的频繁项集联合成大小为k 1的项集,而消减则是进一步验证联合所生成的项集是否为潜在候选项集。

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

Apriori算法使用支持度减少了候选项集的数量,使得算法的时间和空间复杂度较小,并可以依据Apriori性质,直接删除不相关的项集,这是其好的方面。但是该算法仍需要大量的重复扫描事务数据库,对大量的候选项集进行支持度计数,当数据库数据量大部分存储在外部存储器上时,大规模数据的I/O处理操作使得算法的效率受到很大的影响。

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

Apriori算法的主要缺点在于,每迭代一次就要读一次数据库,对于一个有n个项的数据集来说,最不好的情况需要读取n次数据库。为了提高算法的效率,在Apriori算法基础上,人们相继提出了一些改进方法,从不同角度对Apriori算法进行了优化设计。

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

Apriori算法通过在内存中为每一个候选项集设置一个计数器来计算它的频度。当候选项集很多时将占据大量内存,导致内存有可能不够用,因此,需要尽可能减少候选项集的数量。Apriori算法在构造Ck 1时利用Lk进行消减,这样已经减少了一部分候选项集

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究

作者简介:翟霞,女,1980年6月生人,现任哈尔滨华德学院计算机应用技术系软件教研室教师,讲师,主要研究方向为数据仓库与数据挖掘、 决策支持系统分析与设计。

apriori算法与穷举法的区别 关联规则中Apriori算法的创新研究