决策树讲解培训课件

决议树介绍胡作梁1433275决策树讲解第1页目录页CONTENTSPAGE1.何为决议树2.决议树发展3.决议树分类4.决议树适用决策树讲解第2页何为决议树决策树讲解第3页什么是决议树？经过把实例从根节点排列到某个叶子节点来分类实例；叶子节点即为实例所属分类；树上每个节点说明了对实例某个属性测试，节点每个后继分支对应于该属性一个可能值。决议树（DecisionTree），又称为判定树，是数据挖掘技术中一个主要分类方法，它是一个以树结构（包含二叉树和多叉树）形式来表示预测分析模型。决策树讲解第4页决议树发展决策树讲解第5页决议树发展决议树方法是一个比较通用分类函数迫近法，它是一个惯用于预测模型算法，经过将大量数据有目标分类，找到一些有潜在价值信息。决议树起源是CLS（ConceptLearningSystem），CLS是由Hunt、Marin和Stone为了研究人类概念模型而得来，于1966年提出，该模型为很多决议树算法发展奠定了很好基础。1984年，L.Breiman等人提出了CART（ClassificationandRegressionTree）算法。决策树讲解第6页决议树发展1986年，J.R.Quinlan提出了ID3算法。1993年，J.R.Quinlan又提出了C4.5算法，克服了ID3算法一些不足。1996年，M.Mehta和R.Agrawal等人提出了一个高速可伸缩有监督寻找学习分类方法SLIQ（SupervisedLearningInQuest）。同年，J.Shafer和R.Agrawal等人提出可伸缩并行归纳决议树分类方法SPRINT(ScalablePaRallelizableInductionofDecisionTrees)1998年，R.Rastogi等人提出一个将建树和修剪相结合分类算法PUBLIC(ADecisionTreethatIntegratesBuildingandPruning)决策树讲解第7页决议树分类决策树讲解第8页ID3ID3算法选取最大信息增益属性作为决议树分裂属性。在算法实际应用中，这种方法偏向于选择多值属性，但属性取值数目标多少与属性匹配并无真正关联。这么在使用ID3算法构建时，若出现各属性值取值数分布偏差大情况，分类精度会大打折扣。ID3算法本身并未给出处理连续数据方法。ID3算法不能处理带有缺失值数据集，故在进行算法挖掘之前需要对数据集中缺失值进行预处理。决策树讲解第9页C4.5C4.5算法一样是由J.R.Quinlan提出，它在ID3算法基础上演变而来。C4.5算法除了拥有前述ID3算法基本功效外，在其算法中还加入了连续值处理、属性空缺处理等方法。总结来说，C4.5算法在以下几个方面做出了改进：信息增益百分比计算公式以下：1）使用信息增益百分比而非信息增益作为分裂标准。在上式中，

称为分裂信息，它反应了属性分裂数据延展度与平衡性，计算公式以下：决策树讲解第10页C4.52）处理含有带缺失值属性样本C4.5算法在处理缺失数据时最惯用方法是，将这些值并入最常见某一类中或是以最惯用值代替之。C4.5算法处理连续值属性过程3）处理连续值属性以每个数据作为阈值划分数据集，代价是否过大？决策树讲解第11页C4.54）规则产生决议树每条根节点到叶节点路径都对应一个分类规则，可将全部这些路径综合转换为一个规则集。规则集存放于一个二维数组中，每一行代表决议树一个规则。交互验证是一个模型评定方法。在训练开始之前，预留一部分数据，而在训练之后，使用这部分数据对学习结果进行验证方法叫做交互验证。交互验证最简单方法是两分法，将数据集划分为两个独立子集，一个称为训练集，一个称为测试集。另一个方法是K次折叠交互验证，将数据集划分为K个子集，留取一个作为测试集，其余K-1个作为训练集，最终还对数据子集错误数计算平均值。5）交互验证（CrossValidation）从上面改进描述能够看到，C4.5相较ID3有了许多提升，纵然如此，C4.5依然存在一定不足之处。它在测试属性判断和样本集分割方面依旧存在一定偏向性，同时C4.5生成决议树还称不上简练，尤其是对于数据属性及其取值较多情况。所以，人们还在不停改进现有算法和提出新算法。决策树讲解第12页CARE&SLIQCART（ClassificationAndRegressionTree）算法该决议树算法模型采取是二叉树形式，利用二分递归将数据空间不停划分为不一样子集。一样，每一个叶节点都有着与之相关分类规则，对应了不一样数据集划分。为了减小CART决议树深度，在决议树某一分支节点对应数据集大多数为一类时，即将该分支设为叶节点。CART算法采取GINI系数作为属性分裂标准。在计算机大量普及今天，即使内存和CPU越来越大，越来越快，但终究会有许多数据在处理时候无法全部放入内存计算。在众多决议树算法中，大部分算法需要在决议树生成与分类时将数据集全部放入主存，这在数据集规模较小情况下没有问题，不过一旦数据规模超出主存限制，这些算法就无能为力了。SLIQ（SupervisedLearningInQuest）算法为了处理上述问题，提出了一些改进，而且它能确保分类精度不变。在SLIQ决议树生成过程中能够应用其它算法，其精度也与这些算法一直，不过对于大数量级数据，SLIQ效率大大提升，生成模型也较为精简。除此之外，因为SLIQ破除了主存限制，则其对训练数据量和属性量都没有限制了。SLIQ（SupervisedLearningInQuest）算法决策树讲解第13页SPRINT&PUBLIC

因为SLIQ仍存在对主存容量限制，J.Shafter等人提出了SPRINT（ScalablePaRallelizableINductionofdecisionTrees）算法，其在SLIQ基础上又做出了深入改进。该算法真正意义上破除了主存限制，使得决议树处理数据规模到达了前所未有境界。与此同时，并行算法引入也使得SPRINT算法含有更加好伸缩性。SPRINT主要改进了SLIQ数据结构，合并SLIQ中类表与属性表，将这些数据结构均放于辅存之中。这么就使得算法在遍历属性列表寻找最优分裂时，只需使用辅存中合并数据表。最终，SPRINT采取生成树策略是深度优先规则。并行算法就是用多台处理机联合求解问题方法和步骤，其执行过程是将给定问题首先分解成若干个尽可能相互独立子问题，然后使用多台计算机同时求解它，从而最终求得原问题解。SPRINT算法在上述介绍决议树算法中，全部算法均是先经过一定规则建立决议树，然后在进行决议树剪枝，从而到达生成最终决议树目标。而PUBLIC（ADecisionTreethatIntegratesBuildingandPruning）算法则是经典预剪枝决议树算法。作为预剪枝技术生成决议树与后剪枝决议树是一致，PUBLIC算法采取Gini系数作为分裂标准，能够说是CART算法一个有效改进。PUBLIC算法决策树讲解第14页决议树适用决策树讲解第15页C5.0&CHAID1234SUGGESTION一、C5.0算法

（执行效率和内存使用改进、适用大数据集）1）面对数据遗漏和输入字段很多问题时非常稳健；2）通常不需要很长训练次数进行预计；3）比一些其它类型模型易于了解，模型推出规则有非常直观解释；4）允许进行屡次多于两个子组分割。目标字段必须为分类字段。C4.5是在ID3算法基础上将连续属性离散化，C5.0是在C4.5基础上在内存和执行效率进行了改进。二、CHAID(卡方自动交互检测)（可用于多元分类，从统计角度来分裂变量）1）可产生多分枝决议树；2）目标变量能够定距或定类；3）从统计显著性角度确定分支变量和分割值，进而优化树分枝过程；4）建立在因果关系探讨中，依据目标变量实现对输入变量众多水平划分。决策树讲解第16页三、classificationandregressiontree(C&RT)（对二元分类比较有效）1）可自动忽略对目标变量没有贡献属性变量，也为判断属性变量主要性，降低变量数据提供参考；2）在面对诸如存在缺失值、变量数多等问题时C&RT显得非常稳健（robust）；3）预计模型通常不用花费很长训练时间；4）推理过程完全依据属性变量取值特点（与C5.0不一样，C&RT输出字段既能够是数值型，也能够是分类型）5）比其它模型更易于了解——从模型中得到规则能得到非常直观解释，决议推理过程能够表示成IF…THEN形式；6）目标是定类变量为分类树，若目标变量是定距变量，则为回归树；7）经过检测输入字段，经过分量各个划分产生异质性减小程度，找到最正确一个划分；8）非常灵活，能够允许有部分错分成本，还可指定先验概率分布，可使用自动成本复杂性剪枝来得到归纳性更强树。C&RT决策树讲解第17页四、QUEST（quickunbiasedefficientstatisticaltree）（也用于二分类，运算过程比CR&T更简单有效，但不支持使用连续输出变量）QUEST节点可提供用于构建决议树二元分类法，此方法设计目标是降低大型C&R决议树分析所需处理时间，同时减小分类树方法中常见偏向类别较多预测变量趋势。预测变量字段能够是数字范围，但目标字段必须是分类。QUEST决策树讲解第18页1）决议树与其它技术相结合在数据挖掘技术中，从数据集预处理到最终输出需要知识，要用到很多方面技术，所以决议树也需要与其它技术相结合，才能有创新，才能有发展。现在已经有些人将决议树和含糊集合理论、遗传算法、神经网络等技术结合起来研究，都不一样程度提升了决议树效率和精度。2）决议树分类准确率决议树分类准确率也是研究重点，因为它是判断决议树算法优劣标准之一，比如多变量决议树技术，它