决策树--PPT.ppt

决策树决策树根据李峰等人的PPT改编课件主要依据李航编写的《统计学习方法》编制，清华大学出版社另一本参考书：《数据挖掘与数学建模》国防工业出版社 2010 决策树决策树l  1.1  决策树模型与学习l  1.2  特征选择l  1.3  决策树的生成l  1.4  决策树的剪枝l  1.5  CART算法1.1 决策树模型与学习决策树模型与学习l  1.1.1  决策树模型l  1.1.2  决策树与if-then规则l  1.1.3  决策树与条件概率分布l  1.1.4  决策树学习1.1.1 决策树模型决策树模型l什么是决策树？l定义1.1（决策树） 分类决策树模型是一种描述对实例进行分类的树形结构决策树由结点和有向边组成结点有两种类型：内部结点和叶节点内部结点表示一个特征或属性，叶节点表示一个类决策树学习算法的特点决策树学习算法的特点        决策树学习算法的最大优点是，它可以自学习在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习显然，它属于有监督学习从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。

决策树学习的主要算法决策树学习的主要算法                建立决策树的关键，即在当前状态下选择哪个属性作为分类依据根据不同的目标函数，建立决策树主要有一下三种算法ID3 （J. Ross Quinlan-1975）核心：信息熵C4.5—ID3的改进，核心：信息增益比CART（Breiman-1984），核心：基尼指数例例1. 找对象找对象l 决策树分类的思想类似于找对象现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：l     女儿：多大年纪了？   (年龄)      母亲：26      女儿：长的帅不帅？   (长相)      母亲：挺帅的      女儿：收入高不？       (收入情况)      母亲：不算很高，中等情况       女儿：是公务员不？  (是否公务员)      母亲：是，在税务局上班呢      女儿：那好，我去见见1.1.2 决策树决策树与与if-then规则规则l由决策树的根结点到叶结点的每一条路径构建一条规则；l路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论lIf-then规则集合的一重要性质：互斥并且完备1.1.3 决策树与条件概率分布决策树与条件概率分布         将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。

         各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去        1.1.4 决策树学习决策树学习l 1.1.4 决策树学习决策树学习l目标：我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力l决策树学习的损失函数：（通常是）正则化的极大似然函数但是基于损失函数找到全局最优决策树是NP-完全问题l现实中决策树学习通常采用启发式方法，即局部最优l具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature1.2 特征选择特征选择1.2.1 特征选择问题特征选择问题l特征选择在于选取对训练数据具有分类能力的特征l如何判断一个特征对于当前数据集的分类效果？   也即确定选择特征的准则ID年龄年龄有工作有工作有自己有自己的房子的房子信贷情信贷情况况类别类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否例1.2 右表是一个由15个样本组成的贷款申请训练数据。

数据包括贷款申请人的四个特征表的最后一列是类别，是否同意贷款，取2个值：是、否希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类特征选择是决定用哪个特征来划分特征空间1.2.2 信息增益信息增益l 熵熵-就分类而言，所有成员都属于一类，熵为零；就分类而言，所有成员都属于一类，熵为零；不同类别不同类别 数目相等，则熵等于数目相等，则熵等于1，类别数目不等，则熵，类别数目不等，则熵介于介于0,1之间l 条件熵条件熵l 信息增益信息增益l 信息增益的具体公式信息增益的具体公式l 信息增益算法信息增益算法l 例例1.3 对表对表1.1所给的训练数据集所给的训练数据集D,根据信息增益准则选择最优特征根据信息增益准则选择最优特征ID年龄年龄有工有工作作有自有自己的己的房子房子信贷信贷情况情况类别类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否 1.2.3 信息增益比信息增益比l 1.3 决策树的生成决策树的生成1.3.1 ID3算法算法l 例例1.4 对表对表1.1的训练数据集，利用的训练数据集，利用ID3算法建立算法建立决策树决策树ID年年龄龄有工有工作作信贷情信贷情况况类别类别1青年否一般否2青年否好否3青年是好是5青年否一般否6中年否一般否7中年否好否13老年是好是14老年是非常好是15老年否一般否有自己的房子(A3)ID年年龄龄有工有工作作信贷情信贷情况况类类别别4青年是一般是8中年是好是9中年否非常好 是10中年否非常好 是11老年否非常好 是12老年都好是是是否否表1表2l 有自己的房子是否是是否有工作ID年年龄龄信贷情信贷情况况类类别别3青年好是13老年好是14老年非常好是表3ID年年龄龄信贷情信贷情况况类类别别1青年一般否2青年好否5青年一般否6中年一般否7中年好否15老年一般否表4 这里生成的决策树只用这里生成的决策树只用到两个特征（两个内节点），到两个特征（两个内节点），ID3算法容易存在过拟合问题。

算法容易存在过拟合问题补充：如何解决决策树的过拟合问补充：如何解决决策树的过拟合问题题概念原因解决什么是过度拟合数据过度拟合数据是怎么产生的怎么去解决这个问题补充：如何解决决策树的过拟合问补充：如何解决决策树的过拟合问题题——概念概念            过度拟合（过度拟合（overfittingoverfitting）：如果）：如果决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数据的最佳决策树一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过拟合” 定义：定义：给定一个假设H，如果在假设空间上存在另一个假设H'，使得在训练集上H的错误率差比H'小，而在测试集上H的错误率却比H'要大，那么称假设H过度拟合训练数据二二.产生过度拟合数据问题的原因有产生过度拟合数据问题的原因有哪些？哪些？原因原因1 1：样本问题：样本问题 （1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；（什么是噪音数据？） （2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景； （3）建模时使用了样本中太多无关的输入变量。

原因原因2 2：构建决策树的方法问题：构建决策树的方法问题 在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂三三.如何解决过度拟合数据问题？如何解决过度拟合数据问题？针对原因针对原因1 1的解决方法：的解决方法： 合理、有效地抽样，用相对能够反映业务逻辑的训练 集去产生决策树；针对原因针对原因2 2的主要解决方法：的主要解决方法： 剪枝：提前停止树的增长或者对已经生成的树按照一 定的规则进行后剪枝1.3.2 C4.5的生成的生成算法算法l        C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，用信息增益比来选择特征1.4 决策树的剪枝决策树的剪枝l 算法算法1.4 树的剪枝算法树的剪枝算法l 关于剪枝的补充关于剪枝的补充——先剪枝先剪枝剪枝是一个简化过拟合决策树的过程有两种常用的两种常用的剪枝方法剪枝方法：       先剪枝（先剪枝（prepruning））：通过提前停止树的构建而对树“剪枝”，一旦停止，节点就成为树叶。

该树叶可以持有子集元组中最频繁的类；       有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：       1.定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；       2.达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长这种方法对于处理数据中的数据冲突问题非常有效；补充：关于剪枝补充：关于剪枝——先剪枝先剪枝 3.定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长； 4.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长 先剪枝方法不但相对简单，效率很高，而且不需要生成整个决策树，适合于解决大规模问题该方法看起来很直接，但要精确地估计决策树生长的停止时间并不容易，即选取一个恰当的阈值是非常困难的高阈值可能导致过分简化的树，而低阈值可能使得树的简化太少关于剪枝的补充关于剪枝的补充——后剪枝后剪枝 后剪枝（后剪枝（postpruningpostpruning））：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。

相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难补充：关于剪枝的准则补充：关于剪枝的准则无论是通过及早停止还是后修剪来得到正确规模的树，一个关键的问题是使用什么样的准则来确定最终正确一个关键的问题是使用什么样的准则来确定最终正确树的规模：树的规模： 1.使用训练集合(Training Set）和验证集合(Validation Set)，来评估剪枝方法在修剪结点上的效用 2.使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能 3.使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(Minimum Description Length)准则补充：关于剪枝的准则补充：关于剪枝的准则Reduced-Error Pruning(REP,Reduced-Error Pruning(REP,错误率错误率降低剪枝）降低剪枝） REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。

这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验REP——错误率降低剪枝错误率降低剪枝 该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点由如下步骤组成：       1：删除以此结点为根的子树       2：使其成为叶子结点       3：赋予该结点关联的训练数据的最常见分类       4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点    训练集合可能过拟合，使用验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)lPesimistic-Error Pruning(PEP,Pesimistic-Error Pruning(PEP,悲悲观错误剪枝）观错误剪枝） 悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。

把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定于是我们需要把子树的误判计算加上一个经验性的惩罚因子PEP——悲观错误剪枝悲观错误剪枝 对于一个叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N这个0.5就是惩罚因子，那么一棵子树，它有L个叶子节点，那么该子树的误判率估计为这样的话，我们可以看到一棵子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在PEP续的标准误差内对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布 那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：PEP续 把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶子节点的误判次数均值为 使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝： 这个条件就是剪枝的标准。

当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界PEP——小例题小例题T4这棵子树的误差率：子树误判次数的标准误差：子树替换为一个叶节点后，其误判个数为：7+0.5=7.5因为8.5+1.996>7.5，所以决定将子树T4替换这一个叶子节点lCost-Complexity PruningCost-Complexity Pruning（（CCPCCP，代价，代价复杂度剪枝复杂度剪枝) ) 该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数α，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为其中，|N1|：子树Tt中的叶节点数；R（t）：结点t的错误代价，计算公式为R（t）=r（t）*p（t），r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本 的比例；R（Tt）：子树Tt错误代价，计算公式为R（Tt）=∑R(i)，i为子树Tt的叶节点。

例子例子我们以非叶结点T4为例，假设已有的数据有60条，那么R(t)=r(t)*p(t)=(7/16)*(16/60)=7/60R（Tt）=∑R(i)=(2/5)*(5/60)+(0/2)*(2/60)+(3/9)*(9/60)=5/60α=（R(t)-R（Tt）)/(|N1|-1)=1/60CCP续续CCP剪枝算法分为两个步骤：两个步骤： 1.对于完全决策树T的每个非叶结点计算α值，循环剪掉具有最小α值的子树，直到剩下根节点在该步可得到一系列的剪枝树｛T0，T1，T2......Tm｝,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果； 2.从子树序列中，根据真实的误差估计选择最佳决策树CCP续续 通常使用1-SE（1 standard error of minimum error）规则从步骤1产生的一系列剪枝树中选择一棵最佳的剪枝决策树方法为，假定一个含有N＇个样本的剪枝集，分别用在步骤1中产生的剪枝树Ti对该剪枝集进行分类，记Ti所有叶结点上长生的错分样本数为Ei，令E＇=min｛Ei｝，定义E＇的标准错误为：，所得的最佳剪枝树Tbest是满足条件Ei≤E＇+SE（E＇）且包含的接点数最少的那棵剪枝树Ti。

l几种后剪枝方法的比较几种后剪枝方法的比较REPREPPEPPEPCCPCCP剪枝方式自底向上自顶向下自底向上是否需要独立剪枝集需要不需要不需要误差估计剪枝集上的误差估计使用连续校正标准误差计算复杂度O(n)O(n)O(n2)1.5 CART（分类与回归树）算法（分类与回归树）算法lCART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归lCART假设决策树是二叉树二叉树，内部结点特征的取值为“是”和“否这样的决策树等价于递归地二分每个特征步骤：（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准1.5.1 CART生成生成l决策树的生成就是递归地构建二叉决策树的过程对回归树用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择，生成二叉树最开始我们可以按：表面覆盖为毛发与非毛发表面覆盖为鳞片与非鳞片恒温与非恒温来产生当前结点的左右两个孩子我们将Gini指数来作为准则判别哪种划分比较好GINI指数指数l 1.5.2 CART剪枝剪枝l 实验结果实验结果UCI\method\precisioniriswineBreast-cancer感知机100%--KNN88%73.33%-朴素贝叶斯97.8%95.62%95.614%决策树100%96.4286%98.5507%解决决策树过拟合的另一种方法解决决策树过拟合的另一种方法——随机森林随机森林BootstrapingBootstraping的名称来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法。

注：Bootstrap本义是指高靴子口后面的悬挂物、小环、带子，是穿靴子时用手向上拉的工具pull up by your own bootstraps”即“通过拉靴子让自己上升”，意思是“不可能发生的事情”后来意思发生了转变，隐喻“不需要外界帮助，仅依靠自身力量让自己变得更好”解决决策树过拟合的另一种方法解决决策树过拟合的另一种方法——随机森林随机森林组合模型组合模型——Bagging的策略（三个臭皮匠的策略（三个臭皮匠顶个诸葛亮的意思）顶个诸葛亮的意思） *  bootstrap aggregation * 从样本集中重采样(有重复的)选出n个样本 * 在所有属性上，对这n个样本建立分类器(ID3、C4.5、             CART、SVM、Logistic回归等) *重复以上两步m次，即获得了m个分类器 *将数据放在这m个分类器上，最后根据这m个分类器           的投票结果，决定数据属于哪一类解决决策树过拟合的另一种方法解决决策树过拟合的另一种方法——随机森林随机森林解决决策树过拟合的另一种方法解决决策树过拟合的另一种方法——随机森林随机森林随机森林应用非常广泛，根据目标变量的取值类型大致可分为两类      一种是分类分类：当目标变量取值为离散型时（属性变量、种类变量、有序变量、多级变量等），采用该法可进行分类；        当目标变量为连续型，则可做回归，对应的预测结果是目标变量的分布。

      优点：可以产生高准确度的分类器解决决策树过拟合的另一种方法解决决策树过拟合的另一种方法——随机森林随机森林随机森林在bagging基础上做了修改 从样本集中用Bootstrap采样选出n个样本；* 从所有属性中随机选择k个属性，选择最佳分割属性           作为节点建立CART决策树；* 重复以上两步m次，即建立了m棵CART决策树* 这m个CART形成随机森林，通过投票表决结果，决•             定数据属于哪一类解决决策树过拟合的另一种方法解决决策树过拟合的另一种方法——随机森林随机森林随机森林随机森林/Bagging和决策树的和决策树的关系关系*  当然可以使用决策树作为基本分类器*  但也可以使用SVM、Logistic回归等其他分类器，习惯上，•       这些分类器组成的“总分类器”，仍然叫做随机森林回归问题回归问题        下图离散点是样本集合，描述了臭氧(横轴)和温度(纵轴)的关系，试拟合二者的变化曲线使用使用Bagging记原始数据为D，长度为N(即图中有N个离散点)•算法过程•做100次bootstrap，每次得到的数据Di，Di的长度为N•对于每一个Di，使用局部回归(LOESS)拟合一条曲线(图中灰色线是其中的10条曲线)•将这些曲线取平均，即得到红色的最终拟合曲线•显然，红色的曲线更加稳定，并且没有明显过拟合投票机制投票机制•简单投票机制简单投票机制•一票否决一票否决(一致表决一致表决)•少数服从多数少数服从多数•有效多数有效多数(加权加权)•阈值表决阈值表决•贝叶斯投票机制贝叶斯投票机制贝叶斯投票机制贝叶斯投票机制•简单投票法假设每个分类器都是平等的。

•在实际生活中，我们听取一个人的意见，会考虑这个人过去的意见是否有用，从而加大或者减少权值•贝叶斯投票机制基于每个基本分类器在过去的分类表现设定一个权值，然后按照这个权值进行投票投票机制举例投票机制举例•假定有N个用户可以为X个电影投票(假定投票者不能给同一电影重复投票)，投票有1、2、3、4、5星共5档•如何根据用户投票，对电影排序？•本质仍然是分类问题：对于某个电影，有N个决策树，每个决策树对该电影有1个分类(1、2、3、4、5类)，求这个电影应该属于哪一类(可以是小数：分类问题变成了回归问题)一种可能的方案一种可能的方案•WR：加权得分(weighted rating)•R：该电影的用户投票的平均得分(Rating)•C：所有电影的平均得分•v：该电影的投票人数(votes)•m：排名前250名的电影的最低投票数•根据总投票人数，250可能有所调整•按照v=0和m=0分别分析。