改进的ID3算法在远程教学系统中的应用

王建伟，王 鑫，许宪东，李慧君，黑 龙

(黑龙江工程学院 计算机科学与技术学院，黑龙江 哈尔滨 150050)

改进的ID3算法在远程教学系统中的应用

王建伟，王 鑫，许宪东，李慧君，黑 龙

(黑龙江工程学院 计算机科学与技术学院，黑龙江 哈尔滨 150050)

当前，远程教学系统缺少智能性，不能提供个性化教学，引入ID3算法后可以根据学习者的特征对其分类，从而实现对不同学习者的针对性教学。然而传统的决策树ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实。运用一种基于灰色关联分析的修正因子属性选择方法予以改进，对取值较多但灰色关联度低的属性，在计算其信息增益时通过灰色关联度的正弦值作为修正因子，克服传统ID3算法的不足。将改进的ID3算法引入到远程教学系统中，可以更好地对学习者进行分类以实现智能化导学。

ID3算法；决策树；灰色关联度；修正因子；远程教学系统

传统的远程教学系统通常以系统本身为中心，只能对不同的学生提供完全相同的学习材料和学习任务，缺乏智能性[1]。而数据挖掘技术可以从远程教学系统的海量数据中发现一些潜在的、有价值的规律,这无疑为智能化、个性化的网上学习提供了强有力的支持[2]。针对传统网上学习系统的弊端，本文使用决策树ID3算法根据学习者考试成绩对其分类，实现智能化导学。但由于ID3算法存在着一些缺陷，故在原有算法基础上加以改进成为GBID算法，算法改进后无论从算法效率还是分类的精确性上都得到了很大改善，从而更好地实现远程教学系统的智能性。

1 ID3算法分析

ID3算法是Quinlan在1986年提出的一种基于信息熵的决策树学习算法。信息熵是信息的量化度量，而信息增益是两个信息熵的差，代表在消除不确定性后获得的信息量[3]。ID3算法实际上就是一个贪心算法，它采用由上而下、分而治之的递归方式来构造决策树。该算法的核心是[4]：在决策树各级节点上选择属性的时候，通过计算信息增益来选择最佳的分裂属性。首先选择信息增益值最大的属性作为根节点，然后根据此根节点的不同取值创建分支，同时也对应着一个被划分的子集，再对各子集递归调用ID3算法来建立决策树的节点分支直至整个决策树生成。

ID3算法的具体描述如下[5]：假设S是s个数据样本集合。假定类标号属性具有n个不同的值,定义n个不同类Ci(i=1,…,n)。设Si是类Ci中的样本数。对一个给定的样本分类所需要的期望信息给出公式为

(1)

式中：Pi是任意一个样本属于Ci的概率,并用Si/s估计。

设属性A具有k个不同值{a1,a2,…,ak}，用属性A将S划分为k个子集{S1,S2,…,Sk}，其中,Sj包含S中这样一些样本,他们在A上具有值aj。如果把A选则为测试属性(最好的分裂属性),则这些子集对应于由包含集合S的节点生长出来的分枝。Sij是子集Sj中类Ci的样本数。根据由A划分成子集的熵或期望信息给出公式[6]

(2)

(3)

Gain(A)=I(s1,s2,…,sn)-E(A).

(4)

Gain(A)是由于知道了属性A的值而导致的熵的期望压缩。通过该算法计算每个属性的信息增益。将具有最高信息增益的属性选作给定集合S的分裂属性。创建一个节点,并以该属性标记,对属性的每个值创建分枝,并据此划分样本[7]。

作为决策树的一个经典构造算法，ID3算法的优点在于：搜索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险；算法的基础理论比较清晰，在属性选择时利用了信息增益的概念；决策树的每个分支都对应一个分类规则，可以生成容易理解的IF-THEN分类规则，因此，产生的分类规则直观性强，易于理解。但是通过近些年国内外学者对ID3算法的研究也发现了一些不足：计算信息增益时倾向于选择具有多值的属性，这样不太合理，因为在很多情况下取值较多的属性并不总是最优的属性；在构造树的过程中，需要多次自上而下对数据集的排序和扫描，因而导致算法的处理效率较低[8]。

2 基于灰色关联分析的修正因子

灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法，其基本思想是通过确定参考数据列和若干个比较数据列的几何形状相似程度来判断其联系是否紧密，它反映了曲线间的关联程度[9]。首先求得两者的关联系数，由关联系数得到关联度，再按照关联度的大小进行排序、分析，得出结论。灰色关联分析通过一定的方法，找到系统中两个因素变化的态势来判断它们之间的关联程度。如果两者变化同步程度高，则可以认为两者关联较大；反之，则两者关联度较小。因此，灰色关联分析对于一个系统发展变化态势提供了量化的度量，非常适合动态的历程分析[10]。根据灰色关联分析的方法来计算特征属性与分类属性的关联度并取其正弦值作为修正因子，重新计算ID3算法中属性的Gain值，通过这样的方式来解决ID3算法中的多值偏向问题。使用灰色关联分析的方法计算修正因子的方法如下：设训练数据集T有样本个数为n，类别属性记为C，特征属性为m个且分别记为Xi(i=1,2,3,…，m)，则按照灰色系统理论，比较各属性之间的关系，计算两者的关联度。为此，假设n个样本的类别属性值构成一灰色序列：C={C(1),C(2),…，C(n)};n个样本的各特征属性值也构成一个灰色序列:Xi={Xi(1),Xi(2),…,Xi(n)}(i=1,2,…,m)。则特征属性序列Xi与类别属性序列C在第k个点(样本)的灰色关联系数定义为

(5)

(6)

灰色关联分析是将各因素统一放在一个系统中进行比较和分析，因此,它考虑了各因素之间的相关性，比系统分析中常用的因素两两对比法更合理、更科学。考虑到系统中类别属性序列曲线与特征属性序列曲线的紧密程度可用灰色关联度的大小来描述，即灰色关联度最小的特征属性对系统类别属性的影响也最小；反之，灰色关联度大的特征属性对系统类别属性的影响相对要大。所以，对于取值较多但灰色关联度较小的特征属性对分类结果影响不大，显然也不是最优属性。另外，考虑到正弦函数的曲线变化比较缓和，对信息增益因子修正不会出现过度的问题。因此，本文引入灰色关联度的正弦值作为ID3算法的修正因子进行改进。

3 改进的ID3算法

改进算法GBID的具体流程是：

1)计算各特征属性与类别属性之间的灰色关联度，并将它们排序；

2)对取值较多的属性通过灰色关联度判断是否最优，从而确定是否降低它的信息增益；

3)对取值较多但灰色关联度低的属性，在计算其信息增益时通过灰色关联度的正弦值作为修正因子，而其它属性计算信息增益时修正因子设为0。

公式为

(7)

式中：CF(A)为属性A的修正因子，定义为

(8)

显然，0

Gain1(A)=I(s1,s2,…,sn)-E1(A).

(9)

GBID算法的描述如下：

算法：GBID(Sample_set，Attribute_set)

输入：由多个属性描述的训练样本集Sample_set；候选属性集Attribute_set。

输出：一棵决策树。

Begin

如果 Sample_set为空

则返回null；创建结点L；

如果结点L中的所有样本均属于同一类C

则返回L作为叶结点，并以类C为标记；

如果 Attribute_set为空

则返回L作为叶结点，并以Sample_set中最普通的类标记；

根据式(4)计算出Attribute_set中每个属性的信息增益，并选择出信息增益最大的属性A和取值个数最多的属性B;

如果A=B，该条件成立说明选择信息增益最大和取值个数最多的属性作为测试属性易产生多值偏向问题，需要用修正因子降低该属性的信息增益;

则根据式(8)来计算该属性的修正因子；

再根据式(9)重新计算该属性的信息增益；

否则该属性的修正系数为0，信息增益最大的属性不是取值个数最多属性，选择该属性作为分裂属性不会产生多值偏向问题，不需要用修正系数降低该属性信息增益；

从Attribute_set中选择出信息增益最大的属性Splitting _Attribute作为分裂属性；

标记结点L为Splitting _Attribute；

For Each Splitting_Attribute中的已知ai(i=1,2,…,m)；

m为Splitting _Attribute的取值个数∥根据Splitting _Attribute的取值划分Sample_set

根据Splitting _Attribute=ai，从结点L产生相应分支表示测试条件；

设Si(i=1,2,…,m)为Splitting _Attribute=ai所获得的样本集；

如果Si为空,

则加上一个叶结点，并标记为Sample_set中最普通的类；

否则加上GBID(Attribute_set,Splitting _Attribute)返回的结点；

End

4 利用GBID算法为学习者分类

下面以具体实验说明GBID算法的应用。

学习者考试成绩的特征属性课程类型A,B,C，量化为{0,1,2}；在线学习时间可分为较短、适中、较长，量化为{0,1,2}；试卷难度为难、易，量化为{0,1}；沟通能力为强、弱，量化为{0,1}；分类属性考试成绩以80分为界，大于80分为好，小于80分为不好，量化为{0,1}。根据训练集样本数据，依次根据式(6)计算各特征属性与分类属性的灰色关联度，结果为r(课程类型)=0.52，r(在线学习时间)=0.72，r(试卷难度)=0.78，r(沟通能力)=0.56，然后计算上述属性信息增益，可得Gain(课程类型)=0.481 6，Gain(在线学习时间)=0.027 5，Gain(试卷难度)=0.058 8，Gain(沟通能力)=0.036 8，因为课程类型的信息增益最大、取值个数最多但灰色关联度最低，所以需要用修正因子降低其信息增益，设定修正因子CF(课程类型)为sin(0.52)=0.496 8，而其它属性的信息增益设定为0，则GBID算法与ID3算法的比较如表1所示。

表1 GBID算法对考试成绩各属性信息增益的影响

由表1可以看出，ID3算法确定决策树的根节点时，选择信息增益最大的课程类型作为分裂属性，显然这与客观事实不符。而GBID算法在确定根节点时，选择试卷难度作为分裂属性，符合客观事实，避免了多值但非最优属性的课程类型成为分裂属性。

5 结束语

在远程教学系统中，利用GBID算法根据学习者考试成绩进行分类，克服了ID3算法多值倾向问题，使分类更加符合客观规律，以此为依据为不同的学习者提供不同的教学策略，真正实现针对每一个学习者的智能化导学。

[1]王鑫,王建伟,钟玉峰,等.个性化远程教学平台中数据挖掘技术的应用[J]. 黑龙江工程学院学报：自然科学版，2010(24):72-74.

[2]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京：机械工业出版社，2003:15-17.

[3]孙卫强.决策树方法在远程教育辅助教学中的应用研究[D].广州：中山大学，2010:22-25.

[4]陶灵姣,孙继银,李智.远程教育考试成绩分析决策树的构造方法[J].计算机工程与设计，2006(3):37-39.

[5]高红建,谢如鹤,李韩娟.决策分析模型评估客运服务质量的研究[J].黑龙江工程学院学报：自然科学版，2003(2):48-51.

[6]孟迎,冯丽辉,赵铁军.基于决策树的汉语基本名词短语识别[J].黑龙江工程学院学报:自然科学版，2004，6(2):1-4.

[7] 杨鸿宾.数据挖掘在个性化网络教学平台中的应用研究[D].北京：首都师范大学，2005:36-38.

[8]屠宏,吴宏江.数据挖掘在网络学习者学习特征分析系统中的应用[J].远程教育杂志，2004(5):16-18.

[9]陈登科,胡翠华.数据挖掘技术在远程教育中的应用[J].情报科学,2003,4(4):18-20.

ApplicationofimprovedID3algorithmtodistanceeducationsystem

WANG Jian-wei1,WANG Xin1,XU Xian-dong1, LI Hui-jun1, HEI Long1

(College of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin 150050, China)

Currently,the distance education system is lack of intelligence and cannot provide personalized teaching which can be classified according to the feature of different learners after introducing ID3 algorithm in order to realize the targeted teaching to different learners.There are multi-valued problems in the traditional decision tree algorithm ID3, and split attribute selecting does not conform to the objective facts.A feature selection method of correction factor is used based on grey relational analysis. The grey correlation sine value is selected as a correction factor when calculating the information gain for the properties of low value but more grey correlation degree to overcome the deficiency of the traditional ID3 algorithm.The introduction of improved ID3 algorithm can classify learners better to achieve intelligent tutoring.

ID3 algorithm；decision tree；grey correlation degree；correction factor；distance education system

2013-06-25

黑龙江省自然科学基金项目(F201224)

王建伟(1978-)，男,讲师,研究方向:远程教育;数据挖掘.

TP312

A

1671-4679(2014)01-0067-04

郝丽英]