决策树在计算机等级考试中的应用-丁勇.pdf
《决策树在计算机等级考试中的应用-丁勇.pdf》由会员分享,可在线阅读,更多相关《决策树在计算机等级考试中的应用-丁勇.pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计 算 机 系 统 应 用 http:/www.c-s- 2014 年 第 23 卷 第 6 期 236 研究开发 Research and Development 决策树在计算机等级考试中的应用 丁 勇, 武玉艳 (南京理工大学泰州科技学院 计算机科学与技术系, 泰州 225300) 摘要: 江苏省计算机等级考试是由江苏省教育厅推行的一项考试制度, 该考试越来越受到高校和学生们的重视. 首先基于历届学生的考试真实数据, 应用信息熵和 ID3 算法构造决策树. 然后, 提取分类规则, 并通过计算规则 的准确率与覆盖率对规则进行约简, 从而挖掘出有价值的规则。最后利用该分类规则, 预测学生能否通
2、过等级考 试。通过对历史数据进行仿真实验, 表明决策树预测准确率高, 能挖掘出影响学生通过等级考试的关键因素, 对 计算机等级考试课程教学有一定的指导作用. 关键词: 计算机等级考试; 决策树; 信息增益; ID3 算法 Application of the Decision Tree in the Computer Rank Examination DING Yong, WU Yu-Yan (Department of Computer Science and Technology, Nanjing University of Science and Technology, Taizhou
3、225300, China) Abstract: Jiangsu Computer Rank Examination is a examination mechanism formed by Education Department, which gains the attention of universities and students. First, based on data collected from previous students exeamination, this paper uses Information Gain and ID3 algorithm to cons
4、truct a decision tree. Then, this paper extracts the classification rules from the decision tree, and discovers these rules of the accuracy and coverage. Finally, this paper predicts the ability of students to pass the exam by these rules. Experiments indicate that the decision tree has accurate pre
5、diction, which can dig out the key factors affecting students to pass the grade examination and plays a crucial role in the course teaching. Key words: computer rank examination; decision tree; information gain; ID3 Algorithm 江苏省计算机等级考试是由江苏省教育厅推行的 一项考试制度. 该考试的目的是加强普通高校非计算 机专业的学生对计算机基础知识的理解和掌握, 考试 设立
6、多个语种和等级,考生通过相应等级的考试可获 得证书. 这项考试制度实施至今,得到了全省普通高 校和用人单位的广泛认可,因此也受到高校和学生们 的高度重视. 但由于试题知识点多、难度大等因素, 通过率普遍较低. 为了更好地指导学生顺利考过考 试,挖掘考试隐含的相关信息,并进行有针对性的指 导,是十分有必要的. 决策树方法产生于 20 世纪 70 年代后期,它是一 种典型的分类方法,用于发现数据中蕴涵的分类规则. 该方法首先基于一组训练样本数据,通过相应的算法 构造决策树,并从树中获得分类规则,然后对分类规 则进行约简, 利用规则对未来数据进行预测 1 . 决策树 方法分类精确,预测准确率高,可应
7、用于挖掘计算机 等级考试中的隐含信息. 1 决策树算法 常见的决策树算法有 ID3 算法、 C4.5 算法 2,3 . ID3 算法使用信息增益(Gain)作为属性选择的度量,C4.5 算法使用信息增益率(Gain Ratio)将信息增益规范化. 1.1 ID3 算法 ID3 算法是由 J.R.Quinlan 提出的归纳分类算法, 收稿时间:2013-10-26;收到修改稿时间:2013-11-18 2014 年 第 23 卷 第 6 期 http:/www.c-s- 计 算 机 系 统 应 用 Research and Development 研究开发 237 算法的基本思想是找出具有最大信
8、息增益(Gain)的字 段作为决策树的一个节点,再根据该字段的不同属性 值建立树的分支,对每个分支重复建立树的下层节点 和分支,直到分支的属性值属于同一类. 算法描述如 下. 算法: Generate_Decision_Tree 输入: 训练样本 DataSets(D) 候选属性集 Attributes,包含分类属性 输出: 决策树 方法: (1) 创建一个节点 N; (2) If D 中的元组属于同一类 C then (3) 返回 N 作为叶节点,以类 C 为标记; (4) If attributes 为空then (5) 返回 N 作为叶节点,标记为普通类; (6) 选择 attribut
9、es 中具有最高信息增益(Gain) 的属性作为分裂属性 (split_attribute) ; (7) 使用 split_attribute 标记节点 N; (8) For split_attribute 的每个属性值 Vi (9) 由节点 N 生长出一个条件为 split_attribute=Vi 的分枝; (10) 设 Di是 D中满足 split_attribute=Vi的数据集合; (11) IF Di为空then (12) 加一个叶节点 N,标记为普通类; (13) Else (14) 加一个由 Generate_Decision_Tree (Di, attributes-spli
10、t_attribute)返回的节点; (15) End for 1.2 信息增益计算 ID3 算法最关键的是对训练样本中属性的信息增 益(Gain)的计算. 对 D 中元组按类标号 C 进行分类所 需的期望信息由公式 1 表示: (1) = = m i pi i P 1 2 log Info(D)其中, i P 是 D 中任意元组属于类 i C 的概率,因为 采用二进制编码,因此采用以 2 为底的对数函数. Info(D)又称为 D 的熵. 假设按 A属性划分 D 中的元组, 属性 A有 v个不 同值a1,a2,a3.av,用属性 A 将 D 划分为 v 个子集 D1,D2,.Dv,其 中 D
11、j 中的样本在属性 A上具有相同 的值 aj(j=1,2,.v). 设 Dij 是子集 Dj 中类 Ci 的样本数, 由 A 划分成子集所需的期望信息由公式 2 表示: (2) ) ( | | | | ) ( 1 Dj Info D Dj D Info v j A = =其中, ) (Dj Info 是属性 A 划分子集 Dj 所需的期 望信息. 信息增益为基于类标号划分 D 的期望信息与 基于 A属性划分 D 的期望信息之间的差, 由公式 3 表 示: ) ( ) ( ) ( D Info D Info A Gain A =(3) C4.5 算法在 ID3 算法的基础上进行了改进,克服 了信
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 决策树 计算机等级考试 中的 应用
限制150内