决策树基本算法综述.doc

决策树基本算法综述

作者：
专业:软件工程
学号：2012110

日期：2013.2.4

摘要：不同算法产生的决策树，在测试数据上的准确率、树的繁简程度等方面都有所不同。本文针对几种决策树算法，从分类准确率、树的复杂程度等方面进行了描述和比较。
关键词：决策树 ID3 C4.5 统计算法 并行决策树算法

1.概述
1.1决策树算法简介
数据挖掘的研究方向有很多：数据的分类、聚类、分析与预测、关联规则挖掘、序列模式挖掘等。决策树、神经网络、人工智能、贝叶斯网络、关联分析和统计方法等是数据挖掘中常用的算法。在数据分类中，决策树是一种使用广泛的分类方法，它可以对已知的历史数据进行学习和训练，从而得到一颗具有高信息价值、揭示数据内部信息和关联规则的树，实现数据的分类。
1.2决策树算法的优点
（1） 对于相同数据集的分类准确率高、速度快；
（2） 生成的树形象清晰、简单直观，从根节点向树的叶子节点，每一条分支能够唯一确定一条分类的规则；
（3） 可伸缩性强，既可以用于小数据集，也可以用于海量数据集；
（4） 应用领域广泛：目前决策树已应用于金融分析预测、网络金融交易、医疗诊断、天气预测、零售业务及反恐等多个领域。
因此，不难看出，通过决策树提取出内部潜在的规则信息，对于整个市场的控制、公司的运营和个人的投资都有着良好的决策辅助作用，所以基于决策树算法的数据挖掘技术有很高的研究价值。
由于不同的决策树算法应用于不同的数据集后，生成树的繁简程度、叶子节点的个数及分类准确率都大不相同，因此我们有必要对不同决策树分类进行归纳与比较，了解各种算法的特点和特性，针对不同规模的数据集选择适当的决策树算法，进而得到高的准确率及较好的可理解性。
1.3 决策树的表示
决策树通过把实例从根节点排列（sort）到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点指定了对实例的某个属性（attribute）的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定实例的属性值对应的树枝向下移动。然后这个过程在以新节点为根的子树上重复。
图1.3.1画出了一颗典型的学习到的决策树。这颗决策树根据天气情况分类“星期六上午是否适合打网球”。例如，下面的实例将被沿着这颗决策树的最左分支向下排列，因而被判定为反例（也就是这棵树预测这个实例PlayTenis=No）。
实例：<Outlook=Sunny，Temperature=Hot，Humidity=High，Wind=Strong>

（图1.3.1 概念PlayTennis的决策树）

通常决策树代表实例属性值约束的合取（conjunction）的析取式（disjunction）。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的吸取。图1.3.1表示的决策树对应于一下表达式：
（Outlook=Sunny Humidity=Normal） (Outlook=Overcast)
(Outlook=Rain Wind=Weak)
1.4 决策树的剪枝
在决策树学习过程中，如果决策树过于复杂，则存储所要花费的代价也就越大；而如果节点个数过多，则每个节点所包含的实例个数就越小，支持每个叶节点假设的实例个数也越小，学习之后的错误概率就会随之增加；同时对用户来说又难于理解，所以在决策树学习中应该对决策树进行简化。
可以通过剪枝方法简化决策树。有预剪枝和后剪枝两种剪枝方法。
（1） 预剪枝。 预剪枝算法不要求决策树的每个叶节点都属于同一个类，而是在这之前就停止决策树的扩张，例如可以规定决策树的高度，达到一定高度即停止扩张。
（2） 后剪枝。 它由“完全生长”的树剪去分枝。通过删除节点的分枝，剪掉树节点。

2.基本的决策树算法
决策树算法最早产生于20世纪60年代，是一种机器学习系统CLS：Concept Learning System,该系统首次使用树的概念进行概念学习，是决策树学习系统的先驱，它为今后决策树算法的改进提供了帮助。
2.1 ID3算法
ID3算法是由J.R.Quinlan提出的，即迭代分类器。ID3算法可称为最为经典的决策树算法。此算法理论清晰、学习简单、学习能力较强，且构造的决策树平均深度较小，分类速度快，特别适合处理大规模的学习问题。其目的在于减少树的深度，即树的复杂度，从而大大减少了分类的规则个数。ID3算法以信息熵和信息增益作为属性选择标准，使得在每一非叶子节点进行测试时，能获得关于被测试例子最大的类别信息，使用该属性将样本集划分成子集后，系统的信息熵值最小。
设C是样本中类的数目，S是样本数，P(s,j)表示样本S中样本属于第j类的概率，也即p(i,j)，是样本S中属于类j的样本数。因此，对于一个给定的样本分类所需的期望信息增益是：
具有值的属性T可以将S划分为子集,其中包括类的个样本，根据T的这种划分的期望信息称作T的熵。其加权平均为：
E(T)
T上划分获得的信息增益定义为：

假设S为初始样本集，当前的候选属性集用S_attributes表示，候选属性集中的所有属性皆为离散型。ID3算法的主要步骤如下：
（1） 创建根节点B；
（2） 如果B都属于同一类C，则返回B为叶子节点，标记为类C；
（3） 如果S_attributes为空，则返回B为叶子节点，标记B为S中出现最多的类；
（4） 对每个S_attribute中的属性，循环计算信息增益值G；
（5） B的测试属性test_attribute=S_arrtibutes中具有最高G值得属性；
（6） 对每个test_attribute的取值，做如下操作：
| .由节点B长出一个新叶子节点
||.如果新叶节点对应的样本子集T为空，则不再分裂此叶子节点，将其标记为S中出现最多的类；否则，在该叶节点上重复上述（1）~（6）步操作，继续对它分裂。
ID3算法的优化：通过加权和增加属性重要度，加强属性的标注，降低了非重要属性的标注，把“加权和”转换为权与属性重要度相加的“新加权和”。生成决策树时，数据少的数据元组不会被淹没，最终使决策树减少“大数据掩盖小数据”现象的发生。利用属性重要度5，类别条件熵：

信息增益的公式变为：

属性重要度取值在[0,1]之间，其大小由训练数据集数据计算给出。
2.2 C4.5算法
在ID3算法中，具有最大信息增益的属性被选为分裂属性。显然，ID3算法偏袒具有较多值的属性，因而可能导致过度拟合。因此，在C4.5算法中采用信息增益比率来代替信息增益。
增益比率为：，
为了达到最佳分裂的目的，C4.5先计算每个属性的增益，然后仅对那些高于信息增益平均值的属性应用增益比率进行测试。增益比率最大的属性应当首选为分裂属性。
2.3 统计算法
统计算法是Hart和Mingers设计的另外一种属性区分度量方法。这是一种传统的统计方法，在一个可能性表中，它度量任意两个变量之间的联系。通过比较变量的观察频数和期望频数来确定两个变量之间是否有联系，其结果近似服从分布，值越大则表明联系越强。基本的方程如下：，
在上面的方程中，,即可能性表中每一项的期望值。
2.4 并行决策树算法
并行决策树将一个数据集随机分成几个部分，各部分数据分别用不同的处理器学习，选出各自最好的属性，然后通过比较，综合得出最好的属性，以它为基准建树。对每个新节点，递归地重复上述过程，直到所有的节点都展开成树叶。图2.4.1是将一个数据集分成3个子数据集时的学习流程图。

（图2.4.1 一分三学习流程）

并行决策树构建的主要步骤如下：
（1） 根据决策树扩展策略，随机选择一节点作为当前的节点，并将开始时当前的节点选为根节点；
（2） 当前节点的数据集分成几个子集，各个数据子集分别用一个处理器（学习器）学习；
（3） 各处理器分别用ID3，C4.5，统计等方法生成各自最好的属性；
（4） 选择一个最好的属性作为分裂属性；
（5） 依靠期望树分枝因子，创建本节点的孩子节点；
（6） 对每个子节点，重复（1）~（5），直到没有节点能被用来扩展树；
（7） 用EBP方法修剪最终的树。
3.结语
决策树算法已经有了广泛的应用，并且已经有了许多成熟的系统。决策树各类算法各有优缺点，在实际工作中，必须根据数据类型的特点及数据集的大小，选择合适的算法，才能更好的实现分类。

参考文献
[1]Tom M.Mitchell著.曾华军等译.机器学习.机械工业出版社.2012.6
[2]张学工.模式识别.清华大学出版社.2010.8
[3]王莉.ID3算法的研究与应用.福建电脑.2010（01）
[4]杨清.基于决策树的学习算法.湘潭师范学院学报.1999.6
[5]张学兵.决策树算法及其核心技术.计算机技术与发展.2007.1
[6]张琳.决策树分类算法研究.软件技术与数据库.2011.7