基于数据支持的Apriori分类算法的课程推荐研究

    

    

    引言

    在互联网大数据时代，人人均需学习，时时均可学习，学习是信息化时代的显著特征，在网络教学中，根据学生的需求，智能性推荐学生可能感兴趣的课程，对于改善用户体验十分重要。传统的推荐算法采用“最近最常使用”的思想，即某个课程最近被观看得越多，喜欢该课程的学生可能更多。该算法虽然比较朴素，也能取得不错的效果，但是有一个致命的缺点，就是无法根据学生需求智能推薦。例如，某个学生是艺术生，推荐却是数据结构之类的课程，这种推荐极大可能将是一个无效推荐。如何实现智能的有效推荐课程？“最近最常使用”这种朴素的算法无能为力，而Apriori算法却能满足需求，实现智能推荐。

    Apriori算法

    1.Apriori算法介绍

    Apriori算法是一种亲和性分析分类算法，用来分析两个数据之间的相似度。亲和性分析算法使用广泛，我们日常生活中的产品推荐、顾客群划分、攻击检测等都有亲和性分析算法的身影。日常生活中，我们不可能拥有全部数据集，只是拥有数据集的一部分。OneR之类的分析算法要求遍历全部数据集，得出每一个特征值的置信度和误差，然后选取最佳数据规则。这种方法一是训练数据不能达到理想情况，二是算法复杂度太大，当数量增多时，OneR算法复杂度将呈指数级爆炸式增长，不利于计算机分析大数据。

    亲和性分析算法不必遍历全部数据集，它维护一个频繁集合，然后不断地加入新的频繁项，从而巧妙地规避了复杂度爆炸式增长的问题。Apriori算法就是一个简单巧妙的亲和性分析分类算法。

    Apriori算法首先要设立一个最小支持度，这是Apriori算法的重点和精髓所在。因为Apriori算法只考虑频繁的集合，而忽略不频繁的集合，故必须设定一个最小支持度来制订频繁集合的下限。正因为Apriori算法不必考虑全部集合，所以Apriori算法的计算时间较短，效率相对比较高。

    2.数据获取与清洗

    有关课程推荐的数据挖掘实践数据获取并不像获得网络访问日志那么烦琐。学生选课项目在数据库内有清晰、明确的记载，数据库导出数据机制也很完善，同时Python数据挖掘软件包Pandas也支持直接从数据库拿取数据。本节还是先导出学生选课数据CSV文件，然后再在Jupyter平台上进行数据清洗，最终得到数据挖掘必要的数据信息。

    网络教学平台课程分为必修课程和选修课程。必修课程是按照教师要求，班级统一注册的课程，该类型课程具有强制性，学生不可取消。选修课程是学生根据自己的兴趣选学的课程，可以随时取消学习。在课程推荐系统中，应该推荐选修课程而不是必修课程，这一是因为不同班级的学习要求可能不同，二是因为必修课程选课基数大，构建选课系统时，会产生一定噪声问题。因此，本文的课程推荐算法只设计选修课程的推荐。

    笔者使用compulsory字段来判断一门课是不是选修课。所使用的代码为：

    SELECT a.sid， a.cid， a.canceled FROM student_course as a LEFT JOIN course as b on a.cid = b.cid WHERE b.compulsory = '0' limit 10000;

    筛选出100000条学生的选修课信息，并用DataStrip的数据导出功能导出CSV数据。因为数据库里的数据十分规则，所以这里的数据不需要做数据清洗。

    3.数据处理过程

    首先使用pandas加载用户数据，因为导出数据时没有设置数据表头，所以需要把header设置为none，同时设置表头sid、cid和canceled。加载用户数据后，显示前5条数据来查看数据是否加载成功（如图1）。

    Apriori算法的基本思想是找出数据的频繁项集合，对于课程推荐来说，算法依据是：如果学生喜欢某些选修课，那么他们可能喜欢另一些选修课。那么怎么确定学生是否喜欢某门选修课呢？判断依据是：如果学生注册了选修课，同时也没有取消该选修课，那么他们就是喜欢这门选修课;注册过该选修课，但是随后又取消了该门选修课，那么学生就是不喜欢该门选修课;没有注册的课程不知道学生是否喜欢它们。使用代码all_courses['favorable'] = all_courses['canceled'] == 0来判断学生是否喜欢某门选修课，显示判断结果。

    Apriori算法比较复杂，运算所需的内存量很大。在笔者16G内存的机器下，训练用户达到200的情况下，内存使用已达12G左右。因此本文为了减少运算量，使用数据集中的一部分来训练模型。选择前200个用户的选课数据，并筛选出它们喜欢的课程，存储在favorable_courses里面，然后按学生id进行分类。代码如图2所示。

    从图2中可以看到，前200名学生喜欢的课程记录一共有17152条，按照学号分类后，一共有199条数据。因为学生是否喜欢某门选修课程是一个固定已知常量，所以将它的类型设置为frozenset，这样做的原因是能够加快后面Apriori算法的运行速度。

    然后，创建一个新的集合，用来观察前200名学生中喜欢的选修课喜欢的人的数量，并且按照喜欢的人数进行降序排列，显示其前5位。

    Apriori算法的流程是使用最小支持度生成最初频繁项集。然后不断迭代循环，查找现有频繁项集的超集，并判断新生的集合是否频繁，如果不是，算法迭代完成，如果不是把生成的集合当作新的查找集合，继续查找频繁集合，直到完成为止。

    生成频繁项集合时，每次加入学生已经订阅过但是却没有出现在里面的课程，用它生成新的数据项。每次新生成的数据项集合都会与最小支持度比较，判断它是否足够频繁，如果是，则返回作为新的查找集合。如果将最小支持度设置为50，运行代码，初始项目集合中有50个频繁项集。然后对测试数据进行Apriori算法训练，训练数据代码会显示，对于测试数据，最多生成1596个频繁项集，同时也可以看到，随着迭代次数的增多，频繁项集的数量不断衰减，Apriori算法只需判断频繁数据项集合的超集而不需要遍历所有数据，快速收敛正是Apriori算法的优点。

    生成频繁数据项集合后，我们还需要在该集合中抽取关联规则。该关联规则就是课程推荐算法：如果学生喜欢规则前提中的所有课程，那么他可能喜欢结论中的课程。对待任何一个频繁数据项集合，都要生成一条这样的关联规则。

    如上页图3所示，遍历每一次频繁数据项集合，对其中的每一个频繁数据项，收取一条记录作为结论，其余记录作为条件，并把它加入备选关联规则集。一共生成了29188条关联规则集合。

    打印第10000条到10005条备选关联规则，如图4所示，其中frozenset（）表示前提条件，学生喜欢的选修课程，后面是结论，学生可能喜欢的选修课程。例如，学生喜欢id为296、2858、2571、356的选修课程，那么他可能喜欢第260条选修课程。

    筛选备选关联规则。遍历所有学生喜欢的课程集合，首先判断学生是否喜欢关联规则前提下的所有选修课程。如果喜欢，则判断用户是否喜欢结论中的课程。如果是，则关联规则有效，如果不是，关联规则无效。用规则成功的次数除以所有应用规则的次数，得到规则的置信度，即生成9245条有效关联规则。对前5条有效关联规则进行排序，得到的关联规则的置信度均为1。

    4.数据处理的结果

    最后对生成的关联规则进行测试，测试数据选取除去训练数据的用户数据。对于每一条关联规则，首先判断关联规则的前提是否在测试数据中，如果是，则判断关联规则的结论是否在测试数据中，如果在，则关联规则有效。用规则成功的次数除以所有应用规则的次数，得到规则的置信度——共生成9245条有效关联规则。对执行规则进行排序后，打印出前五条关联规则以及他们的训练置信度和测试置信度。不难发现，最高置信度规则为0.903。在测试中对于选修了id为1210、589选修课程的学生来说，有90.3%的可能性选择id为1196的选修课程。

    Apriori算法的改进

    分析上述Apriori算法，每次通过遍历候选数据集，比较它是不是第k-1次频繁项集的子集，若是，则把它加入第k次频繁项集，若不是则将该数据集舍去。当数据挖掘的数据量不大时，这不会造成什么影响。当挖掘的数据量变大时，每次比较和删除数据集将会造成很大的性能损失。性能损失主要有两方面，一是每次比较是不是k-1次频繁项目集的子集时查找所带来的性能损失，二是每次删去数据集合时IO操作带来的性能损失。数据集越大，这两个操作带来的损失越大。

    解决上述问题的方案有两种，一是减小频繁备选数据集的生成数量。当合适的备选数据集生成得越少时，在数据查找和删去无效数据集合上所花费的时间和IO操作就会变少。二是减少查找所花费的时间。每次查找都是按照顺序查找完成的，时间复杂度为O（n），如果每次将上一次生成的频繁数据集映射到Hash表上，那么子集比较的时间复杂度为O（1），生成频繁项集的时间也从O（n2）下降到O（n）。

    我们知道，第k次频繁数据集一定是第k-1次的子集，因此我们可以将k-1次的数据集合两两合并，生成备选数据集合，再与第k-1次数据集合进行比较，而不是从原始数据集合中生成Cnk个备选数据集合，然后与k-1次频繁数据集合比较，删去不合适的频繁数据集合。同时，将每次生成的频繁项集映射到Hash桶中，以降低比较所花费的时间。修改数据集查找算法，修改后的算法如上页图5所示。

    上述查找算法遍历第k-1次频繁项集，不断比较两个频繁项集之间的前k-2项是否相同，然后生成新的频繁项集的备选集合。由上文分析可知，频繁项集的子集一定是频繁的它的逆否命题，不平凡的集合一定不是频繁项的子集。于是遍历以前产生的k-1次频繁项集，查找新生成的频繁项集是否包含这些子集。如果包含，则保留，如果不包含，则删去该备选集合。

    以上文学生数据作为训练数据，比较改进前和改进后的算法，算法执行时间明显缩短。

    Apriori算法的应用

    如上所述，在数据挖掘平台生成关联规则以后，将关联规则存储内存中。每次用户登录时，电化教学系统向数据挖掘平台发送该用户目前的选课列表，高性能数据挖掘服务器根据用户数据，选择合适的关联规则，向用户推荐课程。将数据挖掘平台和前端系统分离的原因是数据挖掘系统计算量很大，如果和电化教学系统共享一台主机，将会影响电化教学系统的性能。

    Apriori系统测试

    1.系统功能测试

    后台系统具有备课中心、课程管理、教学互动、组织结构、用户管理、统计报表、校本资源、网络硬盘、系统设置等9大功能。备课中心负责添加课程、试题和资源。课程管理负责课程的审批和发布。教学互动是讨论交流环节板块，教师可以在此添加课程内容，发布作业，回答学生的提问。组织结构负责管理学生班级和专业，系统管理员可以在用户管理模塊添加学生、教师等角色。统计报表功能能够统计课程的播放次数、资源的下载次数。通过本系统，管理员和教师能够有效地管理电化教学系统。

    以添加题库为例，选择备课中心→题库管理→添加试题，会新增一个题目输入框，在此输入框中可以输入试题的题面，也可以从Word导入题面，在标准答案输入框中可以输入该试题的答案。同时，可以控制题目的难易程度和所要考查的知识点，点击提交按钮即可完成试题的添加。

    2.推荐系统的测试

    基于Apriori算法的热门课程推荐，每次推荐的课程将和学生完成的观看的课程相关。系统测试用户完成了一个模拟电路的课程，因此推荐的都是和电工相关的课程。现在，已经得出了每条规则的置信度，如何评估算法的性能呢？这里采用平均置信度这一评估标准，即把Apriori算法产生的9245条推荐规则的置信度做一次均值运算，和普通的最近最常访问算法做对比，比较算法的性能。代码如上页图6所示。从图6中可以看出，Apriori算法的性能远高于最近最常所使用算法。数据挖掘技术能够有效地提升课程推荐的准确度。

    结束语

    本文重点介绍了两个问题的数据挖掘过程：登录日志的数据挖掘和课程推荐的数据挖掘。两个数据挖掘过程均很好地完成了数据挖掘任务并获取了相关结论，对改进电化教学系统、提高教学质量有着很重要的意义。

    参考文献：

    李广璞，黄妙华.频繁项集挖掘的研究进展及主流方法[J].计算机科学，2018，45（S2）：1-11+26.

    作者简介：吴浩，江苏省海安中等专业学校讲师，硕士研究生毕业，研究方向为信息化教学与教学改革。

    基金项目：本文是第四期江苏省教育科学研究院立项的职业教育教学改革重点课题（编号ZCZ39）的研究成果之一;也是江苏联合职业技术学院立项课题（编号B/2018/07/119）的研究成果之一。