一种改进的Apriori算法及在计算机一级等级考试的应用

何云峰

摘要：在介绍了传统的Apriori算法基础上，对其生成频繁2、3项集的方法进行了改进，给出了具体事例及过程，在数据库消减上也给予了一定的策略，从而减少了数据库容量和扫描次数。最后通过对计算机一级等级考试的数据进行挖掘和验证，证明了改进算法的效率优于Apriori算法；挖掘出的关联规则，对于指导教学有一定的意义。

关键词：Apriori算法 2项集支持度矩阵 计算机一级等级考试

中图分类号：TP301 文献标识码：A 文章编号：1007-9416（2016）06-0000-00

1 关联规则Apriori算法简介

关联规则挖掘（Association Rule Mining）是数据挖掘研究中的一个重要分支，用它可以发现交易数据库中项目、属性之间的内在联系。用于关联规则数据挖掘的著名算法――Apriori算法由Agramal和srikant提出[1]。它的基本思想是重复扫描数据库，根据一个频繁集的任意子集都是频繁集的原理，可以从长度为k的频繁集迭代地产生长度为 k+1 的频繁集，并在第k次扫描时产生出长度为 k的大项集Lk。而在第 k+1 次扫描时，只考虑由Lk 中的k 项集产生长度为 k+1 的候选集 Ck+1，然后再扫描数据库以验证其发生的次数。然而，如果是频繁集很长或最小支持度非常小时，用这种方法产生候选集将会有极大的消耗。如此，则需要大量次数的重复扫描数据库。

2 Apriori算法的改进

每次都要扫描数据库，是一项既费时又费力的工作。于是有学者使用以空间换时间的思路，即用生成大量项目的方法来换取仅扫描一次数据库的方法来改进基本的Apriori算法[2]。但这种方法随着项目数的巨增使得产生的项目组合可能不能放入机器内存一次处理。于是有这样一种思想，即：在Apriori 算法每次扫描数据库时，检测在每次遍历的末尾处集合Ck能适合内存时就不再使用扫描数据库的Apriori 算法而使用把集合Ck放入内存的改进的Apriori 算法。用一种方法来估计下一次遍历中Ck是否适合内存。如果这次产生的Ck可以小到放入内存，且本次遍历产生的大型候选比前次要少，那么就转换算法。有实验说明这种转入内存的Apriorii算法和传统的Apriori算法在生成频繁2、3项集所费时间最多，几乎占到该算法的3/5时间，且前者所耗时间远比Apriori多，于是本文主要对生成频繁2项集和频繁3项集部分进行相关改进，同时使用了一些方法对数据库进行消减。由于已知生成频繁2、3项集所费时间最多，所以本文在使用改进的Apriori算法生成频繁3项集后即转入内存，重新使用传统的Apriori算法，而无需再设置判断条件。

2.1改进想法

做一个上三角矩阵用来存储候选频繁2项集C2的所有元素[3]。例如有A， B， C，D ，4个项目，则C2可用图1表示。这个矩阵称为：2项集支持度矩阵，给A， B， C， D分别赋予顺序号1，2，3，4，于是使用下标（i，j）就可以把候选频繁2项集中的任何一个访问到，比如AB的坐标，使用（2，3）就可以访问到。第一边扫描数据库时就能确定C2中各项的支持度。先对矩阵清零后，把每一条交易按交易项目排序，生成所有可能的顺序2项组合。比如第一条交易项目为{A，B，C，D}，则所有的顺序2项组合为{A， B}、{A， C}、{A， D}、{B， C}、{B， D}、{C， D}，那么它们相应的矩阵元素为{2， 3}， {2， 4}， {2， 5}，{3， 4}等等，把这些元素的计数加1，就完成了对第一条交易项目的处理。接着再扫描完数据库的所有交易，并作相应处理。再设置一个用以记录事务中项目个数的数组M[i]，以备消减数据库使用。

使用以上方法获得候选频繁2项集的支持度后，接着查找矩阵的第二行，找出所有支持度大于min_sup的项，再用第一项与第二项组合生成3项集，并且记下第一项与第二项分别所在的列号，于是查找由这两个列号组成的矩阵元素的值，若大于min_sup，则用第一项与第二项组合生成的3项集就是频繁3项集，其支持度即为第一项和第二项这两项的2个列号组成的矩阵元素的支持度和第一项及第二项的支持度，三者的最小值。该方法可直接产生频繁3项集以及其支持度，无需生成候选频繁3项集。

2.2数据库的消减

第一，因为由该行任意两项组成的3项集的支持度不可能大于min_sup。于是在2项集支持度矩阵中，若某行的支持度都小于min_sup，那么就删去该行表示的事务。第二，若一条事务包含k频繁项集，则它本身至少要包含k个项目。于是在产生k（>3）的候选频繁项集时，只需查看数组M[i]的值大于k的事务，如果小于k，则下次不用再查找。

2.3算法描述及挖掘过程

现举例来说明改进算法的处理过程。例如有项目数据库第一条事物为ACDF，第二条为BCE，第三条为ABCD，第四条为BE。设定min_sup=2。

（1）定义2项集支持度矩阵，除第一行外，上三角矩阵元素都初始化置0。把数据库的每条事物逐一扫描后，可以得到2项集的支持度。例如先把第一条事物拆成2项集{{ A C }，{ A D }，{ A F }，{C D}，{C F}，{D F}}，给矩阵相应位置加1，后面的事务使用同样方法处理。结果如图2。再用数组M记录每条事物中的项目个数和。例如第一条事务中有4个项目A，C，D，F，那么M[1]=4。

（2）读取矩阵中的元素值，取出值大于等于2的就可以得到2项频繁项集，从图3中可以查到{{ A C }，{ A D }，{B C}，{B E}，{C D}}和各自的支持度。

（3）生成3项频繁项集。在矩阵第二行中按顺序找出两个元素值大于等于min_sup的元素，找到AC、AD两项，再寻找这两项的列号组成的元素CD的值，等于2，其大于等于min_sup，所以由AC和AD组成的项ACD是频繁的，其支持度为AC，AD，CD中最小值2。继续查找该行，找不到元素值大于等于2的项。开始查找第三行及以后各行支持度大于等于min_sup的元素。找到BCE。直到扫描完数据库。生成3项频繁项集{{ A C D}、{B C E}}和各自支持度。

（4）转入改进算法第3步，由3项频繁项不能再生成4项候选项集。算法结束。

3 改进算法计算机一级等级考试的应用

在全国计算机一级等级考试中，对于学生答错的题所代表的知识点及学生编号建立事物数据库[4]。之后，使用改进的Apriori算法进行挖掘。实验数据是本校2015级学生参加等级考试的试卷处理后的结果。一共涉及48个知识点，即items（48）。学生做错的知识点用Noi来表示。实验结果得到了几条关联规则。比如，答错了电子表格中“函数”知识点的同学，其中大部分人同时答错了电子表格中“公式”知识点试题；答错了“二进制转八进制”知识点试题的，几乎在“二进制转十六进制”这一知识点上也是全军覆没。

4结语

因为采用了2项集支持度矩阵，较好地解决了频繁2、3项集的求解问题。加之采取了一定的数据库缩减策略，从而比传统的Apriori算法节省了更多的时间。同时也在全国计算机一级等级考试的应用中取得了明显效果。

参考文献

[1] R.Agrawal and R.Srikant， Fast Algorithms for Mining Association Rules in Large Databases[C]，In Research Report RJ 9839， IBM Almaden Research Center， San Jose， Califomia， 1994.

[2]黄艺坤.Apriori算法在无纸化考试系统中的应用和改进[J].周口师范学院学报，2015，32（2）：129-130.

[3]秦吉胜，宋瀚涛.关联规则挖掘AprioriHybird算法的研究和改进[J].计算机工程，2004，30（17）：7-9.

[4]申义彩，杨枫，王晓燕.基于基于关联规则的计算机等级考试答卷分析[J].学术研究，2011，10（20）：128-129.