2022年决策树的基本算法[归 .pdf

3 决策树的基本算法-ID3算法3.1 ID3算法的提出决策树方法的起源是概念学习系统(Concept Learning System, CLS),然后发展到 ID3 方法而成为高峰。 Quinlan 提出的 ID31,3,4算法通过对一个例子集进行学习生成一棵决策树 , 现假设一个例子仅属于两种分类之一: 正例, 即符合被学习的目标概念的例子 ; 反例, 即不符合目标概念的例子。另外, 假设例子的所有属性都是离散属性。3.2 ID3算法描述在决策树归纳方法中 , 通常使用信息增益方法来帮助确定生成每个结点时所应选择的合适属性 , 这样就可以选择具有最高信息增益( 熵减少的程度最大 ) 的属性作为当前结点的测试属性, 以便使对以后所划分获得的训练样本子集进行分类所需要信息最小 , 也就是说 , 利用该属性进行当前 ( 结点所含 )样本集合划分 , 将会使得所产生的各样本子集中的 “不同类别混合程度” 降为最低。 因此采用这样一种信息论方法将帮助有效减少对象分类所需要的划分次数。设 S为一个包含 s 个数据样本的集合 , 类别属性可以取 m个不同的值 , 对应于m个不同的类别 Ci, i 1,2,3,m。假设 si为类别 Ci中的样本个数 , 那么要对一个给定数据对象进行分类所需要的信息量为 I(s1,s2, ,sm)= - pilog(pi) (1)其中 pi= 即为 S中属于类别 Ci的概率。设一个属性 A取 v 个不同的值 a1,a2, , ,av, 利用属性 A可以将集合 S划分为 v 个子集 S1,S2, ,Sv, 其中 Sj 包含了 S集合中属性 A取 aj 值的数据样本 ,若属性 A被选为测试属性 (用于对当前样本集进行划分), 设 Sij为子集 Sj中属于Ci类别的样本集 , 利用属性 A划分当前样本集合所需要的信息熵:4 算法在教师课堂教学评估系统的应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 决策树的构造主要分为两个阶段: 建树阶段和调整阶段。以一个教师课堂教学评估系统为例 , 对决策树分类的应用进行讨论。主要讨论课堂教学评估数据库中的数据挖掘和知识发现。4.1 数据转换和预处理该课堂教学评估指标体系表共分若干项, 经研究可归纳为教学态度6、 教学内容 7、教学方法 8、教学效果 9、评价 A10共五个项目 ( 见表) 。实际数据见表 4-1。表 4-1 教师课堂教学评估质量等级和区段数据A1A6A7A8A9A10192.692.691.3392.5592.6287.0586.2780.985.0587.05390.4592.7786.289.990.45498.396.8397.0397.1598.3591.191.9384.9788.8591.1695.9596.1395.3395.9595.65789.387.2384.283.189.3885.2580.6776.538085.25992.8591.488.28992.851084.6584.4779.380.5584.651193.393.3791.0790.393.31291.0591.9785.686.1591.051387.658889.1787.287.651490.9590.9386.2788.9590.951595.296.0789.6392.695.21691.388.6383.987.8591.31787.1587.5384.1787.3587.151893.0590.486.6387.1593.051978.579.5767.377.7578.52087.492.4779.1382.787.4名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 因属性初始值为连续值 , 需先进行离散化处理。将属性划分为若干个区段,95-100 分为 C1,80-94 分为 C2,70-79 分为 C3,60-69 分为 C4,小于 60分为 C5,找出综合评估成绩与这四项等级之间的规则知识。经过预处理后, 得到的数据库如表 4-2 所示。表 4-2 预处理后的教师课堂教学评估质量数据5 结束语数据挖掘中分类和预测是重要的部分之一，分类算法有很多， 近来出现了很多新的改进算法（基于粗糙集的并行决策树算法、基于贝叶斯的TAN算法等）；分类方法中的决策树方法对于分类和决策有着很大的实用性。本文在教学评估方面验证了决策树方法进行分类的有效性和准确性，该算法不仅适用于教学评估，在政府经济计划辅助决策、保险业、银行、股票交易等领域也大有作为， 可以为管理人员、 决策人员控制投资提供有力的决策支持。决策树算法还有很多有待于改进的方面， 使其更好地为处理海量数据发掘有效信息做出贡献，这才是我们今后的研究方向。同时感谢学院领导对我们的关心和支持，感谢计算机科学与技术系其他老师在学习和生活中给予我的支持和帮助，感谢孙彬、贾彦、张信峰、任欣、许学敏等同学对我的帮助。 在忻州师范学院不仅学到了知识，而且从各位老师那里学到了严谨的治学态度、 踏实认真的工作精神和为人正直的作风，也在做实验的期间体会到团队精神是如此重要， 这都将使我终身受益。 还要感谢我的父母， 是他们一直在背后支持着我。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -