决策树算法研究及应用.pdf

电脑应用技术 二零零八总第七十二期 决策树算法研究及应用∗ 王桂芹 黄道 华东理工大学实验十五楼206室 摘 要：信息论是数据挖掘技术的重要指导理论之一，是决策树算法实现的理论依据。决 策树算法是一种逼近离散值目标函数的方法，其实质是在学习的基础上，得到分类规则。 本文简要介绍了信息论的基本原理，重点阐述基于信息论的决策树算法，分析了它们目前 主要的代表理论以及存在的问题，并用具体的事例来验证。 关键词：决策树 算法 分类 应用 Study and Application in Decision Tree Algorithm WANG Guiqin HUANG Dao College of Information Science and Engineering, East China University of Science and Technology Abstract ：The information theory is one of the basic theories of Data Mining，and also is the theoretical foundation of the Decision Tree Algorithm ．Decision Tree Algorithm is a method to approach the discrete-valued objective function ．The essential of the method is to obtain a clas- sification rule on the basis of example-based learning ．An example is used to sustain the theory. Keywords ：Decision Tree; Algorithm; Classification; Application 1 引 言 决策树分类算法起源于概念学习系统CLS(Concept Learning System)，然后发展到ID3 方法而为高潮，最后又演化为能处理连续属性的 ． ，有名的决策树方法还有 和 C4 5 CART Assistant ，Sliq、Sprint等等[2] 。最初利用信息论中信息增益方法寻找数据库中具有最大信 息量的字段，作决策树的一个结点字段的某些值作门限建立树的分支；在分支下建立下层 结点和子分支，生成一棵决策树。再剪枝，优化，然后把决策树转化为规则，利用这些规 则可以对新事例进行分类。 作者介绍：王桂芹，女，汉族，1983年5月生于山东省嘉祥县，2005年本科毕业于太原理工大学自动化系， 现就读于华东理工大学信息科学与工程学院，攻读硕士学位，研究方向为数据挖掘；黄道，男，汉族， 华东理工大学信息科学与工程学院博士生导师、教授。 1 电脑应用技术 二零零八总第七十二期 2 算法分类 2.1 ID3算法 Quinlan提出的ID3算法是决策树算法的代表，具有描述简单、分类速度快的优点，适 合于大规模数据的处理，绝大数决策树算法都是在它的基础上加以改进而实现的．它采用 分治策略，通过选择窗口来形成决策树，是利用信息增益寻找数据库中具有最大信息量的 属性字段建立决策树的一个节点，再根据该属性字段的不同取值建立树的分枝；在每个分 枝子集中重复建立树的下层节点和分枝过程。 ID3算法的基础理论清晰，使得算法较简单，学习能力较强，且构造的决策树平均深 度较小，分类速度较快，特别适合处理大规模的学习问题。