决策树ID3算法在高校管理信息化中的应用分析

　　摘 要： ID3算法是决策树算法中最经典的一个算法。本文根据高校管理信息化的特殊性将模糊集理论知识与ID3算法相结合，应用到高校管理中，提高了ID3决策树分类的正确性，与ID3原算法相比，易于理解，决策树的构造更加准确和快速。
　　关键词： 决策树 ID3 模糊集 高校信息化 应用
　　
　　1.引言
　　自20世纪60年代以来，决策树方法在机器学习、知识发现等诸多领域有着广泛应用。J.R.Quinlan in在1979年提出的ID3决策树算法是最有影响的一种决策树生成算法，其思想是运用信息熵理论，选择当前样本集中具有最大信息增益值的属性作为测试属性，样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值，就将样本集划分为多少子样本集。用迭代的方法在相应的样本子集的节点上生长出新的叶子节点，直到无可分样本，无剩余属性或样本同属于一个类时结束。但此方法的决策树的知识表示没有规则易于理解。而且ID3算法信息增益的方法往往偏向于选择取值较多的属性，影响的分类预测的高效性。因此，我们对原有的ID3算法进行了改进，将模糊理论知识应用到ID3算法之中，提出一个新的从数值数据中生成一个决策树状图的算法。
　　我在此以某高校学生课程信息系统为基础，对其中积累的海量数据运用数据挖掘技术，实现挖掘算法——决策树ID3改进算法，并抽取规则知识，对高校中的学生的成绩进行了深入的分析和比较，找出影响学生学习的潜在因素和潜在有用价值，为教学管理和保持学生良好状态，提高学生成绩，促进学生全面发展提供参考，从而可以更好地开展学生工作，提高教学质量，促进学校发展。
　　2.ID3决策树算法
　　ID3决策树算法的核心思想是利用信息熵原理选择信息增益最大的属性为属性分类的标准，使用贪心算法递归地拓展决策树的分枝，进行决策树的构造［３］。
　　假设数据集空间中的正例集和反例集的大小分别为p和n，ID3算法基于以下两个基本假设：
　　（1）在数据集空间H上的一棵正确决策树对任意测试数据的分类概率同H中正反例的概率一致；
　　（2）一棵决策树能对测试集做出正确类别判断所需的信息量为：
　　I（p，n）=-ln-ln
　　如果以属性R作为决策树的根，R具有V个值（V，V，…，V），它将H分为V个子集（H，H，…，H），假设H中含有p个正例和n个反例，子集H的信息熵E（H）为：
　　E（H）=-ln-ln
　　以属性R为根分类的信息熵为E（R）：
　　Gain（R）=I（p，n）-E（R）
　　ID3选择使E（R）最小的属性作为根节点，对R的不同取值对应的H的V个子集H递归调用上述过程，生成R的子节点。
　　判定树归纳的基本算法是贪心算法，它采用自上而下、分而治之的递归方式来构造一个决策树。ID3算法是一种著名的判定树归纳算法。
　　3.模糊ID3决策树算法
　　ID3算法根据数据集的属性生成一棵决策树状图来进行数据的分类，我们的算法称为模糊ID3算法，应用了数据模糊集来生成一棵模糊决策树，模糊数据集是由用户为所有属性定义的模糊集。一棵模糊决策树状图包括测试值的节点，
　　由用户定义模糊集的测试值分支的边缘和决定等级名称必然性的叶片。
　　我们的算法与ID3算法非常相似，但ID3算法基于信息增益来选择测试属性，
　　若我们有一组数据D，每个数据有各个属性数值A，A，…，A和一个分类的C={C，C，…，C}与属性A的模糊集。D为类C上一个模糊子集，|D|表示数据D模糊集的所有属性成员值的之和。则生成模糊决策树图的算法如下：
　　（1）生成具有所有数据集的根节点，和所有属性的数据模糊集。
　　（2）如果一个数据的模糊集的节点满足如下条件：
　　①C的数据集的比例大于或等于阈值，≥θ；
　　②数据集的数目少于阈值，|D|＜θ；
　　③没有属性值进行分类。
　　然后它就是一个叶节点，并用类名分配。
　　（3）若不满足上述条件，那就不是一个叶片并且测试节点生成如下：
　　对于A计算出Gain（A，D），并且选择测试属性的A来使之最大化；
　　根据A把D分成模糊子集，D数据信息值就是产生D信息值和A的F；
　　为模糊子集生成新的节点并且把模糊集列为节点之间联系的边缘；
　　用D（j=1，2，…，m）代替D并且重复步骤2。
　　其中，Gain（A，D）=I（D）-E（A，D），E（A，D）=（p•I（D）），P=p=
　　算法结束。
　　4.分析决策树的构造及比较
　　本部分以某职业技术学校2010级所开课程成绩作为测试数据。表1是经过数据清理后的学生考试成绩情况信息的训练集。
　　使用模糊ID3算法，最终得出决策树如图2所示。
　　从根到树叶每条路径创建一个规则，可以很清楚地看出“不是重修、是必修课、试卷难度中等、成绩是中等的记录，而且该种记录占了所有记录一半以上”等分类知识。此外研究修正后的决策树，我们可以很清晰地看到每个课程类型分类的关键，以及把研究问题通过量化体现。这些知识对于决策是有帮助的，如可对课程类型I的学生加强专项题和综合题的训练，提高学生解题能力。而在选修课的重点分配方面，要加大学生对此门功课的相对分配时间和动手能力培养。
　　5.结语
　　改进的ID3算法充分运用了信息论在决策树分类中的优越性，结合模糊集合知识把原有的ID3决策树状图改进为一个可理解的模糊决策树状图来解决分类问题。我们提出一个新的从数值数据中生成一个决策树状图的新的算法，通过使用模糊集。最后，我们将其应用于高职院校信息管理系统中，对学生成绩和选课之间进行分析，找出了影响学生成绩的关键因素，为学生培养提供了参考依据。
　　参考文献：
　　［1］Inmon W H，Hackathorn R.Using the Data Warehouse.John Wiley &Sons，1994.
　　［2］Inmon W H.Building the Data Warehouse.QED Technical Publishing Group.
　　［3］Vipin Kumar，Mahesh V.Joshi，Eui-Hong Sam Han，et al HighPerformance Data Mining［M］.Lecture Notes in Computer Science 2003.8：63-88.
　　［4］毛国君，段立娟，王实，石云.数据挖掘原理与算法［M］.北京:清华大学出版社，2005：64-105.
　　［5］戴永群.数据挖掘在教学中的应用［J］.福建电脑，2005.9.
　　［6］张震.数据挖掘技术分析及其在高校管理决策中的决策［J］.远程教育杂志，2005，6（171）.
　　［7］邓廷等.高校科研决策支持系统中关联规则挖掘的应用［J］.沈阳师范大学学报（自然科学版），2004.1，VOL22，（1）.
　　［8］谷文祥，殷明浩.数据挖掘中决策树加权模糊嫡算法［J］.计算技术与自动化，2002，（03）.