基于ID3算法的质量保证体系数据关联度研究

2018-12-08曹安林

网络安全技术与应用 2018年12期

◆曹安林

◆曹安林

（南京机电职业技术学院江苏 211135）

高等职业院校建立质量保证体系是社会主义市场经济发展的需求，是区域经济发展和行业企业发展总趋势。为社会培育大量高素质应用型技能人才是高等职业院校最基本的人才培养方案和目标。目前，基于网络的综合教学管理信息系统得到了各高等职业院校的广泛应用，在这些管理信息系统的使用过程中，积累了大量的原始数据，然而这些数据只是静态的储存在数据库中，没有进行深层次的分析并有效利用，不能不说是一种浪费。如何从这些原始数据中发现并提炼出有用的信息，精准的对数据进行分析，并将分析结果加工成有效的信息供管理层决策使用，已经成为了高职院校质量管理与控制体系的应用需求。

ID3算法；质量保证；数据关联

0 前言

目前，基于网络的综合教学管理信息系统越来越广泛的应用在高职院校，系统中数据基本涵盖了《高等职业学校设置标准（暂行）》（教发〔2000〕41号）规定的所有办学指标。单纯就某一所高职院校来说，利用人工计算和比对的方式核准办学指标相对容易，一旦数据中包含了大量院校信息时，人工方式将很难保证准确性和完整性。因此本文以南京机电职业技术学院为案例，将数据挖掘技术的ID3算法归纳决策树扩展到建立高职院校的质量管理与控制体系，达到应用创新的目的。主要研究内容如下：

1 科学的对基本数据库中数据进行预处理

如何对基本数据库中的数据进行预处理，主要采用决策树的算法分析。决策树是数据挖掘分类算法的一个重要方法，是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。

生成决策树是采用自上而下的递归构造方法。它的输入是一组带有类别标记的训练数据集合，结果是一棵二叉树或多叉树。决策树如果依靠数学的计算方法可以取得相对更加理想的效果。例如：

决策树的生成过程主要是依据对于数据源的采集分析，对数据源进行分类测试，在整个过程中进行单一方向的或者是多个类别的测试和修剪，当一个数据决策树不能再进一步分割或修剪的时候，对于数据来说整个生成过程也就完成了，也达到了基本数据预处理的目标。

2 ID3算法下的决策树的剪枝

通常在实际应用中，直接生成的决策树并不能立即用于对未知样本来进行分类和应用。由于训练数据集合存在噪声，无法实现对新样本的合理分析，这种条件下，必须要对决策树进行后期处理——即决策树的剪枝处理。这样才能有效的控制和掌握决策树的发展规模，进而提高预测精度，同时也变得更容易理解。

当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶节点都是纯的——这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶节点不纯（这意味着我们要以一定的概率来做出决策）。

高职院校的质量管理与控制体系数据覆盖面比较广，包含种类较多，然其中大部分数据指标以定性属性为主，即离散型训练数据集合为主，计算量相对来说并不是很大。选用ID3算法归纳决策树方法用于质量保证体系数据挖掘系统是较为合适的算法。

3 基于ID3算法的质量保证数据关联分析

ID3采用自顶向下不回溯的策略搜索全部的属性空间，它建立决策树的算法简单，深度小，分类速度快，相对适宜计算量较小的培训数据集合。其关键在于选取“各个决策属性中可对训练数据集合进行最佳分类的属性”，自上而下的归纳成一组if_then规则，所以计算各个决策属性的信息增益并加以比较是ID3算法的关键步骤。其基本算法如下伪代码描述：

Define：Decision_Tree（samples，attribute_list）；

Input：具有离散型属性的训练数据集合samples、决策属性集合attribute_list

Output：一棵决策树。

Function：

（1）创建根节点N；

（2）if samples同为类C then；

（3）return N作为叶节点，以C标记；

（4）if attribute_list = null then;

（5）return N作为叶节点，标记为samples中最普通的类；

（6）选择attribute_list中具有最大信息增益的决策树性test_attribute；

（7）标记N为test_attribute；

（8）switch case each test_attribute中已知的值；

（9）节点N生长出一个条件为test_attribute的分支；

（10）设置Si为samples中test_attribute=Ai样本的集合；

（11）if Si=null then；

（12）生成一个叶节点，标记为samples中最普通的类；

（13）else加入由Decision_Tree（Si，test_attribute）返回的节点。ID3通过不断的递归方式，逐步精确决策树，直到找到一棵完全正确的决策树。

其数学理论依据：

（5）信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为：

出来的分支。根据有A划分成子集的熵为：

分类后，分类的信息量计算公式为：

其中：

综上所述，信息增益为：

根据贪心算法，为使下一步所需的信息量最小，则要求每一次都选择信息增益最大的属性作为决策树的新节点。

下面，通过一个具体实例来说明其具体应用过程。学校部分专任教师信息数据：

表1 专任教师信息表

选取部分专任教师职称作为类别标识属性，其他属性为决策属性，图1是一棵关于“专任职教师是否具有高级职称”的决策树的子树示意图：

图1“专任教师是否具有高级职称”决策树示意图

设训练数据集合S，S中共有14条记录，其中职称分为初级、中级、高级（含副高级）三种，决策属性数据量相对较为平均，所以套用公式3计算S的期望信息量：

接下来根据公式9计算每个一个决策属性的信息量，也就是熵，以年龄为例，将年龄分为30～40之间、40～50之间、50以上三个区间，当年龄为30～40之间时：

当年龄为40～50之间时：

当年龄为50以上时：

由此得到年龄的熵为：

所以根据公式11年龄的信息增益G（Age）为：

同理可得性别信息增益G（Sex）=0.0266、学历信息增益G（Education）=0.4926，当训练数据集合扩大到全校400名教职、教辅员工时得到的性别信息增益G（Sex）为0.0054，而对于其他的决策属性大小次序未发生改变，由此可以看出性别对于教师的职称属性几乎不存在影响，所以在对图1所示的决策树中删除性别决策属性，因为G（Age）值最大，所以选择年龄作为决策树的根节点，对每一个分支进行递归计算，进行剪枝，剪枝后的决策树如图2所示：

4 总结

利用ID3算法对高等职业院校的教育教学进行质量的管控分析，并不是提出改进算法为目的。因此如何通过ID3算法构造一棵最简决策树是整个项目中最核心的部门，同时决策树的剪枝问题是决策树技术中一个重要的部分。ID3算法能利用直观的算法描述、数学描述ID3在构造决策树以及剪枝的详细过程，同时结合案例进行实例化操作，对建立学院质量保证体系关键数据的确立起到很大的指引作用。