基于FP—Growth的高校学业预警系统设计与实现

陈玲萍

摘 要：文章提出了一种基于FP-Growth算法的高校学生学业预警系统，能够根据以往的学生成绩信息挖掘出不及格课程间的关联规则，以提前给学生发出课程预警。首先从现有的学生成绩系统中筛选并构造出学生不及格课程事务数据库；然后运用FP-Growth算法进行课程关联规则挖掘；最后利用关联规则，自动发现学生将来可能存在危险的课程，并结合现在的学习成绩发出学业预警。经验证，本方法对学生成绩的预警有较高的准确率，并可推广应用到学生工作的其他方面。

关键词：关联规则；学业预警；FP-Growth

高等教育进入大众化阶段，学生的学业状况关系到个人发展、家庭和谐及社会安全。通过学业预警系统对学生课程成绩进行分析，能及时发现学生课程上存在的问题和困难，有效地预防学生留级、退学事件的发生，是加强学生学业管理，提高人才培养质量的重要手段，是构建和谐校园、和谐社会的重要途径。

普通的学业预警系统通常只统计学生的学分，当所欠学分达到一定程度就发出预警。这种方法及设计存在预见性不足问题。当系统发出预警时，学生已经失去了采取措施的先机。本文提出采用数据挖掘的方法来设计学业预警系统，通过以往学生的课程成绩发现课程间隐藏的关系，预测未来可能发生的不及格课程，并对学生及时发出预警，以提示学生对预警课程的学习更加重视、更加努力，达到学业预警的目的。

1 关联规则挖掘的应用

关联规则挖掘是数据挖掘领域中的一个重要分支，其应用已经渗透到社会生活的各个领域。关联规则挖掘起源于对购物篮问题的分析，该问题是在现有的商品货物交易记录基础上，对消费者购买习惯进行分析，从而挖掘出消费者的消费模式。在这些一般性消费模式指导下能够更加合理地摆放货物，制定符合消费者消费行为的促销活动，以达到提高销量的目的。Agrawal等[1]提出的基于頻繁项集的Apriori算法是经典关联规则算法，在此之后涌现了大量的关联规则挖掘方面的研究，其中包括关联规则问题衍生出了对Apriori算法的优化问题、关联规则的并行化问题以及关联规则在实际工程中应用问题等。Han等[2]提出的FP-Growth算法是比Apriori效率更高的频繁项集挖掘算法。该算法将事务集压缩到FP-Tree上，将压缩后的事务数据库采用分治的策略划分到条件数据集中，再从各个条件数据集中挖掘出关联规则。由于FP-Growth算法只需遍历数据集两次就能够完成频繁模式发现。因此，本文在学业预警系统中采用FP-Growth算法进行课程关系的挖掘。

2 基于FP-Growth关联规则挖掘的学业预警系统

2.1 关联规则相关定义

2.1.3 频繁项的定义

设X是由某些项目组成的非空集合，即XI且X≠Φ，Minsup为给定的最小支持度，也称为支持度最小门限[3]。如果S（X）≥Minsup，X属于频繁项。由频繁项组成的集合称为频繁项集。此外，若X是由K个项目构成的，则X又称为K-维频繁项；所有K-频繁项构成的集合称为K-维频繁项集。

2.2 FP-Growth算法基本思想

FP-Growth算法是利用树结构来描述项之间的关系，该算法最大的优势在于将事务之间相同的项进行压缩，从而降低了算法的空间复杂度。它和经典的Apriori算法的不同点在于它不是先产生后验证的思想，而是通过构建一种频繁模式树的紧凑型数据结构，并且不需要产生候选频繁项集直接从树结构中提取频繁项集。算法的主要思想是将事务型数据库中的每条事务映射到FP-Tree中，但是不改变项集之间的关联关系。FP-Growth算法的重点在于对FP-Tree的构建，构建FP-Tree需要对数据库进行两次遍历，第一次遍历事务集得到频繁1-项集及其支持度，根据其对应的支持度的大小对其进行排序；第二次遍历事务集，通常以“NULL”为根节点，在第一次遍历得到的频繁1-项集合的基础上构建FP-Tree。为了更快地在提取频繁项集时能够对FP-Tree进行遍历，需要构建一个包含所有频繁项元素的项表头，表中的每个项元素都有一个指针指向该元素项在FP-Tree对应的节点位置，具体算法如下。

2.2.1 构建FP-Tree

遍历事务数据库T，找出所有满足大于最小支持度的所有项并统计这些项的频度，这些项就被称为频繁1-项集合L[4]，根据其对应的支持度的大小对其进行排序L_First。

创建原始FP-Tree，以“NULL”为根节点。

2.2.2 创建表头

为了方便提取FP-子树需构建一个包含所有频繁项元素的项表头，表中的每个项元素都有一个指针指向该元素项在FP-Tree对应的节点位置。

遍历一次事物数据库T，将T中每个事务的项次序根据L_First进行调整，其中频度越高的项越靠近树的根部，将每个事务看作为树的分支，依次将每个事务添加到树中。如果分支中有前n项事务与树中其他事务相同，则认为该事务能够与其他事务进行路径合并，但要在这些相同各个节点上计数加一，剩余没有的项则在该枝干上分出一条包含剩余其他项的枝干。路径合并需要将新事务合并在树中重复度最大的事务上，依次将所有事务压缩到树中。

2.2.3 提取频繁项集

查找出单个项的条件模式基，条件模式基是以所查找元素项为结尾的路径的集合。统计条件模式基中各个元素的频度，将其中频度小于最小支持度的元素删除。将剩余元素进行全排即频繁项集。

3 学业预警系统构建

本学业预警系统是根据FP-Growth算法找出课程之间存在的隐形规则，找出学生在有课程不及格的时候其他课程中比较危险的课程[5]。由于FP-Growth算法是无监督的机器学习算法，因此，需要提供训练样本以提取出普适的规则。可以选择已毕业大学生在其大学期间的学习情况作为训练样本。

3.1 样本抽取

从已经毕业的大学生本科阶段成绩单中筛选出学生曾经不及格的课程，作为训练样本集，同时需要统计对应课程的学分。每个学生的不及格课程看作一个事务，其中的课程作为项。为了在接下来设置支持度时更符合实际情况，需要删除一部分课程，例如大学校级公选课。由于这些课程每个学生选修的都不相同，同时可选课程数量范围较大，因此，这些课程中的每个课程的频度之和都不会太大，为了提高算法的运算量可以将这些课程删除。

3.2 关联规则挖掘

将提取后的训练数据集输入设置好支持度的算法中。最小支持度一般设置为数据集的5%[6]。对数据集需要划分为3个部分进行训练。首先需要对大学期间挂科学分低于20学分的数据集进行关联规则挖掘，得出这个分段容易不及格课程之间的关联规则。同样找出挂科在20～30学分和30学分以上同学容易出现不及格课程之间的关联规则。

3.3 将测试数据集输入进行验证

将第二步得到的关联规则作为判决条件，根据样本中项与规则中的项进行匹配，找出与样本匹配度最高的规则作为输出结果，规则里样本没有的项即为在以后需要多加关注的课程。匹配度最高的规则中未出现的课程为更容易不及格的课程，将这些课程作为预警结果之一输出。

3.4 统计当前不及格课程的学分之和

作为本学业预警系统输出结果之一，学生当前不及格课程的学分更能准确反映该同学的学业状态，并通过训练大量样本得到學生在后续学习中容易不及格课程的列表清单。

4 实验及分析

4.1 实验方法及结果

实验环境基于Win10+i5-6300HQ 2.30GHz四核环境，利用Python3.6软件仿真。首先将原始数据集进行清洗，筛选出500个样本，其中400是训练样本集，100是验证样本集，构建成事务型数据库。其次对FP-Growth算法进行编程。将训练样本数据集导入算法得出课程间的关联规则。然后输入测试样本集验证预警课程得正确度。最后根据学生当前不及格课程得学分之和以及预测课程给出预警结果。

根据测试集的验证课程的预测准确率很高。例如：学号为“1252100121”电子信息工程专业的学生，他在学生成绩系统中显示有一门“大学英语I”不及格，根据关联规则得出他需要注意的课程有“专业英语（电子信息类）”“EDA技术及应用”“电子线路CAD及仿真”“数据结构”“VC程序设计”等。预测的课程中基本包含了该同学在大学期间所有不及格课程，由于现阶段只有一门不及格的课程，因此得到的成绩状态是“黄”。

4.2 实验结果分析

实验结果验证该预测系统能够准确反映学生当前的成绩状态并且对以后的特定的课程的学习有明确的指导效果。本系统的预警信息主要受训练数据集的影响，不同的训练数据集得到的结果会不相同，不同学校的老师评分标准不同也可能会导致不同的训练数据集，因此，本系统在实际应用中应输入符合自己需求的训练数据集，这样得到的结果才能更符合预期结果。

5 结语

本学业系统能够准确地反映出学生现阶段的学习状态，同时也能对其将来的学习给予一定的提醒，学生能通过本系统制定更加符合自己特点的学习计划。同时本系统也能够帮助老师及时了解学生的学习状态，并在必要的时候给同学合理的指导和帮助，对提高本校的教学质量和提高大学生的综合素质都有很大的作用。

[参考文献]

[1]AGRAWAL R，TOMASZ I，ARUN S.Mining association rule between sets of items in large databases[J].ACM Sigmod Record，1993（5）：302-313.

[2]HAN J，PEI J，YIN Y.Mining frequent patterns without candidate generation[C].Dallas：2000 ACM Sigmod International Conference on Management，2000：1-12.

[3]吴暾华，王萍，刘婷.基于支持向量机的大学生学业动态预警研究[J].中国教育信息化，2017（17）：65-67.

[4]陈建成，屠昂燕，许雪贵.基于遗传算法的学生信息关联规则挖掘研究[J].电脑知识与技术，2008（34）：1747-1748，1754.

[5]张体芳.克隆遗传算法在学生成绩分析中的应用[J].计算机时代，2012（8）：18-19，23.

[6]王华，刘萍.改进的关联规则算法在学生成绩预警中的应用[J].计算机工程与设计，2015（3）：679-682，752.