基于树的方法

基于树的方法Tree-basedMethods方匡南教授博士生导师2•本章将介绍基于树的回归和分类方法，这些方法主要根据分层和分割的方式将预测变量空间划分为一系列简单区域。•对某个给定的待预测的观测值，用它所属区域中训练集的平均值或众数对其进行预测。•由于划分预测变量空间的分裂规则可以被概括为一棵树，所以这类方法被称为决策树(decisiontree)方法。基于树的方法3•基于树的方法简便且易于解释。但预测准确性通常低于第6章和第7章介绍的指导的学习方法。•本章还将介绍装袋法、随机森林和提升法三种方法，它们都是先建立多棵树，再将这些树综合，最后根据表决产生预测。•我们将看到，将大量的树集成后会极大地提升预测准确性，然而与此同时会损失一些解释性。基于树的方法目录Contents一、决策树二、装袋法三、随机森林四、提升法1决策树decisiontree6决策树装袋法随机森林提升法•决策树在回归问题和分类问题中都有用武之地。下面先介绍回归树，再介绍分类树。先从一个简单例子开始。•Baseballsalarydata•Howwouldyoustratifyit?•Salaryiscolor-codedfromlow(blue,green)tohigh(yellow,red)决策树基本原理7决策树装袋法随机森林提升法基于Hitters数据集的回归树8决策树装袋法随机森林提升法基于Hitters数据集的回归树•基于Hitters数据集的回归树，根据运动员在职业棒球大联盟效力的年头数和上一年安打次数预测运动员的对数薪水。内部结点上的标记(形式为)表示的是这个分裂点发散出的左分支，右侧的分枝则对应。•以这棵树为例，树顶部的分裂点产生出两个大分枝。左边的分枝对应效力于职业棒球大联盟的年头数Years4.5，右边的分支对应效力于职业棒球大联盟的年头数Years=4.5。•这棵树有两个内部结点和三个终端结点(树叶)。每个树叶上的数字表示落在这个树叶处观测值的平均响应值。jkXtjkXt9决策树装袋法随机森林提升法基于Hitters数据集的回归树•上述回归树将Hitters数据集分为三个区域。1{4.5}RXYears3{4.5,117.5}RXYearsHits2{4.5,117.5}RXYearsHits10决策树装袋法随机森林提升法树的术语•与自然界中的树类似，区域R1、R2和R3称为树的终端结点(terminaInode)或树叶。•决策树通常是从上到下绘制的，树叶位于树的底部。沿树将预测变量空间分开的点称为内部结点(Internalnode)。在Hitters回归树中，文字Years4.5和Hits117.5标示出了两个内部结点。树内部各个结点的连接部分称为分支(branch)。11决策树装袋法随机森林提升法Hitters回归树的解读•Years是决定Salary的最重要因素，和有经验的运动员相比，经验少的运动员薪水更低。如果一名运动员效力年数少，那么他前一年的安打次数对薪水几乎没有影响。但对在联盟效力5年及以上的运动员来说，前一年的安打次数对薪水是有影响的，对他们来说，去年完成更多安打的人往往会得到更高的薪水。•Hitters回归树或许是对变量Years，Hits和Salary之间真实关系的一种过度简化。但相对于其他形式的回归模型，它的优势在于解释起来更简便，且能很好地用图形来表示。12决策树装袋法随机森林提升法建立回归树的过程•建立回归树的过程大致可以分为两步•(1)将预测变量空间(即的可能取值构成的集合)分割成J个互不重叠的区域•(2)对落入区域的每个观测值作同样的预测，预测值等于上训练集的响应值的简单算术平均。12,,,pXXX12,,,jRRRjRjR13决策树装袋法随机森林提升法建立回归树的过程•如何构建区域?理论上，区域的形状是任意的，但出于模型简化和增强可解释性的考虑，这里将预测变量空间划分成高维矩形，或称盒子。划分区域的目标是找到使模型的残差平方和RSS最小的矩形区域•RSS的定义为:是第j个矩形区域中训练集的平均响应值。21ˆ()jjJiRjiRyy12,,,jRRR12,,,jRRRˆjRy14决策树装袋法随机森林提升法建立回归树的过程•遗憾的是，要想考虑将特征空间划分为J个矩形区域的所有可能性，在计算上是不可行的。因此一般采用一种自上而下、贪婪方法：递归二叉分裂•自上而下指的是从树顶端开始(在此处，所有观测值都属于同一个空间)依次分裂预测变量空间，每个分裂点都产生两个新的分支。•贪婪指在建立树的每一步中，最优(best)分裂确定仅限于某一步进程，而不是针对全局去选择那些能够在未来进程中构建出更好的树的分裂点。15决策树装袋法随机森林提升法建立回归树的过程•在执行递归二叉分裂时，先选择预测变量和分割点s，将预测变量空间分为两个区域和，使RSS尽可能地减小。•重复上述步骤，寻找继续分割数据集的最优预测变量和最优分割点，使随之产生的区域中的RSS达到最小。此时被分割的不再是整个预测变量空间，而是之前确定的两个区域之一。如此一来就能得到3个区域。接着进一步分割3个区域之一以最小化RSS..…•这一过程不断持续，直到符合某个停止准则，如当所有区域包含的观测的个数都不大于5时，分裂停止。jXXsjXjXXs16决策树装袋法随机森林提升法回归树•数据集为其中•假设我们已经将空间划分为M个区域，•每个区域的预测值是一个常数，那么•如果我们的目标是最小化•则最优的为1()()MmmmfxcIxR12,,,MRRRmc1,2,,iNˆ()miimcaveyxR(,)iixy12(,,,)iiiipxxxx2(())iiyfxmc17决策树装袋法随机森林提升法回归树•对于第j个划分变量和分割点s，定义一对半平面：•寻找j和s，使得•给定j和s，内部最小化的解为12122212,(,)(,)minmin()min()iiiijsccxRjsxRjsycyc1(,)jRjsXXs11ˆ((,))iicaveyxRjs2(,)jRjsXXs22ˆ((,))iicaveyxRjs18决策树装袋法随机森林提升法回归树•区域产生后，就可以确定某一给定测试数据所属的区域，并用这一区域的训练集平均响应值对其进行预测。•一个将预测变量空间划分为五个区域的例子如下张ppt所示12,,,jRRR19决策树装袋法随机森林提升法•左上：一种不能由递归二叉分裂得到的二维特征空间划分。•右上:二维例子中的递归二叉分裂结果。•左下：右上图对应的回归树。•右下：回归树所对应的预测平面的透视图。20决策树装袋法随机森林提升法剪枝•上述方法会在训练集中取得良好的预测效果，却很有可能造成数据的过拟合，导致在测试集上效果不佳。原因在于这种方法产生的树可能过于复杂。•一棵分裂点更少、规模更小(区域的个数更少)的树会有更小的方差和更好的可解释性(以增加微小偏差为代价)。针对上述问题，一种可能的解决办法是：仅当分裂使残差平方和的减小量超过某阀值时，才分裂树节点。•这种策略能生成较小的树，但可能产生过于短视的问题，一些起初看来不值得的分裂却可能之后产生非常好的分裂，也就是说在下一步中，RSS大幅减小。12,,,jRRR21决策树装袋法随机森林提升法剪枝•因此，更好的策略是生成一棵很大的树，然后通过剪枝(prune)得到子树。•代价复杂性剪枝(costcomplexitypruning)，也称最弱联系剪枝可以完成这一任务。•考虑以非负调整参数标记的一系列子树，每一个的取值对应一棵子树当一定时，其对应的子树使下式最小:••这里的表示树T的终端结点数，是第m个终端结点对应的矩形（预测向量空间的一个子集），是与对应的预测值，也就是中训练集的平均值。0TT0T21:ˆ()mimTiRmixRyyTTmRmRˆmRymR22决策树装袋法随机森林提升法选择最佳子树•调整系数在子树的复杂性和与训练数据的契合度之间控制权衡。•可以用交叉验证或验证法确定，然后在整个数据集中找到与之对应的子树。23决策树装袋法随机森林提升法总结：树的算法•(1)利用递归二叉分裂在训练集中生成一颗大树，只有当终端结点包含的观测个数低于某个最小值时才停止。•(2)对大树进行代价复杂性剪枝，得到一系列最优子树，子树是的函数。•(3)利用K折交叉验证选择。具体做法是将训练集分为K折。对所有•(a)对训练集上所有不属于第k折的数据重复步骤1和2，得到与一一对应的子树。•(b)求出上述子树在第k折上的均方预测误差。•上述操作结束后，每个会有相应的K个均方预测误差，对于这K个值求平均，选出使平均误差最小的。•(4)找出选定的值在步骤2中对应的子树即可。1,,kK24决策树装袋法随机森林提升法Baseballexample•首先，将数据集随机分为两半，训练集中包含132个观测值，测试集中包含131个观测值。•然后在训练集上建立一棵很大的回归树，取不同的α值，得到终端结点数各不相同的子树。•最后用6折交叉验证法估计交叉验证的均方误差，均方误差是α的函数。25决策树装袋法随机森林提升法26决策树装袋法随机森林提升法27决策树装袋法随机森林提升法分类树•分类树和回归树十分相似，它们的区别在于:分类树被用于预测定性变量而非定量变量。•在回归树中，对一给定观测值，响应预测值取它所属的终端结点内训练集的平均响应值。与之相对，对分类树来说，给定观测值被预测为它所属区域内的训练集中最常出现的类(mostcommonlyoccurringclass)28决策树装袋法随机森林提升法分类树•与回归树一样，分类树采用递归二叉分裂。但在分类树中，RSS无法作为确定二叉分裂点的准则。一个很自然的替代指标是分类错误率。•分类错误率的定义为此区域的训练集中非最常见类所占的比例。其表达式如下•代表第m个区域的训练集中第k类所占比例。但事实证明，分类错误率这一指标在构建树时不够敏感。在实践中，另外两个指标更有优势。ˆ1max()mkkEpˆmkp29决策树装袋法随机森林提升法基尼系数和互熵•基尼系数定义如下•它衡量的是K个类别的总方差。不难发现，如果所有的取值都接近0或1，基尼系数会很小。因此基尼系数被视为衡量结点纯度的指标，如果它较小，就意味着某个结点包含的观测值几乎都来自同一类别。•可以替代基尼系数的指标是互熵，定义如下：•事实上，基尼系数和互熵在数值上是相当接近的。1ˆˆ(1)KmkmkkGppˆmkp1ˆˆlogKmkmkkDpp30决策树装袋法随机森林提升法分类树ˆmkp31决策树装袋法随机森林提升法heartdata•数据中包含一个关于303位有胸痛症状的病人的二元变量HD(是否患病)。•Yes表示经血管造影诊断，病人患有心脏病，No表示未患心脏病。•预测变量有13个，包括Age(年龄)、Sex(性别)、Chol(胆固醇指标)和其他一些心肺功能指标。•根据交叉验证，最终得到一棵有6个终端结点的树。32决策树装袋法随机森林提升法heartdata33决策树装袋法随机森林提升法heartdata34决策树装袋法随机森林提升法TreesVersusLinearModels•TopRow:Truelinearboundary;•Bottomrow:truenon-linearboundary.•Leftcolumn:linearmodel;•Rightcolumn:tree-basedmodel35决策树装袋法随机森林提升法树的优缺点•优点•决策树解释性强，在解释性方面甚至比线性回归更方便。•有人认为与传统的回归和分类方法相比，决策树更接近人的决策模式。•树可以用图形表示，非专业人士也可以轻松解释(尤其是当树规模较小时)。•树可以直接处理定性的预测变量而不需要创建哑变量。•缺点•遗憾的是，树的预测准确性一般无法达到其他回归和分类方法的水平。•不过，通过装袋法、随机森林和提升法等方