决策树C4.5算法分析及其在多媒体网络教学评价中的应用

王新华,焦玉琳,冯先强

(1.商丘职业技术学院,河南 商丘 476000; 2.武汉理工大学,湖北 武汉 410076)

决策树C4.5算法分析及其在多媒体网络教学评价中的应用

王新华1,2,焦玉琳1,冯先强1

(1.商丘职业技术学院,河南 商丘 476000; 2.武汉理工大学,湖北 武汉 410076)

C4.5算法是决策树学习的核心算法,与ID3算法相比, C4.5算法是ID3算法的改进,并继承了ID3算法的全部优点,文章给出了决策树构造思想和C4.5决策树学习算法,并将其应用于多媒体网络教学评价之中,采用C4.5决策树算法对教学评价数据进行预处理,选取决策属性,实现挖掘算法并抽取规则知识,C4.5算法能够更好地修正ID3的剪枝算法,并将多媒体网络教学评价进行分类,算法简单且生成速度快,通过生成的决策树,生成可理解的规则.

决策树;C4.5；多媒体；网络教学；评价

近几年国内外，数据挖掘广阔的应用前景得到了商业圈及众多学者的认可，在信息产业界也引起了振荡，通过数据挖掘将有大量的数据转换为专用的信息.数据挖掘根据模式的作用可分为分类、回归、聚类、时间、序列等.分类在数据分析方法中是最重要的，解决的方法也很多，其中决策树是最深入的、应用最广泛的方法之一[1]56.

在当今互联网时代，多媒体网络教学已应用十分广泛，但多媒体网络教学评价的研究有所滞后，对多媒体进行网络教学评价中科学、客观、准确的总结不足[2]46.多媒体网络教学评价具有一定的复杂性、模糊性及多因素性，如何正确地反映出问题，总结出优势是当前的迫切任务和课题.本文利用决策树C4.5算法，对数据进行挖掘来研究多媒体网络教学的评价问题.

1 数据挖掘决策树算法

在数据挖掘方法中，决策树算法是解决实际问题的常用方法之一，在数据挖掘模式中，分类是把数据项映射到一个定义类的过程，由相应的类和输入的属性值向量构成.分类器是一个在其他属性已知的样本下预测另一个属性的模型[3]87-90.

在数据中来生成分类器最有效的方法是生成决策树.而生成决策树的算法主要有6种，即ID3算法、C4.5算法、算法IBLE算法、CHAID算法、Cs算法、CART(分类与回归树)[4]46-50.C4.5算法是一种简而易懂的决策树算法，它是在ID3的基础上进行一定的完善，弥补了ID3中的不足，采用了信息增益率来作为属性选择的衡量标准，进行决策节点属性的选择，但算法的基本方法与工作流相同，这也是决策树算法的基本思想[5]125-126.

决策属性信息增益算法在C4.5中：

设事例样本类标号Ci，i=i,…,n,事例集合为T，则信息熵为：

|T|—带表事例集T的样本个数，frequ(Ci,T)—表示事例集合T中事例属于类Ci的数目.

假设选择y个不同值的属性w，则条件熵可表示为：

|Ti|—基于属性w的某个值的子树中每一类例子的数目.

则信患增益即互信息为:

Gain(W)=info(T)-Ew

C4.5采用标准化处理程序中，当有很多不同属性值，采用启发式搜索方法最有效，信息增益率(gainratio)方法具有更好的信息增益的属性[6]946-948.但也会导致最大信息增益gain属性W作为扩展属性来分枝.信息增益率被定义为：

式中

是利用属性W的值对数据进行挖掘，分枝计算出潜在信息.

在选择相应的错误率上C4.5采用了信息增益率作为分枝准则.信息增益率与分支产生的有用信息成正比.分枝包中含有的信息越多，信息增益率越大.

2 树修剪

基本的决策树算法是没有去噪声的，构造生成的决策树完全同训练样本相同.修剪的核心技术就是克服噪声，使决策树简单易理解.

决策树采用分而治之策略, 自上而下的生成过程, 与此同时降低算法的时间复杂度, 忽视各类样本的总体分布对噪声的敏感性.可以非常准确地反映一个完整的决策树训练样本数据集的特征数据[7]39-42.

但是,不能用于新数据的分类和预测,会出现过匹配或过时适应数据.当这个模型应用到新的测试集将导致不准确的预测，所以一个完整的决策树结构还应该包括决策树剪枝.决策树剪枝就是避免决策树过度拟合.

树修剪有两种常用的修剪方法:

1)预剪枝：就是指预先确定最大深度的决策树生长，过大过小都会抑制它的生长，同时也无法实现新数据的预测或准确分类.

2)后剪枝：即在充分生长的基础上允许决策树在T规则下,剪去没有代表性的分枝或叶节点.根据检测和训练样本集对目标变量精度进行计算修剪[8]20-21.

3 决策树C4.5算法

将多媒体网络教学评价分为6项体系指标，即J1(教学方法)、J2(教学态度)、J3(教学质量)、J4(教学效益)、J5(教学效率)、J6(教学评价).如表1所示.A代表评分为90～100，B代表评分为80～89，C代表评分为70～79，D代表60～69，E代表评分小于60分，F代表评分小于40分，J6为结论.

表1 多媒体网络教学评价指标体系

训练样本数据集S中，共有10个元组，有6个类别分别是优秀、良好、中等、一般、较差、非常差，对多媒体网络教学评价方法，采用数据挖掘是为了使教学水平得到提高，这里我们选用优、良、中、及格进行分析，此4个对应类别的子集元素个数分别为：r1=4,r2=2,r3=3,r4=1.

为计算决策属性信息增益，这里先计算期望信息量：

则单个期望信息量计算：

以J1为例：

E(SA)=0.9183

E(SB)=1.5

E(SC)=0

E(SD)=1

Gain(S,J1)=I(r1,r2,r3,r4)-E(S,J1)=1.8465-1.0755=0.771

因此,属性J1的信息增益率为

Ratio(J1)=Gain(J1)/E(S,J1)=0.771/1.0755=0.7169

同理可得:

Ratio(J2)=Gain(J2)/E(S,J2)=1.0465/0.8=1.3081

Ratio(J3)=Gain(J3)/E(S,J3)=0.8465/1=0.8645

Ratio(J4)=Gain(J4)/E(S,J4)=0.9135/0.9510=0.9606

Ratio(J5)=Gain(J5)/E(S,J5)=0.989/0.8755=1.1296

由上述计算结果可知J2属性中具有最大的信息增益比.最后所构造的判定树如图1所示.

4 决策结论描述

由图1所得C4.5算法构造多媒体网络教学评价决策树，可方便快捷地提取决策树描述从根节点到叶节点所有路径都对应相应的决策规则.

描述如下所示:

1)if(A2=C)thenA6=中等

2)if(A2=D)thenA6=及格

3)if(A2=A&&A3=A)thenA6=优秀

4)if(A2=A&&A3=B&&A4=B)thenA6=良好

5)if(A2=A&&A3=B&&A4=A)thenA6=优秀

6)if(A2=B&&A3=A)thenA6=优秀

7)if(A2=B&&A3=B)thenA6=良好

8)if(A2=B&&A3=C)thenA6=中等

5 结论

决策树是数据挖掘中一个常用的算法工具,数据挖掘是一种新的数据分析技术,本文研究了分类方法中常见的C4.5决策树算法,C4.5算法是在ID3的基础上改进而成的,它更好地修正了ID3的剪枝算法,并对高分支属性、数值型属性和含空缺值属性的整理有了系统的描述,C4.5决策树算法简单而且生成速度也比较快,通过生成的决策树,可以生成可理解的规则.在决策树中可以大致地判断出属性之间的相对重要性.决策树C4.5算法分析应用在多媒体网络教学评价中，将更好地为网络教学服务，科学客观地评价，使多媒体网络教学评价技术更上一个台阶.

[1] Han Jiawei,Kanber Micheline .数据挖掘概念与技术[M].北京:机械工业出版社,2002.

[2] 戴 南.基于决策树的分类方法研究[D].南京:南京师范大学,2003.

[3] 李雄飞,李 军.数据挖掘与知识发现[M].北京:高等教育出版社,2003.

[4] 张云涛,龚 玲.数据挖掘原理与技术[M].北京:电子工业出版社,2000.

[5] 王中辉,鲁来凤.决策树在教学评价中的应用[J].甘肃科技，2006(3).

[6] 范 洁,杨岳湘,温 璞.C4.5算法在在线学习行为评估系统中的应用[J].计算机工程与设计，2006(3).

[7] 彭松波,何文秀.决策树在高校就业管理系统中的应用研究[J].中原工学院学报，2006(8).

[8] 谷 琼,朱 莉,蔡之华,袁红星.基于决策树技术的高校研究生信息库数据挖掘研究[J].电子技术应用，2005(7).

[责任编辑 冰 竹]

Decision-Tree C4.5 Algorithm Analysis and Its Application in Multimedia Network Teaching Appraisal

WANG Xinhua1，2, JIAO Yulin1, FENG Xianqiang1

(1.ShangqiuPolytechnic,Shangqiu476000,China;2.WuhanUniversityofTechnology,Wuhan430063,China)

The C4.5 algorithm is the decision tree study core algorithm. Compared with ID3 algorithm, C4.5 algorithm is an improved ID3 algorithm, and it inherited the entire ID3 algorithm's merit. This article has given the decision tree structure thought and the C4.5 decision tree study algorithm, and applies it during the multimedia network teaching appraisal. The paper uses the C4.5 decision tree algorithm to preprocess the data and chooses the decision attributes first, then draws the rules, which shows that what attributes determine the classification of the multimedia network teaching appraisal. The results of data mining indicate that the algorithm can classify the teaching appraisal data properly and get some valuable information for decision making.

decision-tree; C4.5; multimedia; network teaching; appraisal

2015-09-07

河南省重大科技攻关计划项目(项目编号：142102110028)

王新华(1970- ),男,河南商丘人，商丘职业技术学院副教授，在读博士，主要从事智能控制与节能技术研究。

1671-8127(2015)05-0016-04

TP18

A