1、决策树简介胡作梁胡作梁 1433275目录页CONTENTS PAGE1.何为决策树2.决策树的发展3.决策树分类4.决策树适用Part1何为决策树Part 1Part 2Part 3Part 44什么是决策树？通过把实例从根节点排列到某个叶子节点来分类实例；叶子节点即为实例所属的分类；树上每个节点说明了对实例的某个属性的测试，节点的每个后继分支对应于该属性的一个可能值。决策树（Decision Tree），又称为判定树，是数据挖掘技术中的一种重要的分类方法，它是一种以树结构（包括二叉树和多叉树）形式来表达的预测分析模型。Part2决策树的发展Part 1Part 2Part 3Part 46
2、决策树的发展决策树方法是一种比较通用的分类函数逼近法，它是一种常用于预测模型的算法，通过将大量数据有目的分类，找到一些有潜在价值的信息。决策树的起源是CLS（Concept Learning System），CLS是由Hunt、Marin和Stone为了研究人类概念模型而得来的，于1966年提出，该模型为很多决策树算法的发展奠定了很好的基础。1984年，L.Breiman等人提出了CART（Classification and Regression Tree）算法。Part 1Part 2Part 3Part 47决策树的发展1986年，J.R.Quinlan提出了ID3算法。1993年，J.
3、R.Quinlan又提出了C4.5算法，克服了ID3算法的一些不足。1996年，M.Mehta和R.Agrawal等人提出了一种高速可伸缩的有监督的寻找学习分类方法SLIQ（Supervised Learning In Quest）。同年，J.Shafer和R.Agrawal等人提出可伸缩并行归纳决策树分类方法SPRINT(Scalable PaRallelizable Induction of Decision Trees)1998年，R.Rastogi等人提出一种将建树和修剪相结合的分类算法PUBLIC(A Decision Tree that Integrates Building an
4、d Pruning)Part3决策树的分类Part 1Part 2Part 3Part 49ID3ID3算法选用最大信息增益的属性作为决策树分裂属性。在算法实际应用中，这种方法偏向于选择多值属性，但属性取值数目的多少与属性的匹配并无真但属性取值数目的多少与属性的匹配并无真正关联。这样在使用正关联。这样在使用ID3算法构建时，若出现各属性值取值数分布偏差大的算法构建时，若出现各属性值取值数分布偏差大的情况，分类精度会大打折扣。情况，分类精度会大打折扣。ID3算法本身并未给出处理连续数据的方法。ID3算法不能处理带有缺失值的数据集，故在进行算法挖掘之前需要对数据集中的缺失值进行预处理。Part 1
5、Part 2Part 3Part 410C4.5C4.5 算法同样是由J.R.Quinlan 提出，它在ID3 算法的基础上演变而来。C4.5 算法除了拥有前述的ID3 算法基本功能外，在其算法中还加入了连续值处理、属性空缺处理等方法。总结来说，C4.5 算法在以下几个方面做出了改进：信息增益比例计算公式如下：1）使用信息增益比例而非信息增益作为分裂标准。)()()(KSplitInfAGainAGainRatio21()logiiiSSSplitInf KSS 在上式中，称为分裂信息，它反映了属性分裂数据的延展度与平衡性，计算公式如下：(K)SplitInfPart 1Part 2Part
6、3Part 411C4.52）处理含有带缺失值属性的样本C4.5 算法在处理缺失数据时最常用的方法是，将这些值并入最常见的某一类中或是以最常用的值代替之。C4.5算法处理连续值属性过程3）处理连续值属性以每个数据作为阈值划分数据集，代价是否过大？Part 1Part 2Part 3Part 412C4.54）规则的产生决策树每条根节点到叶节点的路径都对应一个分类规则，可将所有这些路径综合转换为一个规则集。规则集存储于一个二维数组中，每一行代表决策树的一个规则。交互验证是一种模型的评估方法。在训练开始之前，预留一部分数据，而在训练之后，使用这部分数据对学习的结果进行验证的方法叫做交互验证。交互验
7、证最简单的方法是两分法，将数据集划分为两个独立子集，一个称为训练集，一个称为测试集。另一种方法是K 次折叠交互验证，将数据集划分为K 个子集，留取一个作为测试集，其余K-1 个作为训练集，最后还对数据子集的错误数计算平均值。5）交互验证（Cross Validation）从上面的改进描述可以看到，C4.5 相较ID3 有了许多提高，纵然如此，C4.5 仍然存在一定的不足之处。它在测试属性的判断和样本集分割方面仍旧存在一定的偏向性，同时C4.5 生成的决策树还称不上简洁，特别是对于数据属性及其取值较多的情况。因此，人们还在不断改进现有算法和提出新的算法。Part 1Part 2Part 3Par
8、t 413CARE&SLIQCART（Classification And Regression Tree）算法该决策树算法模型采用的是二叉树形式，利用二分递归将数据空间不断划分为不同子集。同样的，每一个叶节点都有着与之相关的分类规则，对应了不同的数据集划分。为了减小CART 决策树的深度，在决策树某一分支节点对应数据集大多数为一类时，即将该分支设为叶节点。CART算法采用GINI系数作为属性分裂的标准。在计算机大量普及的今天，虽然内存和CPU 越来越大，越来越快，但终究会有许多数据在处理的时候无法全部放入内存计算。在众多决策树算法中，大部分算法需要在决策树生成与分类时将数据集全部放入主存，这
9、在数据集规模较小情况下没有问题，但是一旦数据规模超出主存限制，这些算法就无能为力了。SLIQ（Supervised Learning In Quest）算法为了解决上述问题，提出了一些改进，并且它能保证分类精度不变。在SLIQ 决策树的生成过程中可以应用其他算法，其精度也与这些算法一直，不过对于大数量级的数据，SLIQ 效率大大提高，生成的模型也较为精简。除此之外，由于SLIQ 破除了主存的限制，则其对训练数据量和属性量都没有限制了。SLIQ（Supervised Learning In Quest）算法Part 1Part 2Part 3Part 414SPRINT&PUBLIC 由于SLI
10、Q 仍存在对主存容量的限制，J.Shafter 等人提出了SPRINT（Scalable PaRallelizable INduction of decision Trees）算法，其在SLIQ 的基础上又做出了进一步的改进。该算法真正意义上破除了主存限制，使得决策树处理的数据规模达到了前所未有的境界。与此同时，并行算法的引入也使得SPRINT 算法具有更好的伸缩性。SPRINT 主要改进了SLIQ 的数据结构，合并SLIQ 中的类表与属性表，将这些数据结构均放于辅存之中。这样就使得算法在遍历属性列表寻找最优分裂时，只需使用辅存中的合并数据表。最后，SPRINT 采用的生成树策略是深度优先规则
11、。并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。SPRINT 算法在上述介绍的决策树算法中，所有算法均是先通过一定的规则建立决策树，然后在进行决策树剪枝，从而达到生成最终决策树的目的。而PUBLIC（A Decision Tree that Integrates Building and Pruning）算法则是典型的预剪枝决策树算法。作为预剪枝技术生成的决策树与后剪枝决策树是一致的，PUBLIC 算法采用Gini 系数作为分裂标准，可以说是CART 算法的一种有效改进。PU
12、BLIC 算法Part4决策树的适用Part 1Part 2Part 3Part 416C5.0&CHAID1234SUGGESTION一一、C 5.0算法算法 （执行效率和内存使用改进、适用大数据集执行效率和内存使用改进、适用大数据集）1）面对面对数据遗漏和输入字段很多的问题时非常稳健；数据遗漏和输入字段很多的问题时非常稳健；2）通常）通常不需要很长的训练次数进行估计；不需要很长的训练次数进行估计；3）比）比一些其他类型的模型易于理解，模型推出的规则有非常直观的解释；一些其他类型的模型易于理解，模型推出的规则有非常直观的解释；4）允许）允许进行多次多于两个子组的分割。目标字段必须为分类字段。
13、进行多次多于两个子组的分割。目标字段必须为分类字段。C4.5是在是在ID3算法的基础上将连续属性离散化，算法的基础上将连续属性离散化，C5.0是在是在C4.5的基础上在内存和执行效率的基础上在内存和执行效率进行了改进。进行了改进。二二、CHAID(卡方自动交互检测卡方自动交互检测)（可用于多元分类，从统计角度来分裂变量）（可用于多元分类，从统计角度来分裂变量）1）可产生多分枝的决策树）可产生多分枝的决策树；2）目标变量可以定距或定类）目标变量可以定距或定类；3）从统计显著性角度确定分支变量和分割值，进而优化树的分枝过程）从统计显著性角度确定分支变量和分割值，进而优化树的分枝过程；4）建立在因果
14、关系探讨中，依据目标变量实现对输入变量众多水平划分）建立在因果关系探讨中，依据目标变量实现对输入变量众多水平划分。Part 1Part 2Part 3Part 417三三、classification and regression tree(C&RT)（对二元分类对二元分类比较有效）比较有效）1）可自动忽略对目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少）可自动忽略对目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量数据提供参考；变量数据提供参考；2）在面对诸如存在缺失值、变量数多等问题时）在面对诸如存在缺失值、变量数多等问题时C&RT 显得非常稳健（显得非常稳健（ro
15、bust）；）；3）估计模型通常不用花费很长的训练时间；）估计模型通常不用花费很长的训练时间；4）推理过程完全依据属性变量的取值特点（与）推理过程完全依据属性变量的取值特点（与 C5.0不同，不同，C&RT的输出字段既可以的输出字段既可以是数值型，也可以是分类型是数值型，也可以是分类型）5）比）比其他模型更易于理解其他模型更易于理解从模型中得到的规则能得到非常直观的解释，决策推从模型中得到的规则能得到非常直观的解释，决策推理过程可以表示成理过程可以表示成IFTHEN的形式的形式；6）目标）目标是定类变量为分类树，若目标变量是定距变量，则为回归树；是定类变量为分类树，若目标变量是定距变量，则为回
16、归树；7）通过）通过检测输入字段，通过度量各个划分产生的异质性的减小程度，找到最佳的一检测输入字段，通过度量各个划分产生的异质性的减小程度，找到最佳的一个划分个划分；8）非常）非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树。本复杂性剪枝来得到归纳性更强的树。C&RTPart 1Part 2Part 3Part 418四四、QUEST（quick unbiased efficient statistical tree）（也用于二分类，运算过程比（也用于二分类，运算过程比CR&
17、T更简单有效，但不支持使用连续的输出变量）更简单有效，但不支持使用连续的输出变量）QUEST节点节点可提供用于构建决策树的二元分类法，此方法的设计目的是减少大型可提供用于构建决策树的二元分类法，此方法的设计目的是减少大型 C&R 决策树分析所需的处理时间，同时减小分类树方法中常见的偏向类别较多预测变量的决策树分析所需的处理时间，同时减小分类树方法中常见的偏向类别较多预测变量的趋势。预测变量字段可以是数字范围的，但目标字段必须是分类的。趋势。预测变量字段可以是数字范围的，但目标字段必须是分类的。QUESTPart 1Part 2Part 3Part 4191）决策树与其他技术相结合）决策树与其他
18、技术相结合在数据挖掘技术中，从数据集的预处理到最终输出需要的知识，要用到很多方面的技术，所以决策树也需要与其他技术相结合，才能有创新，才能有发展。现在已经有人将决策树和模糊集合理论、遗传算法、神经网络等技术结合起来研究，都不同程度的提高了决策树的效率和精度。2）决策树分类的准确率）决策树分类的准确率决策树分类的准确率也是研究的重点，因为它是判断决策树算法优劣的标准之一，比如多变量决策树技术，它减少了决策树的规模，它的最终目的是为了提高决策树的精度。未来的发展Part 1Part 2Part 3Part 420实际中数据集往往存在大量的缺失数据、噪声数据等等。当然，最简单的方法就是直接将这样的数据删除，但是这样必然会导致分类结果不准确。目前的方法就是用出现频率最高的值替代缺失值。4）决策树算法的增量学习）决策树算法的增量学习目前很多决策树算法都不具备增量学习的功能，对于新的训练样本需要重新建树，这样会花费大量的时间，大大降低了效率。3）数据集的预处理）数据集的预处理未来的发展21 谢谢
