分类器组合增量集成的远程教育论文

１引言

基于上述分析，为了更好地在远程教育系统中对学生的表现进行预测，本文提出使用投票方法结合朴素贝叶斯的增量版本、１－ＮＮ和ＷＩＮＮＯＷ算法。实验结果表明，本文提出的算法应用于预测学生表现方面非常有用，能够识别出学生的不良表现，还能使老师在较早阶段采取预防措施。甚至在学年一开始，为了对有危险的群体提供额外的帮助，更加准确地诊断出学生表现的能力会随着学期中加入新的课程数据而提升，为老师提供了更加有效的结果。

２背景

本章给出为预测学生表现进行的教育数据挖掘、在线学习算法和增量集成分类器的一些基本理论。

２．１教育数据挖掘

分类、分簇、可视化、关联规则和统计挖掘通常基于学生们的使用数据发掘新的、有趣且有用的知识，主要应用于电子学习问题或对象可处理与评估学生的学习表现、基于学生的学习表现提供适应性课程和学习建议、处理与评估学习材料和基于网页的教育课程、提供教师和学生的电子学习课程反馈、监督非典型学生的学习表现。分类（电子学习中最有用的教育数据挖掘任务之一）可用作不同的教育目标，例如：将提示驱动或错误驱动的那些学生分组，找出这些学生通常有的错误观念；使用智能教学系统时预测／分类学生等。还有，使用不同数据挖掘方法预测学生学习成绩（分出低、中、高等级）、使用来自Ｍｏｏｄｌｅ日志的神经网络模型。

２．２在线学习算法和增量集成分类

在线学习任务是为了从标记的随时间分布的训练数据中获得一组概念描述，这类学习对许多应用都是重要的，如计算机安全、智能用户接入和市场购物篮分析，客户的喜好会随着新产品而变化，服务变得可用。应对概念漂移算法必须快速并精确地收敛到新的目标概念，而且在时间和空间上都有效。在不断变化的环境中增量学习系统理想的特征有：•无明显关于系统环境变化的信息进入系统时监测环境变化的能力。•从变化环境中迅速恢复的能力和调整假设满足新环境的能力。•旧环境重复出现时在环境中利用先验经验的能力。在线学习算法处理每个训练实例一次，不需要存储和预处理，维护当前的影响目前所有训练实例的假说，这类算法对大型数据集也是有用的，对大数据使用要求多次遍历的批算法代价非常昂贵。批神经网络学习算法会多次遍历数据集，但在线学习的神经网络仅需遍历一次数据，然而，仅遍历一次数据可能会有一些相关损失。所有这些算法都有一个已知的缺点，一次进行几个例子的学习非常困难，为了解决这个问题，一些技术依赖于窗口技术，它包括存储的最后ｎ个例子，当新例子加进来时才执行一次学习任务。加权多数算法（ＷＭ）是许多在线算法的基础，ＷＭ维护专家集的权重向量，通过专家之间的加权多数投票预测输出。投票感知在训练期间能存储更多的信息，然后使用这个精细的信息在测试集上产生更好的预测。为了计算一个预测，算法计算了每个预测向量的二进制预测，通过加权多数投票合并所有这些预测，使用的权重是上述的幸存次数，这产生了直观的感受，“优秀”的预测向量幸存时间长，在多数投票中有较大的权重。合并分类器的概念是改进分类器性能的一个新方向，然而，在线设置中不是很明白如何直接应用集成方法。一个解决办法是依靠用户指定每个基本学习者输入流中例子的数目，但该方法假设已知很多关于数据流结构的情况。也存在重新加权分类器的在线升级算法，但是这些算法假设分类器数目是固定的，此外，当基本模型由少量例子训练时在线升级最初可能会有很大的损失，算法可能再也无法恢复。

３算法

提出众所周知分类器优化集的选择是多分类器系统的一个重要部分，通常把分类器输出的独立性当作获得更好的多分类器系统的优势。分类器合并项中，投票方法要求分类器无任何先决条件。当使用投票方法合并多个分类器时，如果大多数专家同意他们的观点就会做出正确的决策，基于对这一点的信任，本文期待能获得更好的结果。目前，有三种集成学习算法备受关注：•ＷＩＮＮＯＷ算法的核心类似于感知。如果∑ｉｘｉｗｉ＞θ，它分类一个新的实例ｘ到类２，否则分类至类１。然而，如果预测的类是正确的，ＷＩＮ－ＮＯＷ如下更新它的权重，如果预测的值是ｙ′＝０，且实际值为ｙ＝１，则权重太小；因此，对于每个ｘｉ＝１，权重ｗｉ＝ｗｉ•β这类的特征，其中，推广参数β大于１。如果ｙ′＝１且ｙ＝０，则权重太大；因此，对于每个特征ｘｉ＝１，会通过设定权重ｗｉ＝ｗｉ•β中０＜β＜１来降低对应的权重，称为降级参数。ＷＩＮ－ＮＯＷ是指数更新算法的一个实例，相关特征的权重呈指数增长，但是不相关特征的权重呈指数缩小，基于这个原因，ＷＩＮＮＯＷ能迅速适应目标函数中的变化（概念漂移）。•１－最近邻（１ＮＮ）是基于这样的原则：一般会存在与数据集内实例很靠近的实例，且这些实例有类似的属性。如果把实例打上类标签，则未分类实例的标签值可以通过观察它的最近邻居类而确定。这个空间内实例的绝对位置不如实例之间相对位置那么重要，使用距离度量标准确定相对距离，理想的距离度量标准一定是两个相似类的实例之间的最小距离，而不同类的实例之间的最大距离。•朴素贝叶斯分类器是最简单的贝叶斯网络形式，因为它认定了每个特征与其他特征都是独立的假设，给定类特征的状态。独立性的假设显然几乎总是错误的，然而，简单的朴素贝叶斯方法仍然很有竞争力，尽管它提供了对真实基础概率很差的估计。朴素贝叶斯算法用于“批模式”，意味着算法见到它的训练实例之后还不能执行它绝大部分计算，而是在所有训练实例上累积特定信息，然后在整个群里或者实例的“批”上执行最终的计算，然而，需要注意的是，算法中没有固定任何东西去阻止使用它进行增量式的学习。例如，考虑增量式朴素贝叶斯算法可以运行，假设它只遍历一次训练数据。第１步，初始化所有的计数和总和为０，然后贯穿训练实例，一次一个，对于每个训练实例，给定特征向量ｘ和它的标签值，算法贯穿特征向量并递增合适的计数；第２步，用每个计数值除以同一类训练实例的数目转化这些计数和总数为概率；最后，计算之前的概率ｐ（ｋ），当作类ｋ所有训练实例的分数。本文提出的集成算法以创建三个算法（ＮＢ、ＷＩＮＮＯＷ、１－ＮＮ）的集为起点，当新的实例到达时，算法经过它，并接收每个专家的预测。在线设置中，算法连续修改它使用的假说，重复接收模式，基于专家预测的多数投票预测它的分类，找出正确的分类，可能因此更新它的假说。本文提出的集成方法的整体框图如图１所示，其中，ｈｉ是每个分类器产生的假说，ｘ是分类的实例，ｙ＊是提出的在线集成方法的预测。模型的数目或运行时间参数由用户调整，这也是算法的一个易用性指标，对于非专业性数据挖掘，本文提出的集成方法无用户调整参数，将更吸引人。本文使用这三个具体的算法是因为它们很容易适应在线环境，不仅同一个ＷＲＩ的新标记可利用，而且下一个ＷＲＩ的标记也变得可用。对这三个算法使用简单的多数投票方法是因为它在在线环境中使用简单。增量训练学习者成为新实例的打包升级实现是可用的，但是没有新特征变得可用。本文提出的集成方法能轻松的实现每台机器并行使用学习算法。并行和分布式计算对机器学习（ＭＬ）执行者来说很重要，ＭＬ系统并行或是分布执行的优点有：

１）提高速度；

２）增加可使用的应用范围（例如它可以处理更多数据）。

４实验

４．１数据集

本文以希腊远程教育大学“信息”课程提供的训练集ＨＯＵ为研究目标，ＨＯＵ的基本教育单元是模块，一个学生每年可以注册高达三个模块，“信息”课程由１２个模块组成，可得到学士学位。ＨＯＵ的ＩＮＦ１０模块中，每学年学生必须上交四份书面作业，参加与老师面对面的四个可选会议，１１个月后应考最终的测试。希腊的大学成绩系统是１０分制系统，学生分数大于等于５，则通过课程或模块，而小于５则意味着挂科。共有１３４７个实例（学生的记录）注册ＩＮＦ１０，如表１所示。从两个不同资源中收集数据，ＨＯＵ的学生注册和老师的记录，几乎收集到了所有学生的有关数据。“类属性”（因变量）表示导致期末考试测试结果的两个值，“失败”表示学生表现差，“差表现”表示学年内暂停学业的学生（由于个人或专业原因或没能力上交两份书面作业）及不参加期末考试或参加了期末考试但分数低于５分的学生，“通过”表示完成了ＩＮＦ１０模块，在期末考试中得到的分数超过５分。

４．２实验结果及分析

第一阶段（训练阶段）使用２００６～２００７学年收集的数据训练每个算法，将训练阶段划分成四个连续步骤，第１步包括来自第一份书面作业和得到的类中的数据，第２步包括第１步使用的数据和第二份书面作业的数据，第３步包括第２步使用的数据和第三份书面作业的数据，第４步包括第３步使用的数据和第４份书面作业的数据。随后，收集新学年（２００７～２００８）的一组数据，这组数据用于测量预测值精度（测试阶段），测试阶段也分成四个步骤，第１步，为了预测类，使用第一份书面作业。剩余的步骤以上述相同的方式使用新学年的数据。实验一：将本文提出的算法与每个在线学习算法（朴素贝叶斯、１－ＮＮ、ＷＩＮＮＯＷ）进行比较。本文通过调整任一算法的特定数据集来最小化任一专家系统偏见的影响，尽可能使用学习参数的缺省值，这样可能导致较低的估计误差率，但可能会影响所有学习算法的偏置，表中的ＷＲＩ－１标记的行表示预测精度。从表可以明显看出，依照ｐ＜０．０５的ｔ－测试，本文提出的集成算法的分类精度优于其它各个分类器。总的来说，本文提出的集成算法在四个测试步骤的四个输出上明显比ＷＩＮＮＯＷ算法更精确，此外，本文提出的算法在四个测试步骤的两个输出上明显比１－ＮＮ算法更精确，而且，本文提出的算法在四个测试步骤的一个输出上明显比ＮＢ算法更精确。实验二：将本文提出的集成方法与每一批先进的机器学习技术的代表性算法进行了比较。批算法是用于测量学习算法精度的上层算法，大部分批算法的增量版本都不是无损的，无损在线学习算法就是当给定同一个训练集时，这个算法会返回一个假说，与它对应的批算法返回的相同。Ｃ４．５算法是一个决策树代表性算法，ＲＢＦ算法是一个众所周知的估计神经网络权重值的学习算法，是神经网络的代表性算法，本研究中，３－ＮＮ算法结合了强鲁棒性噪声，ＲＩＰＰＥＲ是规则的代表性学习者，最后，序贯最小优化算法（ＳＭＯ）是ＳＶＭｓ的代表性算法，表中ＷＲＩ－２、ＷＲＩ－３、ＷＲＩ－４标记的行表示每个算法的预测精度。表明显地表示出本文提出的集成方法在四个测试步骤的一个输出上明显比ＲＢＦ、ＢＰ和ＳＭＯ算法更精确，此外，本文提出的算法在四个测试步骤的两个输出上明显比３ＮＮ算法更精确，本文提出的算法在四个测试步骤的一个输出上明显比ＲＩＰＰＥＲ和Ｃ４．５算法更精确，最后，本文提出的算法在四个测试步骤的四个输出上也明显比投票感知方法更精确。实验三：将本文提出的方法与几个众所周知的集成分类器进行了比较，必须提到的是其他集成方法只能用于批模式，本文使用批集成作为测量集成方法精确度的上层算法。第三个实验用于比较：

１）Ａｄａｂｏｏｓｔ决策树桩算法和１０次迭代算法，

２）有１０颗树的随机森林集成算法，

３）投票感知器算法，

４）带Ｃ４．５的旋转森林算法和１０次迭代算法。表４明显地表示出本文提出的集成方法在四个测试步骤的一个输出上明显比其他测试的批集成方法更精确。从表可以看出，正如之前提到的，本文提出的集成方法的主要优点是它能很容易地适用于在线环境，不仅相同ＷＲＩ的新标记变得可用，而且下一个ＷＲＩ的标记也可用，如果本文已经使用了另一个测试学习者和集成方法，那么当下一个ＷＲＩ的标记变成可用时，应该从零开始重新训练分类器。实验四：将本文的数据集中所有算法都用于批学习者，表５给出了训练时间。从表５可以明显看出，增量更新将比在目前所见的所有数据上返回一个批算法快得多，它甚至可能是仅有的办法，如果不能存储目前所见的所有数据或者如果实时时间内需要执行在线预测和更新，至少它是非常迅速的。最大限度减小所需的训练时间是学者们非常感兴趣的事，正如前面提到的，数据分析主要的研究领域是可用于数以百计训练实例问题的精确度技术的探索。

５结语

本文提出了一种使用投票方法结合三个在线分类器的集成算法：朴素贝叶斯、１－ＮＮ和ＷＩＮ－ＮＯＷ算法，通过非常精确的预测，老师有能力知道哪些学生能完成模块或课程，这个预测初始精度为７３％，基于学生的人数统计数据，在期末考试前达到８２％。数据集来自模块“信息介绍”，但结论是可推广的，目前引起了学者们对ＨＯＵ大部分模块广泛的研究兴趣。实验结果表明，相比几种较为先进的分类器，本文提出的分类集成算法能够更加准确地预测学生的表现。

作者：冯莉 单位：厦门城市职业学院人文社科与艺术系动漫教研室