关于改进的Apriori算法综述

何云峰

摘要：Apriori算法虽是关联规则中的基本算法，但其使用效率并不是太高。幸运的是经过20多年的发展，迄今已经相当成熟。除了外国学者不断改进外，中国学者对此也花费了不少代价。从apriori算法的性质，Apriori算法与其他算法的综合使用等方面，对中国学者在Apriori算法的改进研究方面进行了比较全面的总结。

关键词：Apriori算法；改进的Apriori算法；算法综述

中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2017）02-0153-01

1 引言

关联规则挖掘中最经典的Apriori算法在1993年被R.Agrawl等人于提出，该算法的目的在于从数据库中找出最大项目集从而生成关联规则。

随后，其改进算法AprioriTid和AprioriHybird被提出，AprioriTid的特点是在第一次遍历数据库之后，就改用扫描生成的候选项集，同时计算出频繁项集的支持度的思想，就不再扫描数据库了。AprioriHybird算法则是结合了Apriori和AprioriTid的各自特点，即在开始时先用Apriori扫描数据库，当生成的候选项集能够存放到内存中时，就要转成AprioriTid，这样开销就小了很多。接下来，又有人提出了DHP算法。

2 正文

我国学者研究关联规则挖掘始于2000年左右，主要思路也是跟着国外学者的想法。

从Apriori算法性质方面有学者提出了改进，这些性质主要包括：1）对于一个k维的Tk数据项集，如果Tk是k维最大项集，则在k-1维数据项集生成的集合Lk-1中包含k-1维子集的个数一定要不小于k。同时在Lk-1中的剪枝操作[1]也利用了这个性质。2）对于k维频繁项集，由其产生的所有k-1维子集都是频繁的，而且子集的个数一定等于k。根据这一性质提出改进，在产生频繁1项集L1和频繁2项集L2后，准备生成频繁3项集时，先由频繁2项集组合生成候选3项集C3，之后再把L2中每个元素顺次取出，再与C3的子集比较，是则进行计数加1的操作，重复这个步骤得到C3中个元素的计数，计数等于3的就是3项频繁集。重复这种方法就得到更多频繁集的生成。

也有不少学者从数据库扫描次数和数据库容量消减方面提出了改进。有学者曾使用通过在频繁项集Lk-1中的筛选，再在数据库中找到不满足最小支持度的元素及所包含它们的事务，从而把该（k-1）项目的事务删除，即缩小了数据库容量，同时也提高了剪枝操作的效率。在评估候选频繁项集时使用概率法和用户兴趣度，从而筛选掉一些不太感兴趣的事务，也能缩小数据库的大小。有学者在2008年使用仅2次扫描数据库的思路重组原始数据库[2]。

在转换数据库存储方式方面有很多学者也做了不少努力，在2004年有学者提出了用矩阵表示数据库的思想，用矩阵的每一行来表示每一条事务，每行中有项目的位置逐次加1，最后可得到支持度矩阵[3]。过了2年，有人提出在转为矩阵的基础上[3]，再使用自定义的矩阵的方法去完成剪枝步骤；还有使用行向量内积的方法去搜寻频繁项集。2009年有学者提出了一种较新的处理事务的方法——二元组表示法，把原始事务数据库用一个项目串和串的出现频率的二维组来替换，当然这个二元组的创建需要把数据库扫描一遍。例如这样的形式[I1I2I3，3]。如果该二元组能用链表结构来表示，则能加快一定速度[4]。既然能通过普通链表实现存储，那用十字链表方式存储数据库的事务也有学者进行了尝试。还有学者直接把数据库的存储形式进行了改变，比如原来的表示方式是用第几条事务是由哪几个元素组成的，形如“M1A，C，F”，现在则变为哪些元素被哪些事务包含了，即“BM2M4M6M7”形式。这种方法实际并没有带来太大的改进效果，应该说只是换了个花样。另外，把Hash技术、散列表技术应用于数据库的处理中也起到了良好的效果。比如在产生1_频繁项目集和2_频繁项目集时，使用hash技术或散列表技术。

从Apriori算法与其他算法的综合使用方面来看，可谓是多种多样，精彩纷呈。有在IDS日志分析中使用Apriori算法与聚类算法相结合的。也有使用Apriori算法和遗传算法相结合对数据库进行处理的。还有在云计算中使用Apriori算法[5]以及在矩阵聚类法中使用Apriori算法的。

3 结语

Apriori算法经过若干年的发展研究，出现了各种各样的改进。无论从算法本身角度去发展还是和其他算法联合使用，现今的Apriori算法已经到了一种发展到顶的味道，似乎很难再有什么大的突破。

参考文献

[1]胡吉明，鲜学丰.挖掘关联规则中Apriori算法的研究与改进[J].计算机技术与发展，2006，16（4）：99-101.

[2]郭健美，宋顺林，李世松.基于Apriori算法的改进算法[J].计算机工程与设计，2008，29（11）：2814-2815.

[3]马盈仓.挖掘关联规则中Apriori算法的改進[J].计算机应用与软件，2004，21（11）：82-83.

[4]张春生.改进的数据库一次扫描快速Apriori算法[J].计算机工程与设计，2009，30（16）：3811-3813.

[5]吴琪.基于云计算的Apriori挖掘算法[J].计算机测量与控制，2012，20（6）：1653-1655.