一、决策树

决策树的学习过程包括三个步骤：

a）特征选择。不同的特征和预测目标具有不同强度的相关性，选择相关性最强的特征能够有效提高预测效果。

b）节点分裂。训练集会在决策树中按照节点规则分流，如果 节点A 没办法给出一个满意的分类结果，那它就会选择分裂，分成 2 个或者多个节点。那么根据什么分裂呢？节点A 会用熵来判断用哪个特征分裂是最优的。

c）剪枝。决策树不加限制地分裂容易产生过拟合现象，剪枝可以一定程度地缓解过拟合，提高泛化能力。

决策树的学习算法有多种，常用的有：ID3，C4.5，CART。下面逐个介绍

1、ID3

前言

1.1计算公式

1.2例子

以如下样本为例：







当我们最左侧的纹理清晰的子集D1进行第二次分裂时，可以计算D1的信息熵：

7好2坏

此时对于 D1 子集的触感属性进行属性不同取值区间的信息熵计算得出，当触感硬滑时：
6好0坏

当纹理清晰触感软粘时：
1好2坏

1.3 剪枝策略

无

1.4优缺点

缺点：

• 1、对于连续性变量其无法进行分裂，
• 2、信息增益对取值比较多的属性友好；这也决定了这种算法的局限性，因此我们将引出第二个算法C4.5。信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• ID3 没有剪枝策略，容易过拟合；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。

2、C4.5

2.1 计算公式

另一种写法：

2.2 例子

2.2.1那么续型变量该怎样计算信息增益呢？

只需将连续型变量由小到大递增排序，取相邻两个值的中点作为分裂点进行二分类，然后按照离散型变量计算信息增益的方法计算信息增益，取其中最大的信息增益作为最终的分裂点
如求修障时长的信息增益，首先将修障时长递增排序，即10.2、12、14、16、18、20、22、23、24、25,取相邻两个值的中点，如10.2和12，中点即为11.1，因此可以求得：

2.3 剪枝策略

引入悲观剪枝策略进行后剪枝；
为什么要剪枝：过拟合的树在泛化能力的表现非常差。
用“留出法”（总数据集里抽出一部分作为测试集）区分出训练集和测试集，前面计算公式是用训练集，后面剪枝与否是看测试集的数据结果（测试集的准确率）

2.3.1 预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：
节点内数据样本低于某一阈值；
所有节点特征都已分裂；
节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

2.3.2 后剪枝

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

详细内容参考：

决策树总结（三）剪枝
决策树的剪枝：CPP[代价复杂度剪枝]
决策树剪枝：PEP 悲观错误率剪枝
决策树剪的剪枝：REP [降低误差剪枝法]

2.4 优缺点

对比ID3
优点：

• 1 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1
  个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；

• 2 解决了对特征分类数的依赖，引入信息增益率作为划分标准

• 3 对于缺失值的处理，有所改进：

• 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）

• 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）

• 针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；

• 针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

缺点：

• 剪枝策略可以再优化；
• C4.5 用的是多叉树，用二叉树效率更高； C4.5 只能用于分类；
• C4.5使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
• C4.5在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行

3—1、CART（基尼指数：用于分类）

ID3和C4.5都是多叉树，而CART是二叉树，内部节点的取值为“是”或“否”。并且CART既可用于分类，也可用于回归。

3.1 计算公式

3.1.1对于二分类：

3.1.2 对ID3和C4.5的改进

-ln（p（y））=1-p（y）

3.2 相关处理

3.2.1 分类树如何生成

生成分类树的过程与 ID3 和 C4.5 类似。从根节点开始，对每个特征的每个切分点计算基尼指数，选择最小的那个作为最优特征和最优切分点（或选基尼指数增益（率）最大的）。现在这个节点就可以分裂了( •̀ ω •́ )✧，直到节点样本数量太少或者基尼指数太小或者特征不够了才停止。叶子节点上的最终类别是这个叶子节点上样本数量最多的那个。

3.2.2缺失值处理

上文说到，模型对于缺失值的处理会分为两个子问题：如何在特征值缺失的情况下进行划分特征的选择？选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？
对于问题 1，CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。
对于问题 2，CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

3.2.3 类别不平衡

3.3例子

通过计算选择基尼指数增益最大的变量进行分裂，以如下数据为例：

当根据是否有房来进行划分时，基尼指数增益计算过程为：



若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的，
当分组为{married} | {single,divorced}，
当分组为{single} | {married,divorced}，
当分组为{divorced} | {single,married}时

对比计算结果，根据婚姻状况属性来划分根节点时取基尼指数增益最大的分组作为划分结果

通过不断地递归分裂可以最终求得CART分类树为：

CART和C4.5最大的区别就是选择分裂点时候的计算逻辑，一个是基尼指数的增益率一个是信息增益率，此外就是CART一定是二叉树C4.5未必是。

3—2、CART（平方误差 ：用于回归）

理解CART回归树会很好的帮助大家理解XGBoost算法
要强调的是CART决策树是二叉树，内部结点特征的取值只有“是”和“否”，左分支是取值为“是”的分支，有分支则相反。这样的决策树等价于递归地二分每个特征。

3.1 计算公式

x是样本点


通过使用平方误差最小准则计算出左右子集的平均误差和最小时 ，A特征的分裂点 s为最佳分裂点：

特征A 和切分点S可以通过遍历求得。在得到这一个节点的最优特征和最优切分点后，可以将训练样本分成两半，传递到两个孩子节点。然后对节点分裂过程疯狂递归，直到满足设定的条件为止，回归树就生成完了

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

3.2 例子

注：XGBoost是多个回归树的集合，那么是不是XGBoost也是这么分裂变量的呢，结论是当然不是，XGBoost有着一套自定义的分裂逻辑，但是其本质也是CART回归树，只不过他在前人的基础上进行了改进，

3.3 剪枝策略

采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。

这是代价复杂度剪枝的核心思想。

我们每次剪枝都是针对某个非叶节点，其他节点不变，所以我们只需要计算该节点剪枝前和剪枝后的损失函数即可。

3.4 优缺点

对比C4.5，提升：

• C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
• C4.5 只能分类，CART 既可以分类也可以回归；
• CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
• CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
• CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

4、总结比较

最后通过总结的方式对比下 ID3、C4.5 和 CART 三者之间的差异。
除了之前列出来的划分标准、剪枝策略、连续值确实值处理方式等之外，我再介绍一些其他差异：

• 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
• 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；剪枝策略的差异：ID3 没有剪枝策略，C4.5是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

最详细的XGBoost推导过程–关于XGBoost我所知道的一切
微痛学习 决策树