ixxmu
commented
10 months ago 5.图解机器学习 | 回归树模型详解 by 生信小知识
5.图解机器学习 | 回归树模型详解
微信公众号：生信小知识
关注可了解更多的生物信息学教程及知识。问题或建议，请公众号留言;
目录
前言1.决策树回归算法核心思想1）决策树结构回顾2）回归树的核心思想2.启发式切分与最优属性选择1）回归树模型示例2）回归树构建方法（1）贪婪式递归（2）递归二分3.过拟合与正则化1）过拟合问题2）过拟合问题处理（1）约束控制树的过度生长（2）剪枝3）正则化后记
前言
本系列内容均来自 ShowMeAI 论坛：https://www.showmeai.tech/
该论坛中内容详实，部分系列非常适合数学功底不那么好的同学学习，这里仅对 【图解机器学习】系列进行学习，并同时整理为笔记。
过往已发布笔记：
今天主要介绍回归树的原理知识。
大家在前面的部分学习到了使用决策树进行分类，实际决策树也可以用作回归任务，我们叫作回归树。而回归树的结构还是树形结构，但是属性选择与生长方式和分类的决策树有不同。
本公众号已与ShowMeAI论坛负责人联系，并得到授权转载。在次给做机器学习的朋友们推荐下他们的微信公众号，有兴趣的同学可以自行关注。
1.决策树回归算法核心思想
1）决策树结构回顾
我们一起来回顾一下决策树的结构，决策树的典型结构如下图所示。
决策树的学习过程和预测过程如下图所示：
详细内容可以参考[3.图解机器学习 | 决策树模型详解]()。
主流的决策树算法有：
ID3：基于信息增益来选择分裂属性（每步选择信息增益最大的属性作为分裂节点，树可能是多叉的）。
C4.5：基于信息增益率来选择分裂属性（每步选择信息增益率最大的属性作为分裂节点，树可能是多叉的）。
CART：基于基尼系数来构建决策树（每步要求基尼系数最小，树是二叉的）。其中：CART树全称Classification And Regression Tree，即可以用于分类，也可以用于回归，这里指的回归树就是 CART 树，ID3和C4.5不能用于回归问题。
2）回归树的核心思想
要讲回归树，我们一定会提到CART树，CART树全称Classification And Regression Trees，包括分类树与回归树。
CART的特点是：假设决策树是二叉树，内部结点特征的取值为「是」和「否」，右分支是取值为「是」的分支，左分支是取值为「否」的分支。
这样的决策树等价于「递归地二分每个特征」，将输入空间（特征空间）划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
设有数据集D，构建回归树的大体思路如下：
① 考虑数据集 D 上的所有特征 j，遍历每一个特征下所有可能的取值或者切分点 s，将数据集 D 划分成两部分 D1 和 D2 。
② 分别计算 D1 和 D2 的平方误差和，选择最小的平方误差对应的特征与分割点，生成两个子节点（将数据划分为两部分）。
③ 对上述两个子节点递归调用步骤 ① ②，直到满足停止条件。
回归树构建完成后，就完成了对整个输入空间的划分（即完成了回归树的建立）。将整个输入空间划分为多个子区域，每个子区域输出为该区域内所有训练样本的平均值。
我们知道了回归树其实是将输入空间划分为M个单元，每个区域的输出值是该区域内所有点y值的平均数。但我们希望构建最有效的回归树：预测值与真实值差异度最小。下面部分我们展开讲讲，回归树是如何生长的。
2.启发式切分与最优属性选择
1）回归树模型示例
我们用一个经典的棒球案例来解释回归树：根据从业年限和表现，去预估棒球运动员的工资。如下所示，有1987个数据样本，包含322个棒球运动员（数据同一个运动员在不同年份的数据）：
横坐标是年限。
纵坐标是表现。
红黄表示高收入，蓝绿表示低收入。
这个简单案例中，每个样本数据有两个特征：从业年限years 和成绩表现hits，回归树的决策过程由最终生成的回归树决定，如右图所示：
根决策节点是特征years，其划分阈值为4.5，years≤4.5的样本划分到左边，＞4.5的样本划分到右边
第二个决策节点的特征为hits，其划分阈值为117.5，hits≤117.5的样本划分到左边，＞117.5的样本划分到右边。
一个样本顺着决策树的决策条件，走到叶子节点，即可获得预测工资，这里的预测工资总共就3种取值，分别为5.11、6.00、6.74。
我们来深入拆解和对应一下，其实回归树构建完成后，实现了对整个空间的划分，如下图所示：
实际预测时，新样本会按照回归树的决策过程，被划分到下图R1、R2、R3之中的一个区域 Ri，而这个新样本的预测值（本案例中为棒球运动员的工资）就是它所在区域中所有训练样本的工资平均值。
2）回归树构建方法
下面切到回归树构建的核心：切分方式与属性选择。
假设一回归问题，预估结果y∈R，特征向量为X=[x1, x2, x3, …, xp]，回归树2个步骤是：
① 把整个特征空间 X 切分成 J 个没有重叠的区域R1, R2, R3, …, RJ
② 每个分化的区域中，所有样本我们都给一样的预测结果：区域中所有样本的平均值。
（1）贪婪式递归
仔细观察一下上面的过程，实际上我们希望能找到如下的 RSS 最小的化划分方式 R1, R2, R3, …, RJ：
y：每个训练样本的标签构成的标签向量，向量中的每个元素 yi 对应的是每个样本的标签。
X：特征的集合，x1, x2, x3, …, xp 为第1个特征到第p个特征。
R1, R2, R3, …, RJ：整个特征空间划分得来的 J 个不重叠的区域。
y~Rj：划分到第 j 个区域 Rj 的所有样本平均标签值，用这个值作为该区域的预测值，即如果有一个测试样本在测试时落入到该区域，就将该样本的标签值预测为 y~Rj 。
回归树采用的是「自顶向下的贪婪式递归方案」。这里的贪婪，指的是每一次的划分，只考虑当前最优，而不回头考虑之前的划分。
从数学上定义，即选择切分的特征 xj 以及切分点 s 使得划分后的树RSS结果最小，公式如下所示：
但是这个最小化和探索的过程，计算量是非常非常大的。我们采用「探索式的递归二分」来尝试解决这个问题。
（2）递归二分
我们再来看看「递归切分」。下方有两个对比图，其中左图是非递归方式切分得到的，而右图是二分递归的方式切分得到的空间划分结果（下一次划分一定是在之前的划分基础上将某个区域一份为二）。
两种方式的差别是：
递归切分一定可以找到一个较优的解
非递归切分穷举不了所有情况，算法上无法实现，可能无法得到一个较好的解。
回归树总体流程类似于分类树：分枝时穷举每一个特征可能的划分阈值，来寻找最优切分特征和最优切分点阈值，衡量的方法是平方误差最小化。分枝直到达到预设的终止条件（如叶子个数上限）就停止。
这部分内容感觉没有说清楚关于贪婪式递归和递归二分具体的差异，似乎只说明了贪婪式递归的方法。不过这也足够了。
关于贪婪式递归的计算方法，详细可以参考：https://zhuanlan.zhihu.com/p/82054400
但通常在处理具体问题时，单一的回归树模型能力有限且有可能陷入过拟合，我们经常会利用集成学习中的Boosting思想，对回归树进行增强，得到的新模型就是提升树（Boosting Decision Tree），进一步，可以得到梯度提升树（Gradient Boosting Decision Tree，GBDT），再进一步可以升级到XGBoost。通过多棵回归树拟合残差，不断减小预测值与标签值的偏差，从而达到精准预测的目的，在后面我们会介绍这些高级算法。
3.过拟合与正则化
1）过拟合问题
决策树模型存在过拟合风险，通常情况下：
树的规模太小会导致模型效果不佳。
树的规模太大就会造成模型过拟合。
2）过拟合问题处理
对于决策树，我们通常有如下一些策略可以用于缓解过拟合：
（1）约束控制树的过度生长
限制树的深度：当达到设置好的最大深度时结束树的生长。
分类误差法：当树继续生长无法得到客观的分类误差减小，就停止生长。
叶子节点最小数据量限制：一个叶子节点的数据量过小，树停止生长。
（2）剪枝
约束树生长的缺点就是提前扼杀了其他可能性，过早地终止了树的生长。
我们也可以等待树生长完成以后再进行剪枝，即所谓的后剪枝，而后剪枝算法主要有以下几种：
Reduced-Error Pruning（REP，错误率降低剪枝）。
Pesimistic-Error Pruning（PEP，悲观错误剪枝）。
Cost-Complexity Pruning（CCP，代价复杂度剪枝）。
Error-Based Pruning（EBP，基于错误的剪枝）。
3）正则化
对于回归树而言，在剪枝过程中我们会添加正则化项衡量。如下所示，考虑剪枝后得到的子树｛Tα｝，其中 α 是正则化项的系数。当固定住 α 之后，最佳的 Tα 就是使得下列式子值最小的子树。
|T| 是回归树叶子节点的个数。
α 可以通过交叉验证去选择。
后记
这部分内容详细介绍了回归树的算法模型原理，在理解了决策树的基础上，还是比较容易理解，不过关于贪婪式递归和递归二分具体的差异没有解释的非常清楚，但是不影响我们的使用。这对于后面的机器学习真的很有帮助，再次感叹 ShowMeAI 论坛整理的真的非常棒，对数学能力不太高的我真的非常友善了！
https://www.showmeai.tech/tutorials/34?articleId=192
https://mp.weixin.qq.com/s/bHb0zPwYEDshGjYunxFbgA