4. 决策树
https://gitee.com/fakerlove/machine-learning
4.1 基本流程
参考资料
https://www.cnblogs.com/molieren/articles/10664954.html
https://www.zhihu.com/question/22178202
https://blog.csdn.net/jiaoyangwm/article/details/79525237
https://www.cnblogs.com/yonghao/p/5135386.html4.1.1 简介
决策树是一种机器学习的方法。决策树的生成算法有ID3, C4.5和C5.0等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。
决策树是一种十分常用的分类方法，需要监管学习（有教师的Supervised Learning）
4.1.2 工作原理
决策树基本上就是把我们以前的经验总结出来。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？
4.1.3 概念
1) 构造
构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
- 根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
- 内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
- 叶节点：就是树最底部的节点，也就是决策结果。
节点之间存在父子关系。比如根节点会有子节点，子节点会有子子节点，但是到了叶节点就停止了，叶节点不存在子节点。那么在构造过程中，你要解决三个重要的问题：
- 选择哪个属性作为根节点；
- 选择哪些属性作为子节点；
- 什么时候停止并得到目标状态，即叶节点。
2) 剪枝
剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
过拟合：指的是模型的训练结果“太好了”，以至于在实际应用的过程中，会存在“死板”的情况，导致分类错误。
欠拟合：指的是模型的训练结果不理想。
剪枝的方法：
- 预剪枝：在决策树构造时就进行剪枝。方法是，在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。
- 后剪枝：在生成决策树之后再进行剪枝。通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。方法是：用这个节点子树的叶子节点来替代该节点，类标记为这个节点子树中最频繁的那个类。
决策树的生成主要分以下两步，这两步通常通过学习已经知道分类结果的样本来实现。
- 节点的分裂：一般当一个节点所代表的属性无法给出判断时，则选择将这一节点分成2个子节点（如不是二叉树的情况会分成n个子节点）
- 阈值的确定：选择适当的阈值使得分类错误率最小 （Training Error）。
4.2 划分选择
4.2.0 前期准备
介绍两个指标**：纯度和信息熵**。
1) 纯度
你可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小。
举个例子，假设有 3 个集合：
- 集合 1：6 次都去打篮球；
- 集合 2：4 次去打篮球，2 次不去打篮球；
- 集合 3：3 次去打篮球，3 次不去打篮球。
按照纯度指标来说，集合 1> 集合 2> 集合 3。因为集合1 的分歧最小，集合 3 的分歧最大。
2) 熵
熵是一种事物的不确定性叫做熵
3) 信息
能够消除该人对这件事情的不确定性叫做信息
信息量
- 调整概率
- 排除干扰
- 确定情况
噪音是信息获取的干扰
数据是信息+噪音
对于一道题A,B，C,D的人，正确答案是C
小红知道这道题答案为C，小红的熵为0，因为她没有不确定性
小黄不知道这道题的答案，A,B,C,D 每道题概率1/4 ,熵为2,有不确定性。
小白告诉小黄答案是D,小红告诉小黄答案是C。这个时候的小白就是噪音
信息是相对的
太阳从东边升起
对于知道的人而言，熵为0
对于可能从东西的人而言，熵为1
对于东南西北都有可能的人而言，熵为2
对于同一件事情，不同人的熵不一样
4) 信息熵
性质
- 单调性，发生概率越高的事件，其携带的信息量越低；
- 非负性，信息熵可以看作为一种广度量，非负性是一种合理的必然；
- 累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和，这也是广度量的一种体现。
类似于阴阳的叫法，正反两面
在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵的概念，并给出了计算信息熵的数学公式：
代表节点为分类i的概率
信息熵反映出一个信息的不确定度，当一个事件的不确定性越大，所包含的信息量越大，信息熵越大
举个例子，假设有 2 个集合：
- 集合 1：5 次去打篮球，1 次不去打篮球；
- 集合 2：3 次去打篮球，3 次不去打篮球。
在集合 1 中，有 6 次决策，其中打篮球是 5 次，不打篮球是 1 次。那么假设：类别 1 为“打篮球”，即次数为 5；类别 2 为“不打篮球”，即次数为 1。那么节点划分为类别1的概率是 5/6，为类别2的概率是1/6，带入上述信息熵公式可以计算得出：
信息熵=
同样，集合 2 中，也是一共 6 次决策，其中类别 1 中“打篮球”的次数是 3，类别 2“不打篮球”的次数也是 3，那么信息熵为多少呢？我们可以计算得出：
信息熵=
从上面的计算结果中可以看出，信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。
我们在构造决策树的时候，会基于纯度来构建。而经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。
4.2.1 信息增益ID3
1) 简介
信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。
在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。所以信息增益的公式可以表示为：
公式D是父亲节点，是子节点，Gain(D,a)中的a作为D节点的属性选择
2) 流程
例一：
假设D 天气 = 晴的时候，会有 5 次去打篮球，5 次不打篮球。
其中 D1 刮风 = 是，有 2 次打篮球，1 次不打篮球。
D2 刮风 = 否，有 3 次打篮球，4 次不打篮球。那么a 代表节点的属性，即天气 = 晴。
此时节点D的信息增益为
例二
如果你将天气作为属性的划分，会有三个叶子节点 D1、D2 和D3，分别对应的是晴天、阴天和小雨。我们用 + 代表去打篮球，- 代表不去打篮球。那么第一条记录，晴天不去打篮球，可以记为 1-，于是我们可以用下面的方式来记录 D1，D2，D3：
D1(天气 = 晴天)={1-,2-,6+\}
D2(天气 = 阴天)={3+,7-\}
D3(天气 = 小雨)={4+,5-\}
我们先分别计算三个叶子节点的信息熵：
因为 D1 有 3 个记录，D2 有 2 个记录，D3 有2 个记录，所以 D 中的记录一共是 3+2+2=7，即总数为 7。所以 D1 在 D（父节点）中的概率是 3/7，D2在父节点的概率是 2/7，D3 在父节点的概率是 2/7。那么作为子节点的归一化信息熵,信息增益=
同理我们可以计算出其他属性作为根节点的信息增益，它们分别为：
Gain(D , 温度)=0.128
Gain(D , 湿度)=0.020
Gain(D , 刮风)=0.020
我们能看出来温度作为属性的信息增益最大。
因为 ID3 就是要将信息增益最大的节点作为父节点，这样可以得到纯度高的决策树，所以我们将温度作为根节点。
其决策树状图分裂为下图所示：
然后我们要将上图中第一个叶节点，也就是 D1={1-,2-,3+,4+}进一步进行分裂，往下划分，计算其不同属性（天气、湿度、刮风）作为节点的信息增益，可以得到：
Gain(D , 天气)=0
Gain(D , 湿度)=0
Gain(D , 刮风)=0.0615
我们能看到刮风为 D1 的节点都可以得到最大的信息增益，这里我们选取刮风作为节点。
同理，我们可以按照上面的计算步骤得到完整的决策树，结果如下：
3) 缺点
有些属性可能对分类任务没有太大作用，但是他们仍然可能会被选为最优属性。
这种缺陷不是每次都会发生，只是存在一定的概率。在大部分情况下，ID3 都能生成不错的决策树分类。针对可能发生的缺陷，后人提出了新的算法进行改进。
4.2.2 增益率C4.5
1) 简介
为了解决上面的问题，发明了C4.5 决策树算法
不直接使用信息增益，而是采用增益率来选择最优划分属性
信息增益率=
其中称为属性a的固定值，属性a的可能取值数目越大，即V越大，IV值越大
2) 改进的地方
采用悲观剪枝
ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。
悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。
离散化处理连续属性
C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。
处理缺失值
针对数据集不完整的情况，C4.5 也可以进行处理。
假如我们得到的是如下的数据，你会发现这个数据中存在两点问题。第一个问题是，数据集中存在数值缺失的情况，如何进行属性选择？第二个问题是，假设已经做了属性划分，但是样本在这个属性上有缺失值，该如何对样本进行划分？
我们不考虑缺失的数值，可以得到温度 D={2-,3+,4+,5-,6+,7-}。
温度 = 高：D1={2-,3+,4+}；
温度 = 中：D2={6+,7-}；
温度 = 低：D3={5-} 。
这里 + 号代表打篮球，- 号代表不打篮球。比如ID=2 时，决策是不打篮球，我们可以记录为 2-。
所以三个叶节点的信息熵可以结算为：
这三个节点的归一化信息熵为 。
针对将属性选择为温度的信息增益率为：
Gain(D′, 温度)=Ent(D′)-0.792=1.0-0.792=0.208
D′的样本个数为 6，而 D 的样本个数为 7，所以所占权重比例为 6/7，所以 Gain(D′，温度) 所占权重比例为6/7，所以：
Gain(D, 温度)=6/7*0.208=0.178
这样即使在温度属性的数值有缺失的情况下，我们依然可以计算信息增益，并对属性进行选择。
3) 小结
首先 ID3 算法的优点是方法简单，缺点是对噪声敏感。训练数据如果有少量错误，可能会产生决策树分类错误。C4.5 在 IID3 的基础上，用信息增益率代替了信息增益，解决了噪声敏感的问题，并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况，但是由于 C4.5 需要对数据集进行多次扫描，算法效率相对较低。
4.2.3 基尼指数CART
1) 简介
https://www.cnblogs.com/keye/p/10564914.htmlCART算法（classification and regression tree）分类和回归算法，是一种应用广泛的决策树学习方法
CART算法既可以用于分类还可以用于回归。CART决策树的生成就是递归的构建二叉树，但是针对分类和回归使用的策略是不一样的，对于回归树，使用的是平方误差最小准则;而对于分类树，使用的是基尼指数最小化准则。
CART决策树使用基尼指数来选择划分属性
CART分类树算法使用，基尼系数代表了模型的不纯度，。这和信息增益（比）相反。
基尼值
假设个类别，第个类别的概率为，概率分布的基尼值表达式：
越小，数据集D的纯度越高
基尼指数
属性a的基尼指数定义为
二分类
对于一个二分类问题，第一个样本输出概率为,基尼系数表达式为
2) 流程
- 对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，则返回决策子树，当前节点停止递归。
- 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
- 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和C4.5算法里描述的相同。
- 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。
- 对左右的子节点递归的调用1-4步，生成决策树。
对生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。
例子
3) 对连续特征和离散特征的处理
CART分类树算法对连续值的处理，思想和C4.5相同，都是将连续的特征离散化。
唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。
具体思路：m个样本的连续特征A有m个，从小到大排列，则CART取相邻两样本值的平均数做划分点，一共取m-1个，其中第i个划分点Ti表示为：。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为，则小于的值为类别1，大于的值为类别2，这样就做到了连续特征的离散化。
注意的是，与ID3、C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性在后面还可以参与子节点的产生选择过程。
CART分类树算法对离散值的处理，采用的思路：不停的二分离散特征。
在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别，我们会在决策树上建立一个三叉点，这样决策树是多叉树。
CART采用的是不停的二分。会考虑把特征A分成和、和三种情况，找到基尼系数最小的组合，比如，然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开，后面还有机会对子节点继续选择特征A划分。这和ID3、C4.5不同，在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。
4) CART回归树建立算法
5) CART剪枝
https://blog.csdn.net/wjlwangluo/article/details/78797759
https://blog.csdn.net/intricate_/article/details/1050417966) 优缺点
优点：
- 简单直观，生成的决策树很直观。
- 基本不需要预处理，不需要提前归一化和处理缺失值。
- 使用决策树预测的代价是O(log2m)。m为样本数。
- 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
- 可以处理多维度输出的分类问题。
- 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以很好解释。
- 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
- 对于异常点的容错能力好，健壮性高。
缺点：
- 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
- 决策树会因为样本发生一点的改动，导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
- 寻找最优的决策树是一个NP难题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习的方法来改善。
- 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
- 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
4.2.4 小结
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分类回归 | 二叉树 | 基尼系数 均方差 | 支持 | 支持 | 支持 |
CART算法缺点：
无论ID3，C4.5，CART都是选择一个最优的特征做分类决策，但大多数，分类决策不是由某一个特征决定，而是一组特征。
这样得到的决策树更加准确，这种决策树叫多变量决策树(multi-variate decision tree)。
在选择最优特征的时，多变量决策树不是选择某一个最优特征，而是选择一个最优的特征线性组合做决策。代表算法OC1。
样本一点点改动，树结构剧烈改变。这个通过集成学习里面的随机森林之类的方法解决。
信息熵与基尼指数的关系
https://www.jianshu.com/p/75518e6a5c64
https://blog.csdn.net/qq_39408570/article/details/89764177Gini 指数的计算不需要对数运算，更加高效； Gini 指数更偏向于连续属性，熵更偏向于离散属性。
4.3 剪枝处理
参考资料
https://blog.csdn.net/am290333566/article/details/81187562
https://blog.csdn.net/u012328159/article/details/79285214
https://www.cnblogs.com/lysuns/articles/4736155.html后剪枝算法
https://blog.csdn.net/weixin_43216017/article/details/87534496剪枝处理是决策树学习算法树对付过拟合的主要手段。
4.3.1 预剪枝
1) 概念
预剪枝是指在决策树生成过程中。对每个结点在划分前先进行评估，
若当前结点的划分不能带来决策树的泛化性能提升。则停止划分并将当前结点标记为叶结点，
2) 流程如下
下面把样本进行分类
如果不进行剪枝处理，直接使用信息增益ID3方法，画出的决策树。如下图所示：
计算过程如下
因为色泽和脐部的信息增益值最大，所以从这两个中随机挑选一个，这里选择脐部来对数据集进行划分，这会产生三个分支，如下图所示：
划分规则如下
举例
划分前：所有样本都在根节点，把该结点标记为叶结点，其类别标记为训练集中样本数量最多的类别。好瓜
然后我们把好瓜的标准应用到验证集上，全部判断为好瓜，但是验证集上的结果为{3,4}。3个好瓜，判断正确，4个坏瓜判断错误
正确率
划分后的的决策树为：
划分后，在验证集上结果正确率。于是脐部得以划分
决策树算法对结点 (2) 进行划分，再次使用信息增益挑选出值最大的那个特征，这里我就不算了，计算方法和上面类似，信息增益值最大的那个特征是“色泽”，则使用“色泽”划分后决策树为：
但到底该不该划分这个结点，还是要用验证集进行计算，
可以看到划分后，精度为：4/7=0.571<0.714，因此，预剪枝策略将禁止划分结点 (2) 。
对于结点 (3) 最优的属性为“根蒂”，划分后验证集精度仍为71.4%，因此这个划分不能提升验证集精度，所以预剪枝将禁止结点 (3) 划分。
对于结点 (4) ，其所含训练样本已属于同一类，所以不再进行划分。
所以基于预剪枝策略生成的最终的决策树为：
3) 小结
对比未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛华性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
4.3.2 后剪枝
1) 概念
后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，
若将该结点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶结点
2) 流程如下
我们考察6 节点，是最底下的非叶子节点。替换前
在验证集上的正确率为42.9%
若将以其为根节点的子树删除，即相当于把结点 (6) 替换为叶结点，替换后的叶结点包括编号为{7,15}的训练样本，
因此把该叶结点标记为“好瓜”（因为这里正负样本数量相等，所以随便标记一个类别），
此时的决策树在验证集上的精度为57.1%（为剪枝的决策树为42.9%），所以后剪枝策略决定剪枝，
剪枝后的决策树如下图所示：
接着考察结点 5，同样的操作，把以其为根节点的子树替换为叶结点，替换后的叶结点包含编号为{6,7,15}的训练样本，根据“多数原则”把该叶结点标记为“好瓜”，测试的决策树精度认仍为57.1%，所以不进行剪枝。
考察结点 2 ，和上述操作一样，不多说了，叶结点包含编号为{1,2,3,14}的训练样本，标记为“好瓜”，此时决策树在验证集上的精度为71.4%，因此，后剪枝策略决定剪枝。剪枝后的决策树为：
接着考察结点 3 ，同样的操作，剪枝后的决策树在验证集上的精度为71.4%，没有提升，因此不剪枝；对于结点 1 ，剪枝后的决策树的精度为42.9%，精度下降，因此也不剪枝。 因此，基于后剪枝策略生成的最终的决策树如上图所示，其在验证集上的精度为71.4%。
3) 小结
对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。
4) 常见的后剪枝算法
错误率降低剪枝法
错误率降低剪枝法(Reduced-Error Pruning)简称REP方法。
顾名思义，该剪枝方法是根据错误率进行剪枝，如果一棵子树修剪前后错误率没有下降，就可以认为该子树是可以修剪的。
REP剪枝需要用新的数据集，原因是如果用旧的数据集，不可能出现分裂后的错误率比分裂前错误率要高的情况。由于使用新的数据集没有参与决策树的构建，能够降低训练数据的影响，降低过拟合的程度，提高预测的准确率。
REP方法是通过一个新的验证集来纠正树的过拟合问题。对于决策树中的每一个非叶子节点的子树，我们将它替换成一个叶子节点，该叶子节点的类别用大多数原则来确定，这样就产生了一个新的相对简化决策树，然后比较这两个决策树在验证集中的表现。
如果新的决策树在验证集中的正确率较高，那么该子树就可以替换成叶子节点，从而达到决策树剪枝的目的。
该算法是从下往上依次遍历所有的子树，直至没有任何子树可以替换使得在验证集上的表现得以改进时，算法就可以终止。
实例：
生成的决策树，我们要对其进行剪枝，使用REP算法。 Step 1： 将节点4删掉替换成8和9，测试在验证集上的表现，若表现更好，则将节点4删掉并替换成8和9的并集，若表现不好则保留原树的形状。 Step 2： 将节点2删掉替换成8、9和5，测试在验证集上的表现 Step 3： 将节点3删掉替换成6和7，测试在验证集上的表现
悲观剪枝
上文的REP方法思想简单且易于使用，不过最大的问题在于它需要一个新的验证集来修正我们的决策树。在PEP方法中，我们不需要新的验证集。
PEP方法也是根据剪枝前后的错误率来决定是否剪枝。和REP不同之处在于：PEP不需要新的验证集，并且PEP是自上而下剪枝的。由于我们还是用生成决策树时相同的训练样本，那么对于每个节点剪枝后的错分率一定是会上升的，因此在计算错分率时需要加一个惩罚因子0.5。
对于一叶节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为：
我们假设在子树中每一个样本的误判服从一个二项分布，其中N表示子树所包含的所有样本个数。
所以，在剪枝前，其期望的误判数为： E(剪枝前误判数)=
其误判的标准差为： std(剪枝前误判数)
在剪枝之后，把子树替换成叶节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶节点的误判次数均值为: E(剪枝后误判数)$ = N*e$
当子树的误判个数大于对应叶节点的误判个数一个标准差之后，就决定剪枝。剪枝条件为： E(剪枝后误判数) -std(剪枝前误判数)<E(剪枝前误判数) 例子
对于节点T4而言，剪枝前后的计算过程如下：
所以，剪枝前的误判概率为： 所以： E(剪枝前误判数)
std(剪枝前误判数)
在我们对T4进行剪枝后，即将T4直接作为叶节点，剪枝后的误判概率 剪枝后的误判期望数为： E(剪枝后误判数)$ = 20*0.375 = 7.5$
剪枝条件为：
因此满足条件，所以我们将把T4节点剪枝。
代价复杂度剪枝法
代价复杂度算法(Cost-Complexity Pruning)简称为CCP算法。
CCP算法为子树定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数α。
代价指的是在剪枝过程中因子树被叶节点替代而增加的错分样本;
复杂度表示剪枝后子树减少的叶结点数;
则表示剪枝后树的复杂度降低程度与代价间的关系，定义为:
其中，表示节点t的错误代价，表示节点t的错分样本率； 表示节点t中样本占全部样本的比例 表示子树中的叶节点数
CCP算法可以分为两个步骤，
Step 1： 按照上述公式从下到上计算每一个非叶节点的值，然后每一次都剪掉具有最小值的子树。从而得到一个集合，其中表示完整的决策树，表示根节点
Step 2： 根据真实的错误率在集合选出一个最好的决策树
假设数据有100条，从下往上，首先计算的值，
同理，的为0.03，由于此时，我们将剪掉而得到一颗新树。
4.4 连续与缺失值
4.4.1 连续值处理
概念
到目前为止我们仅讨论了基于离散属性来生成决策树，现实学习任务中常常遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。我们将相邻的两个属性值的平均值作为候选点。
基本思路：连续属性离散化。
常见做法：二分法（这正是C4.5决策树算法中采用的机制）。
对于连续属性a,
我们可考察包括n-1个元素的候选划分集合
将区间$[a^i,a^{i+1}) \frac{a^i+a^{i+1}}{2}$作为候选点。对这些候选点进行信息增益考察
过程如下
假设有连续属性a,D=。例如学生成绩，有n个学生，学生成绩在[0,100]区间内,假设学生成绩
排序后
第一个划分点是
第二个划分点是
依次类推，最后T=
计算信息增益
依次类推算出
当算出所有的信息增益，找出最大的那个。然后选择最大的那个作为分类
西瓜书的例子
根节点包含的17个训练样本在该属性上取值均不同。该属性的候选划分点集合包括16个候选值：
计算可知属性“密度”信息增益为0.262，对应划分点0.381.
对属性“含糖率”，其候选划分点集合也包括16个候选值：
计算可知其信息增益为0.349，对应于划分点0.126.
类似的，计算得到的各属性的信息增益值：
比较能够知道纹理的信息增益值最大，因此，“纹理”被选作根节点划分属性，下面只要重复上述过程递归的进行，就能构造出一颗决策树：
4.4.2 缺失值处理
缺失值是指一个样本的某些属性值有缺失。 当属性值有缺失时要解决两个问题
在决策树中处理含有缺失值的样本的时候，需要解决两个问题：
- 如何在属性值缺失的情况下进行划分属性的选择？（比如“色泽”这个属性有的样本在该属性上的值是缺失的，那么该如何计算“色泽”的信息增益？）
- 给定划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？（即到底把这个样本划分到哪个结点里？）
例子
假设有训练集D,样本有属性a,现将训练集中a属性无缺失的样本放入,a的取值可能集合为对属性集做一些处理：
按属性值：$ \tilde{D}a_i\tilde{D}^{v}\tilde{D}\tilde{D}=\bigcup_{v=1}^{V}$
按类别：假设训练集有个类，中第$ (k=1,2, \dots,|\mathcal{Y}|)\tilde{D}{k}\tilde{D}=\bigcup{k=1}^{|y |}\tilde{D}_k$
假设D中某个样本为x，为x赋权值w,（样本权重初始值为1，后面会用到）并且定义：
此时重新定义信息增益计算方式来选择最优属性：
表示按a的属性值进行划分$ \tilde{D}^{1}, \tilde{D}^{2},..., \tilde{D}^{v}\tilde{r}_{v}$(该属性值无缺失的比例占整个无缺失样本的比例)，然后求和。
首先选取色泽为例
={2,3,4,6,7,8,10,11,12,14,15,16,17}的14个样例,
“色泽=乌黑”={2,3,7,9,8,15},6个样本
“色泽=青绿”={4,6,10,17}，4个样本
“色泽=浅白”={11,12,14,16},4个样本
的信息熵
14个样本中6个好的，8个坏的。
“色泽=乌黑”={2,3,7,9,8,15},6个样本。4个好的，2个坏的
“色泽=青绿”={4,6,10,17}，4个样本。2个好的，2个坏的
“色泽=浅白”={11,12,14,16},4个样本。0个好的，4个坏的
上的信息增益为
因为根节点的
依次类推把所有属性的信息增益算出来
所以选择纹理
F={1,2,3,4,5,6,7,9,11,12,13,14,15,16,17}
其中{8,10}是缺失样本
“纹理=稍糊”分支：{7,9,13,14,17}，“纹理=清晰”分支：{1,2,3,4,5,6,15}，“纹理=模糊”分支：{11,12,16}
那么问题来了，编号为{8,10}的样本在“纹理”这个属性上是缺失的，该被划分到哪个分支里？
前面讲过了，这两个样本会同时进入到三个分支里，只不过进入到每个分支后权重会被调整（前面也说过，在刚开始时每个样本的权重都初始化为1）。
编号为8的样本进入到三个分支里后，权重分别调整为5/15，7/15 和 3/15；
编号为10的样本同样的操作和权重。因此，经过第一次划分后的决策树如下图所示：
接下来，递归执行“纹理=稍糊”这个分支，样本集，共7个样本。如下图所示：
此时 为无缺失样本所占比例。选取色泽为例。确实样为13
对比能够发现属性“敲声”的星系增益值最大，因此选择“敲声”作为划分属性，划分后的决策树如下图所示：
我们都知道构造决策树的过程是一个递归过程，原来不打算继续介绍递归过程了，但是因为权重发生了变化，所以继续介绍下递归过程
最终到结果为
4.5 多变量决策树
https://blog.csdn.net/weixin_44132485/article/details/106502422