Apriori算法的学位预警应用范文

《电脑开发与应用杂志》2014年第六期

1经典的Apriori算法的缺点

Apriori算法是一种典型的挖掘布尔关联规则的频繁项集的算法。它使用的是一种被称作逐层搜索的迭代方法，即用k-项频繁项集探索生成（k+1）-项频繁项集。操作方法为先找出频繁1-项集的集合，并将该集合记作L1。再用L1找频繁2-项集的集合L2，用L2找L3，一直到不能再由LK-1找到频繁k-项集为止。生成每个LK都需要扫描数据库才能完成。Apriori算法中频繁项集的生成由连接和剪枝两步组成完成核心操作。为找LK，通过LK-1与自己连接产生候选k-项候选项集的集合记作Ck，完成连接操作步。扫描数据库，确定Ck中每个候选项的支持度的计数，将所有支持度小于最小支持度的项集去掉，从而确定LK，完成剪枝操作步。经典Apriori算法的不足主要有两点。一是在连接步产生庞大的冗余候选项集，二是在生成k-项频繁项集LK频繁项集时，多次扫描事务数据库。

2改进的Apriori算法

针对经典算法的不足之处，改进的Apriori算法提出基于多关键字升序重排频繁项集的项的方法进行频繁项集重组的进行算法优化，此外在改进的算法中还加入了精减频繁项集、压缩数据库事务方法，同时在算法的终止条件判断上借助于频繁项集个数来判断，提高算法执行的效率。

2.1改进的Apriori算法的描述改进的Apriori()算法是基于多关键字排序的项集重排序的Apriori算法，利用数据库优化技术，不断缩小数据库的规模，并结合精减频繁集和连接优化策略，大大提高了挖掘的效率。由频繁项集的个数做为算法终止条件，简化算法终止条件判断。具体步骤为：①生成1-候选项集C1；②L1={c∈C1|c.count>=minsup_count}，并统计中项集个数coun（tL1）；③FOR（k=2；coun（tLK-1）叟k；k++)DO；④FOR所有l∈LK-1DOBEGIN//统计LK-1中各单项出现的次数LK-1（x）；⑤IF(xi∈l)THENxi.count++；⑥删除所含次数小于k-1次单项的项集（k＞2，xi为LK-1中的各单项）；⑦ENDFOR；⑧采用多关键字排序策略对频繁项集项集LK-1进行升序排序//频繁项集的重排序；⑨CK=apriori_gen（LK-1）；//生成k-候选项集；⑩FOR所有事务t∈DDOBEGIN；輥輯訛Ct=subset(CK，t)//在数据库中删除k-1项事务或删除比非频繁项集（k-1）-项集多出一项的k项事务；輥輰訛ENDFOR；輥輱訛FOR所有候选c∈CtDOBEGIN；輥輲訛c.count++；輥輳訛ENDFOR；輥輴訛LK={c∈CK|c.count>=minsup_count}；輥輵訛统计LK中项集个数coun（tLK）；輥輶訛ENDFOR。改进的Apriori算法是基于多关键字排序的频繁项集升序重排列，减少了大量冗余候选项集的产生；精减频繁项集的无效项、压缩数据库事务以及频繁项集的个数控制算法终止条件，提高了算法的执行效率。

2.2算法验证算法验证在最小支持度sup_min固定为25%时，针对不同的交易事务数，比较Apriori算法和改进Apriori算法的执行效率。实验结果如图1所示。由图可知两种算法的执行时间都会随着事务数的增加而增加，但是改进的Apriori算法比经典Apri-ori算法增长的速度明显变缓，因此，当挖掘事务数增加时，改进的Apriori算法的优越性会表现的更加明显。

3基于改进的Apriori算法的学位预警应用

一般来说，各高校都有各自院系专业学生的培养方案，通过培养方案可知影响学生学位的因素。总体来说，影响学生学位的主要因素有：必修课程、选修课程以及学生第二课堂等。其中必修课程分为公共必修课、学科基础必修课和专业必修课，选修课程为公共选修课、学科选修课和专业选修课；第二课堂主要是课外扩展教育，主要分为思想政治与道德素养学分、社会实践与志愿服务方面、科学技术与创新创业方面、文化艺术与身心发展方面、社团活动与社会工作方面、技能培训及其他方面。系统主要针对学生学位预警进行研究应用，包括必修与选修课程，以及绩点计算来达到学生学位预警的功能。本系统采用本校信管系计算机科学与技术本科专业的学生数据作为测试数据。在设计数据库的过程中存放了学生信息及成绩、课程信息以及生成挖掘规则并针对某个学生依据挖掘结果给出预警分析。首先完成数据清洗及转换：课程类别：公共必修A、学科必修B、专业必修C、公共选修D、学科基础选修E、专业选修F、绩点G。学生成绩：采用离散区进行转换，90分以上a，80分至90分b，70分至80分c，60分至70分d，60分以下e。对于某门课程缺失的成绩使用该班该门课程的所有同学的平均成绩填充。生成的系统操作界面如图2所示：依据该系统可以得到如下规则：当公共必修课程成绩较低时，容易出现专业必修课程成绩也较低的问题，学生应该引以为戒。当公共必修、专业必修课的成绩较低时，则其学科必修课程成绩也会较低，学生应该引以为戒。当学科基础选修成绩较低时，其专业选修课程的成绩也会较低。故该系统可以起到如下作用：当公共必修、专业必修的得分在70分以下时，将影响学生对学位获得，从而进行预警。当公共必修和学科必修的得分在70分以下时，提示学生可以通过专业必修课程的得分来进行调整达到顺利获得专业学位的目的。

4结束语

本文对原有的Apriori的算法提出了一种基于精减项集和基于多关键字排序的项集重排的改进的Apriori算法，并将改进的Apriori算法应用到学位预警系统中，结果证明，应用该算法实现的学位预警系统能够很好地达到预期目标。

作者：曹莹苗志刚张红霞单位：河北金融学院信息管理与工程系