Apriori算法研究与应用

侯博宇

【摘要】Apriori算法是数据挖掘中关联规则中一种算法，其应用比较广泛，本论文主要介绍Apriori算法的基本思想、操作主要步骤、算法的描述、改进的Apriori算法及其的具体应用。

【关键词】Apriori算法关联研究与应用

Apriori算法是一种挖掘关联规则的频繁项集算法，其算法应用比较广泛，尤其在商业领域。关联规则的一个经典的例子就是在超市对顾客购买物品的分析。通过顾客购买各种商品总结发现物品与物品之间的关系，分析顾客在购买过程中的习惯与心理。什么样的商品被顾客频繁地同时购买，这样就可以有助于商家制定营销策略。关联规则的计算依赖于发现相关数据中频繁出现的数据项，寻找数据子集间的关联关系或者一些数据与其他数据之间的派生关系。

一、Apriori算法的基本思想

1994年，Agrawal等提出了Apriori算法用于发现数据库中的频繁项集，主要使用逐层搜索的迭代算法，通过扫描数据库得出频繁项集，一般来说，约定第n次扫描得频繁k-项集，记为Lk，首先对事务数据库进行第一次扫描，找出候选频繁1-项集，记为L1，然后利用L1来产生候选项集C2，对C2中的项进行挖掘出L2，即频繁2-项集，一直重复循环，直到无法发现更多的频繁k-项集为止。Apriori算法每挖掘一层Lk就需要对整个数据库进行扫描。如果在求解过程中某次计算Lk为空时，那么整个算法的求解过程自然结束。

二、Apriori算法的主要步骤

1.对所有数据进行第一次扫描，生成候选1-项集合C1，计算项集的支持数，得到频繁1-项集L1。

2.由Apriori-gen（L1）函数中的连接和剪枝两步生成候选2-项集C2，然后进行第二次扫描数据库，计算项集的支持数，得到频繁2-项集L2。

3.按以上重复，LK进行自连接，生成候选K一项集CK，删除CK中所有的非频繁子集,生成K一频繁项集LK。

4.重复3直到候选项集为空，不再产生频繁项集，算法终止。

三、Apriori算法描述

Apriori具体的算法如下所示：

该算法的第一次遍历计算第1个项集的支持度，以确定频繁1-项集。然后的第k次遍历包括两个阶段。

首先，除第1次扫描为单元素项目集构成的，使用Apriori-gen函数产生在第（k-1）次遍历中找到频繁项集Lk-1和候选项集Ck。继续扫描整个数据库，计算Ck中候选的支持度。并且用函数subset来帮助寻找己成为候选项集的子集，同时记录每个候选项集的支持频度，连接满足最小支持度的候选集，最终得到频繁集L。

四、改进Apriori算法

通過对算法的分析，我们能够得出结论，Apriori算法存在着两个弊端，一是每次找到频繁项集和候选项集时都要扫描数据库。二是事务数据库D事务量较大时，产生的频繁项集和候选项集数量也会很庞大。为了提高Apriori算法的效率，当前Apriori算法的改进有基于散列（Hash）的方法、AprioriTid 算法、基于数据分割（Partition）的方法、基于采样（Sampling）的方法以及事务压缩技术等，下面介绍几种改进算法，并在此基础上得到自己的改进算法。

经典 Apriori 算法对候选集进行整理，主要是对其大小进行了压缩，但是Ck的生成过程中还是需要对整个事务数据库进行k 次扫描。所以，在海量的数据库中，经典 Apriori 算法的效率就会大大降低，占用系统的开销也很大。AprioriTid 算法在候选频繁项目集 Ck 的生成过程中，扫描事务时删除其中不需要的，进行压缩和整理事务数据库，这样扫描的效率得到了提高，占用系统的开销也很小。扫描第一次数据库后，候选集将不再使用事务数据库D计算支持度，从第二步开始循环处理生成Tk，直到再没有频繁项集。生成集合Tk的每个成员形式为（TID，{Xk}），该集合与数据库中事务相关，TID是事务标识，其中每个XK都是一个潜在的频繁k-项目集。

参考文献

[1]刘晓霞. 数据挖掘技术在高校教学管理系统中的应用研究. 中国海洋大学硕士论文，2010，8~16

[2]吴青，傅秀芬. 水平分布数据库的正负关联规则挖掘. 计算机技术与发展，2011，（6）：113~117