基于决策树的在线学习行为分析

王士霞

(新乡医学院临床技能培训中心,河南新乡453003)

基于决策树的在线学习行为分析

王士霞

(新乡医学院临床技能培训中心,河南新乡453003)

利用决策树算法出色的数据分析能力和直观易懂的结果展示等特点,采用C4.5算法挖掘学生在线学习行为与学习效果的历史数据.为避免决策树“过拟合”问题,在已生成的决策树上采用PEP方法进行剪枝,并构建学习分析模型.最后,利用建立的分析模型对测试数据集进行评估,得到了较为理想的分类预测结果.学习分析模型的创建为科学、合理地评估学生在线学习行为提供了有效的方法和手段,同时也给教学设计和课件开发提供了参考性建议.

数据挖掘;决策树;C4.5;在线学习行为

随着网络开放课程的普及和学习技术系统的发展,在线学习行为越来越多地发生在各种教育情境中,也给我们带来了大量的学习行为数据.如何利用海量的大数据提高学习效果,辅助在线教学日益成为教育者和学习者共同关注的话题,由此,学习分析技术应运而生.在新媒体联盟发布的《2013年地平线报告》中[1],学习分析(Learning Analysis)技术被排在未来五年内影响高等教育的六大信息技术的第一位[2].如何构造高效的数据挖掘算法去发现和理解隐藏在数据背后的信息,成为学习分析技术中成为最核心的问题.

决策树(Decision Tree)起源于概念学习系统CLS(Concept Learning System),它从一系列无规则、无次序的事例中推理出决策树表示形式并形成相应的分类规则[3],是从数据中生成分类和预测器的一种快速、有效的方法.C4.5算法[4]是Quilan于1993年提出来的,它改进了ID3算法的不足,引入了新的方法和功能,如:提出了连续属性的离散化处理方法;通过信息增益比例的计算来选择特征属性,使其适用于缺少特征值的训练样本的情况,同时解决了信息增益偏向于选择特征取值较多的问题;在决策树构造过程中或者构造完成之后,为避免树的过度拟合使用相应的修剪技术;引入K交叉验证用来选取局部最优解.该算法因其具有较高的算法精度、较强的适应性等特点得到了广泛应用.本文通过对学生在线学习行为进行监控,采用决策树分类算法C4.5对获得的学习行为数据进行评估,挖掘分析在线学习行为与学习效果之间的内在联系,实现学习过程的智能评价,为学习者合理安排在线学习提供指导性意见.

1 C4.5决策树算法

C4.5是机器学习算法中的一种分类预测算法,其总体框架可以分为两步:第一步是基于训练数据集构建分类预测模型,包括建树(Tree Building)和剪枝(Tree Pruning)两个阶段组成;第二步是将测试数据集应用于该模型,输出分类预测结果.其中第一步建立用于分类预测的决策树模型是最重要的工作.

1.1 C4.5决策树的建立

设训练数据集T的类标号属性具有m个不同值,定义m个不同类Ci(i =1,2,...,m).其中某属性A有v个不同值,属性将集合T划分为v个子集{T1,T2,...,Tv}.属性A的信息增益可表示为

C4.5决策树形成算法通过递归的过程由给定的训练数据产生一棵决策树,算法C4.5 FormTree(T,A)的伪代码如下,其中,T表示样本集,候选属性集用T_attributeList表示.

1.2 C4.5决策树的剪枝

C4.5决策树的剪枝策略的主要目的是避免决策树过拟合(Overfitting)样本.通常采用的策略是后剪枝方法[5],即在已生成过拟合决策树上进行剪枝,对那些置信度不够的子树节点用叶节点来替代.悲观剪枝(PEP,Pessimistic Error Pruning)方法采用自顶向下的剪枝策略,使它与其他方法相比效率更高、速度更快而被广泛使用.

PEP为了提高对测试集合的预测可靠性,对误差估计进行了连续性校正.对于训练集数据生成的原始树T,若

2 基于C4.5决策树的在线学习行为分析方法

本文所使用的数据来自于新乡医学院网络教学综合平台2014年《计算机基础》课程所采集的学生在线学习行为数据,共1 200条.采用保持法随机将此数据集的2/3作为训练数据集,其余的1/3作为测试数据集.应用C4.5算法对学生在线学习行为数据进行挖掘分析,找出学习行为与学习评价结果之间的联系,生成表达式规则,构建学习行为分析模型,以此来评估学生在线学习行为,评价模型如图1所示.

图1 学习行为分析模型Fig.1 Analysis model of learning behavior

2.1 学习行为特征数据的提取

新乡医学院所使用的网络教学平台为我们采集了学习者使用学习平台产生的各种访问及交互信息,如果所有行为数据均参与计算,将会大大降低分析的效率.考虑到课程特点及数据项之间存在依赖关系,选择提取以下数据建立学习行为特征数据库:用户识别(ID)、进入课程次数(LOGS)、课程讨论区发帖次数(POSTS)、阅读课程教学材料次数(READS)、上交作业次数(WORKS)、在线时长(TIME)、考试成绩(GRADE),表1为部分输入数据.

表1 部分输入数据Tab.1 Part of the input data

2.2 数据预处理

C4.5算法作为对ID3算法的改进,增加了将连续型属性进行离散化的功能:

(1)将节点上的数据样本按照属性的取值进行排序,将该连续型属性的最小值赋值给MIN,其最大值赋值给MAX;

(2)生成区间[MIN,MAX]中的N个等分断点,它们分别是

(3)分别计算把[MIN,Ai]和(Ai,MAX](i=1,2,...,N)作为区间值时的Gain值;

(4)选择其中Gain值最大的分割阈值作为属性Ak的最佳分割阈值,把属性值设置为[MIN,Ak]和(Ak, MAX]两个区间值.

上述连续型属性进行离散化的过程中,需要对所有划分情况进行预测.当训练集中连续型属性数量较多且取值也较多时,算法的计算量巨大,而影响了决策树的生成效率.Fayyad等证明:无论用于学习的训练集中的数据有多少个类别,不管类别的分布如何,连续型属性的最佳分割点总是在边界点处[6].根据Fayyad的边界点原理,姚亚夫等改进了原有算法,只在连续属性分界点处的少数几个分割点中选择最佳分割阈值[7],从而提升了C4.5算法处理连续属性的性能,本文利用姚亚夫构造的分类器将连续属性进行离散化预处理,得到待挖掘的输入数据.

2.3 生成决策树及分类规则

生成决策树的具体计算过程如下:

(1)依次计算每个属性的信息增益以及信息增益率.

(2)选取信息增益率最大,且信息增量不低于所有属性平均值的属性作为测试属性.从上述计算结果可知,READS属性具有最高的信息增益率,以该属性作为节点,属性的每一个分布引出一个分支,据此再划分样本.如果节点中所有样本都在同一个类,则该节点成为树叶.

(3)对划分的每个子数据集递归执行(1)-(2).当子集中再无属性可供划分,或数据记录在主属性上的取值相同时停止,从而形成完全决策树.

为避免决策树“过拟合”问题,在已生成的决策树上采用PEP方法进行剪枝,得到最终的决策树模型.从根节点到叶节点的每条路径创建一条规则,以IF-THEN形式形成分类规则,将决策树转化为等价的规则集合.

2.4 模型正确性评估

构建此模型的目的是对学生的在线学习行为进行预测分析.因此,利用生成的分类模型进行准确性评估,对测试数据集中的未知数据进行预测,通过比较测试结果与实际情况相吻合的程度来判断该决策树是否有效.

用于测试的样本数据集为400个,使用构建的分析模型对测试数据集进行评估,得到的分类准确率的结果如表2所示.通过对数据集的测试评估,总的预测分类正确率达到87.80%.检测结果表明,利用C4.5算法进行数据挖掘所得到学习行为分析模型对未来数据样本的分类预测正确率能够达到基本要求.

表2 测试数据集评估结果Tab.2 Evaluation results of test data set

3 小结

本文根据学生在线学习行为数据的特点,使用决策树分类方法中的C4.5算法进行决策学习和规则提取,构建了学习分析模型,预测学习结果.通过测试数据集的评估,得到了较为理想的分类准确率,为进一步研究在线学习分析技术提供了有效的方法和手段.

[1]JohnsonL,AdamsS,CumminsM.TheNMCHorizonReport:2013HigherEducationEdition[R].Austin,Texas:TheNewMediaConsortium.

[2]Siemens G.1stInternational conference on learning analytics and knowledge 2011[EB/OL].(2010-07-12)[2014-10-15]. https://tekri.athabascau.ca/analytics/about.

[3]Quinlan J R.Induction of decision trees[J].Machine Learning,1986,1:81-106.

[4]Thakur D,Markandaiah N,Raj D S.Re optimization of ID3 and C4.5 decision tree[C].International Conference on Computer and Communication Technology,2010:448-450.

[5]Kantardzic M.Data mining:Concepts models,and algorithms[M].New York:John Wiley and IEEE Press,2003:139-164.

[6]FayyadUM,IraniKB.Onthehandlingofcontinuous-valueattributesindecisiontreegeneration[J].MachineLearning,1992,8(1):87-102.

[7]姚亚夫,邢留涛.决策树C4.5连续属性分割阈值算法改进及其应用[J].中南大学学报:自然科学版,2011,42(12):3772-3776.

（责任编辑：卢奇）

Behavior analysis of online learning based on the decision trees

WANG Shixia
(Department of Clinical Skills Training Centre,Xinxiang Medical University,Xinxiang 453003,China)

Along with the continuous popularization of online learning,online learning,like a treasure behavior,is hidden in the Network platform.A reasonable mining technology was need to discover and use it.Based on the characteristics of the decision tree like algorithm good data analysis ability and intuitive result display,the C4.5 algorithm was used to explore the historical data of students'online learning behavior and learning efficiency in this paper.In order to avoid the over fitting problem of the decision tree,the decision tree that has been generated using method of PEP was pruned,and construct learning analysis model.Finally,the test data was evaluated by using the established analytical model,and obtained the comparatively ideal classification forecast result.The establishment of the learning analysis model provides an effective method and means for the scientific and reasonable assessment of students'online learning behavior,but also provides a reference for teaching design and courseware development.

data mining;decision tree;C4.5;online learning behavior

TP393.08

：A

：1008-7516（2015）05-0067-04

10.3969/j.issn.1008-7516.2015.05.014

2015-07-06

河南省教育厅人文社会科学研究项目(2015-GH-089)

王士霞(1977-),女,河南新乡人,实验师.主要从事数据挖掘与分析研究.