决策树基本算法综述

《决策树基本算法综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、决策树基本算法综述作者：专业:软件工程学号：2012110日期:2013.2.4摘要：不同算法产牛的决策树，在测试数据上的准确率、树的繁简程度等方血都有所不同。本文针对几种决策树算法，从分类准确率、树的复杂程度等方面进行了描述和比较。关键词：决策树ID3C4.5统计算法并行决策树算法1•概述1.1决策树算法简介数据挖掘的研究方向冇很多：数据的分类、聚类、分析与预测、关联规则挖掘、序列模式挖掘等。决策树、神经网络、人工智能、贝叶斯网络、关联分析和统计方法等是数据挖掘中常用的算法。在数据分类中，决策树是一种使用广泛的分类方法，它

2、可以对已知的历史数据进行学习和训练，从而得到一颗具冇高信息价值、揭示数据内部信息和关联规则的树，实现数据的分类。1.2决策树算法的优点（1）对于相同数据集的分类准确率高、速度快；（2）生成的树形象清晰、简单肓•观，从根节点向树的叶了节点，每一条分支能够唯一确定一条分类的规则；（3）可伸缩性强，既可以用于小数据集，也可以用于海量数据集；（4）应用领域广泛：目前决策树已应用于金融分析预测、网络金融交易、医疗诊断、天气预测、零售业务及反恐等多个领域。因此，不难看出，通过决策树提取出内部潜在的规则信息，对于報个市场的控制、公司的运营

3、和个人的投资都有着良好的决策辅助作用，所以基于决策树算法的数据挖掘技术有很高的研究价值。由于不同的决策树算法应用于不同的数据集后，生成树的繁简程度、叶了节点的个数及分类准确率都人不相同，因此我们有必要对不同决策树分类进行归纳与比较，了解各种算法的特点和特性，针对不同规模的数据集选择适当的决策树算法，进而得到髙的准确率及较好的可理解性。1.3决策树的表示决策树通过把实例从根节点排列（sort）到某个叶子节点來分类实例，叶子节点即为实例所属的分类。树上的每一个节点指定了对实例的某个属性（attribute）的测试，并且该节点的每

4、一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定实例的属性值对应的树枝向下移动。然后这个过程在以新节点为根的子树上重复。图131画出了一颗典型的学习到的决策树。这颗决策树根据天气情况分类“星期六上午是否适合打网球”。例如，下面的实例将被沿着这颗决策树的最左分支向下排列，因而被判定为反例（也就是这棵树预测这个实例PlayTenis=No）o实攸ij：O

5、utlook*Sunnv：Humidity(图131概念PlayTennis的决策树)通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction)«从树根到树叶的每一条路径对应一组丿瓜性测试的合取，树本身对应这些合取的吸取。图131表示的决策树对应于一下表达式：(Outlook=SunnyAHumidity=Normal)v(Outlook=Overcast)v(Outlook=RainWind=Weak)1.4决策树的剪枝在决策树学习过程中，如果决策树过于复杂，则存储所要花费的代价也就越人

6、；而如果节点个数过多，则每个节点所包含的实例个数就越小，支持每个叶节点假设的实例个数也越小，学习Z后的错误概率就会随Z增加；同时对用户来说又难于理解，所以在决策树学习屮应该对决策树进行简化。可以通过明枝方法简化决策树。冇预剪枝和后明枝两种敢枝方法。(1)预剪枝。预剪枝算法不要求决策树的每个叶节点都属于同一个类，而是在这之前就停止决策树的扩张，例如可以规定决策树的高度，达到一定高度即停止扩张。(2)后剪枝。它由“完全生长”的树剪去分枝。通过删除节点的分枝，明掉树节点。2•基本的决策树算法决策树算法最早产牛于20世纪60年代，是

7、一种机器学习系统CLS：ConceptLearningSystem,该系统首次使用树的概念进行概念学习，是决策树学习系统的先驱，它为今后决策树算法的改进提供了帮助。2.1ID3算法ID3算法是llU.R.Quinlan提出的,即迭代分类器。ID3算法可称为最为经典的决策树算法。此算法理论清晰、学习简单、学习能力佼强，口构造的决策树平均深度较小，分类速度快，特別适合处理大规模的学习问题。其H的在于减少树的深度，即树的复杂度，从而大大减少了分类的规则个数。ID3算法以信息爛和信息增益作为属性选择标准，使得在每一非叶子节点进行测试

8、时，能获得关于被测试例子最人的类别信息，使用该属性将样木集划分成了集后，系统的信息爛值最小。设C是样本中类的数目，S是样本数，P(s,j)表示样本S小样本属于第j类的概率，也即P(ij)=Sj/S,是样本S中属于类j的样木数。因此，对于一个给定的样木分类所需的期望信息增益是：Infa(S)