搜索
决策树ID3算法在学生成绩中的应用摘要：介绍了数据挖掘中决策树的分类方法和概念，以及著名的ID3算法，同时也介绍了ID3算法在学生成绩中的应用．关键词：数据挖掘；知识发现；分类；决策树；ID3算法引言：随着数据库管理系统在教学工作中的应用，数据库积累的数据越来越多，特别是学生的成绩数据库，数据量过于庞大，但目前对这些数据的处理还只是简单的备份、查询与统计，并没有对大量的成绩数据进行深入的分析，加以捕捉有利于教学工作的信息．因此如何快速而又准确地从浩瀚的成绩数据库中提取出所需信息，就需要一种新的数据分析技术加以处理，数据挖掘技术正是解决这个问题的可行而有效的方法．1基本原理1．1数据挖掘基本概念数据挖掘(DataMining，简称DM)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又有潜在的有用信息和知识的过程[1]，是数据库中的知识发现(KnowledgeDiscoveryinDatabases，简称KDD)的核心．它是涉及数据库、人工智能、机械学、统计学、人工神经网络等的交叉学科．目前，常用的数据挖掘分析方法有：关联规则分析、序列模式分析、分类分析、聚类分析几种，本文选择了分类技术中的决策树用于学生成绩中的数据挖掘．1．2决策树的分类方法和概念决策树是通过一系列规则对数据进行分类的过程．它提供一种在什么条件下会得到什么值的类似规则的方法【2J．它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性值从该节点向下分支，叶节点是要学习划分的类，从根节点到叶节点的一条路径就对应着一条分类规则，整个决策树就对应着一组析取表达式规则．1．3ID3算法介绍决策树归纳的基本算法是贪心算法，它以自顶向下递归的方法构造决策树．著名的决策树归纳算法ID3算法的基本策略如下：(1)树以代表训练样本的单个节点开始．(2)如果样本都在同一个类中，则这个节点成为树叶节点，并用该类标记．(3)否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好的将样本分类的属性，该属性成为该节点的“测试”或“判定”属性．(4)对测试属性的每个已知的值创建一个分支，并据此划分样本．(5)算法使用类似的方法，递归地形成每个划分上的样本决策树．一旦一个属性出现在一个节点上。就不必在该节点的后代上考虑这个属性．属性选择采用信息增益的方法来确定．通过选择具有最高信息增益的属性作为当前节点的测试属性，这样保证分类时所需信息最小，从而产生的决策树最为简单．几个重要的公式：任意样本分类的期望m信息：I(s。，s：，⋯，S。)=一．∑．pi姗：(Pi)，其中，数据集为S，m为S分类数目，Pi=Si／S是任意一个数据tS上⋯上q对象属于类别Ci的概率．利用属性A划分样本集合所需要的信息(熵)：E(A)=五』二1二二巫I(s。j，J2JJ⋯，SⅢi)．信息增益：Gain(A)=I(S。，S：，⋯，S，)一E(A)．当决策树创建时，由于数据中的噪声和孤立点，许多分枝反映的是训练中的异常，因此还要对决策树进行剪枝．有两种常用的剪枝方法，先剪枝方法和后剪枝方法．最后要从决策树提取分类规则，并用if⋯tIlen的形式表示出来．2ID3算法在学生成绩中的应用2．1数据预处理2．1．1数据转换数据转换主要是对数据进行规格化操作，将数据变成统一的格式．由于分类技术需要离散值属性，而学生成绩属于连续值属性，需将连续值属性离散化处理．使用概念分层技术，可以将连续值属性转换为离散值属性．将学生本学期的总评成绩属性的所有值按0—70分、70～80分、80分以上划分成“差”、“一般”、“良好”3类．从而生成学生成绩分析基本数据库．如图1．2．1．2数据消减数据消减的目的是缩小所挖掘数据的规模，本文选择其中与成绩属性相关性较大的课后上机时间、学前对知识了解程度、课堂学习情况、平时成绩、总评属性作为建立总成绩分类决策树模型的依据，并且为了重点分析成绩良好的原因，将“总评”字段转化为“是否优良”字段，选择“是否优良”为类别属性，有两个类“Yes”和“No”，从而生成用于对成绩是否优良进行分类的基本数据表，如图2．2．2ID3算法的实现与应用这里将重点说明是否优良决策树模型的生成．从训练集中选取252个样本，其中类“是”有85个样本，类“否”有167个样本．计算对给定样本分类所需的信息熵：t(s⋯S)=I(85，167)=一爰l。g：簧一墨l。g：墨=o．9222首先计算“平时成绩”属性，该属性有3个属性值，需对每个属性所划分的子集计算信息熵：对于“平时成绩”=“较好”，类“Yes”有52个样本，类“No”有37个样本，由公式计算出：I(su，S：。)=0．9794对于“平时成绩”=“中”，类“Yes”有32个样本，类“No”有81个样本，由公式计算出：I(SmS笠)=0．8598对于“平时成绩”=“差”，类“Yes”有1个样本，类“No”有49个样本，由公式计算出：I(SmS∞)=0．1414按平时成绩划分给定样本所需的期望信息为：E(平时成绩)：丽89I(s¨，$21)+黑I(S。：，S篮)+罴I(SmS∞)=O．7595，则Gain(平时成绩)=I(s。，S：)一E(平时成绩)=0．1627．同理：Gain(课后上机时问)三0．0812，Gain(课堂学习情况)=0．089，Gain(学前对知识了解程度)=0．0353．由于“平时成绩”属性具有最高增益信息，它被选作测试属性．创建一个节点，用“平时成绩”标记，并对每个属性值，引出一个分支，样本以此划分．其它分支节点的划分也按此方法．算法返回的决策树如图3所示．这是一棵完全生长的决策树，过于“枝繁叶茂”，为了使得到的决策树所蕴含的规则具有普遍意义，必须对决策树进行修剪，以提高今后分类识别的速度和分类识别新数据的能力．本文采用事后修剪的方法，首先计算出一个充分生长的决策树的错误率，由用户指定一个最大的允许错误率．当剪枝达到某个深度时，计算出的错误率高于允许的最大值时，立即停止剪枝，否则可以继续剪枝．图4为剪枝后的成绩是否优良分类决策树．决策树最大的优点就是可以直接提取分类规则．由于本例中希望了解影响学生学习成绩优良的因素，因此，所提取的规则主要考虑分类为“Yes”的百分比规则．所生成的成绩为优良的分类规则如下：IF平时成绩=“较好”AND课堂学习=。完全掌握”THEN成绩优良的比率=100％IF平时成绩=“较好”AND课堂学习=“基本掌握”THEN成绩优良的比率=72％IF平时成绩=“较好”AND课堂学习=“不够好”AND上机时间=“=4”THEN成绩优良的比率=67％IF平时成绩=“较好”AND课堂学习=“不够好”AND上机时间=“2—4”THEN成绩优良的比塞=71％一．2)t17．3y田4剪枝后的成绩是否优良决策树IF平时成绩=“较好”AND课堂学习=“不够好”AND上机时间=“=2”THEN成绩优良的比率=18％IF平时成绩=“较好”AND课堂学习=“不够好”AND上机时间=“=O”THEN成绩优良的比率=O％IF平时成绩=“较好”AND课堂学习=“不好”THEN成绩优良的比率=0％IF平时成绩=“中”AND课堂学习=“完全掌握”THEN成绩优良的比率=100％IF平时成绩=“中”AND课堂学习=“基本掌握”THEN成绩优良的比率=32％IF平时成绩=“中”AND课堂学习=“不够好”THEN成绩优良的比率=22％IF平时成绩=“中”AND课堂学习=“不好”THEN成绩优良的比率=O％IF平时成绩=“较差”THEN成绩优良的比率=2％3结论数据挖掘是深层次的数据信息分析方法，将数据挖掘技术应用于对学生成绩的分析无疑是非常有益的，它可以全面地分析考试结果与各种因素之间隐藏的内在联系，可以挖掘出很多意想不到的知识，从而会促进教学质量的进一步提高，科学地指导教学．相信随着数据挖掘在教学上越来越广泛的应用，必将会给我国的教育事业带来质的飞跃．参考文献：1]张儒良，玉翰虎．论数据挖掘优化教学管理[J]．贵州民族学院学报，2004，(2)：133—135．[2]马秀红，宋建社，董晟飞．数据挖掘中决策树的探讨[J]．计算机工程与应用，2004，(1)：185．[3]JiaweiHart，MichellneKamber．数据挖掘概念与技术[M]．范明。孟小峰译．北京：机械工业出版社，2001．[4]张伟.数据挖掘中的ID3算法研究与实现[J].软件导刊,2010,(5).