改进的Apriori算法在学生成绩分析中的应用

一、关联规则的Apriori算法

Apriori算法的原理是, 如果一个项集是频繁项目集, 那么它的非空子集也是频繁项目集。采用Apriori算法生成频繁集的过程是:首先通过循环扫描事务数据库统计出项目集合中每个项目的支持度, 然后根据设定的最小支持度进行筛选, 得到1-频繁项目集。1-频繁项目集中的项进行自连接处理, 即可生成所有包含2个元素的项目集, 然而这些项目集不一定是频繁项目集, 所以需要进行剪枝。剪枝的办法是看它的所有1非空子集是否在1-频繁项目集中, 如果不在, 则剔除该2项目集, 剪枝后剩下的项目集就是候选2-频繁项目集。扫描整个事务数据库计算出候选2-频繁项目集中每个项目的支持度, 筛选出支持度不小于最小支持度的项目得到2-频繁项目集。依次类推生成3-频繁项目集……直至产生的候选k-频繁项目集为空, 算法结束。若频繁项集不能再连接成新的候选项集时, 此时的频繁项集就是最大频繁项集。自连接不是项目之间的排列组合, 而根据k-频繁项目集中的两个项目是否有k-1项相同决定。采用Apriori算法从频繁项目集中找出符合条件的关联规则的过程是, 遍历所有的频繁项目集, 从每个项目集中依次取1、2、...k个元素作为后件, 该项目集中的其他元素作为前件, 筛选出置信度不低于最小置信度的规则即可。可以先生成所有的后件只有一项的关联规则, 然后再生成后件两项的关联规则, 依次类推, 直到生成所有的关联规则。

二、Apriori算法的分析与改进

Apriori算法的过程描述表现了Apriori算法的主要不足之处是:算法对数据库的多次扫描必然占用大量的时间和内存空间, 使得算法运行速度慢;算法的频繁项目集自连接、剪枝耗费内存空间, 也限制了算法的运行效率。基于分片的改进Apriori算法首先将原始事务数据库分成多个不重叠的“片”并使用Apriori算法分别找出每个片段的局部频繁项目集, 这些局部频繁项目集合并组成全局候选频繁项目集。最终的频繁项目集通过扫描原始事务数据库计算全局候选频繁项目集的支持度得出。本文采用李桥提出的基于分片的Apriori-P算法对成绩进行关联规则挖掘。Apriori-P算法如下:

输入:事务数据库D, 最小支持度min_sup。

输出:频繁项集L。读取事务数据库D;

三、改进的Apriori算法在成绩分析中的应用

下面以某校2014级计算机专业“成绩表”的部分信息为例介绍成绩数据关联规则挖掘的全过程。表1是计算机专业成绩表的部分信息。

表1中的10名学生成绩数据经过数据清理—类型转换—有效数据筛选后, 得出如表2所示的数据信息 (num代表学号, grade_id代表成绩的等级) :

表2中的频繁项集的Apriori-P算法挖掘过程是:首先将表2中的事务数据库D等分为三个局部候选集, 分别为20140201-20140203局部候选集、20140204-20140206局部候选集、20140207-20140210局部候选集.

设置最小支持度为2找出每个候选集的频繁项目集, 如表3、4、5所示:

局部频繁集合并得到全局候选项集{d, i, n}, 扫描事务数据库D, 计算出{d, i, n}的支持度为3, 高于最小支持度2, 确定{d, i, n}为频繁项集。然后按以下方法可以推算关联规则:首先求出含有最大频繁集的事务数nnum, 其次将频繁项集中各个单项计数表示为pnum, 如果nnum/pnum不小于最小置信度, 则将以“n->d&i”形式表示的关联规则输出;将频繁项集中的任意两项组合的事务数定义为pnuml, 如果nnum/pnuml不小于最小置信度, 则将以”d&i->n”形式表示的关联规则输出。如果设置最小置信度为75%, 本例的关联规则有”d&i->n”、”d&n->I”、”n&i->d”和”d->i&n”。

四、成绩数据挖掘结果分析

当设置最小支持度值10%、最小置信度值45%时, 成绩挖掘结果是最大频繁项集为{d, i, n}, 三个关联规则为”d&i->n”、”d&n->i”、”n&i->d”, 即高等数学成绩等级为d, 计算机应用基础成绩等级为i, C语言成绩等级为n。当设置最小支持度值5%、最小置信度值35%, 最大频繁项集为{d, i, n}、{d, i, m}、{c, i, m}和{c, i, n}, 而关联规则有“d&i->n”、“d&n->i”、“i&n->d”、“d&m->i”、“i&m>d”、“c&i->m”、“c&m->i”、“i&m->c”、“c&i->n”和“c&n->i”。经过反复修改检测后确定最小支持度为5%、最小置信度为35%时生成的关联规则最能表现课程之间的关联程度。下面通过表9具体分析关联规则挖掘结果。

从表9获知, 关联规则“d&i->n”的有效性最强, “c&i->m”有效性次之。根据关联规则“d&i->n”和“c&i->m”的强有效性, 最终高等数学成绩及格和计算机应用基础课成绩及格影响决定了C语言成绩及格, 而高等数学中等成绩和计算机应用基础中等成绩影响决定了C语言中等成绩, 这说明高等数学和计算机应用基础的学习好坏必然影响到C语言的学习。

摘要：学校积累了海量的成绩信息, 除了反馈学生各学期的学习结果, 还可以从中挖掘出各学科之间的关联关系, 帮助学生更有效率的学习.关联规则的Apriori算法对数据库的多次扫描和频繁项目集自连接、剪枝耗费内存空间, 也限制了算法的运行效率.本文采用李桥提出的基于分片的Apriori-P算法对成绩数据进行关联规则挖掘。

关键词：Apriori算法,改进,分析