面试必备：一文讲透树模型（b树面试题）

面试必备：一文讲透树模型（b树面试题）

一、树模型的概括

决策树呈树形结构，更通俗来讲，树模型的数学描述就是**“分段函数”**。如下一个简单判别西瓜质量的决策树模型示例（注：以下西瓜示例，数据随机杜撰的，请忽略这么小的西瓜瓜~）：

学习这样树模型的过程，简单来说就是从有监督的数据经验中学习一个较优的树模型的结构：包含了依次地选择特征、确定特征阈值做划分的内部节点及最终输出叶子节点的数值或类别结果。

二、树模型的要素

从上述例子，我们可以将树模型的学习可以归到经典机器学习的4个要素：

2.0 已知(标签)的数据2.1 树模型的结构（分段函数结构：特征划分+决策结果）2.2 学习目标2.3 优化算法

树模型通过结合这几个要素，更快更好地划分特征空间，得出比较准确的决策。如下对这几个要素具体解析。

2.1 树模型的结构

2.1.1学习树结构的过程

决策树剪枝的目的是极小化经验损失+结构损失，基本策略有”预剪枝“和”后剪枝“两种策略：①预剪枝：是在决策树生成过程中，限制划分的最大深度、叶子节点数和最小样本数目等，以减少不必要的模型复杂度；②后剪枝：是先从训练集生成一棵完整的决策树，然后用用验证集自底向上地对非叶结点进行考察，若将该节点对应的子树替换为叶子结点（剪枝）能带来决策树的泛化性能提升（即目标函数损失更小，常用目标函数如：loss = 模型经验损失bias+ 模型结构损失α|T|， T为节点数目, α为系数），则将该子树替换为叶子结点。

2.1.2 复杂树结构的进阶

树模型的集成学习

实践中可以发现，浅层的树很容易欠拟合，而通过加深树的深度，虽然可以提高训练集的准确度，却很容易过拟合。

这个角度来看，单个树模型是比较弱的，且很容易根据特征选择、深度等超参数调节各树模型的多样性。正因为这些特点，决策树很适合通过结合多个的树模型做集成学习进一步提升模型效果。

集成学习是结合一些的基学习器共同学习，来改进其泛化能力和鲁棒性的方法，主流的有两种集成思想：

线性决策树

2.2 学习目标（目标函数）

上文有提到，树模型的学习目标就是让各组的划分的准确率（纯度）都比较高，减小划分误差损失（此处忽略了结构损失T）。能达成划分前后损失差异效果类似的指标有很多：信息熵、基尼系数、MSE损失函数等等 都可以评估划分前后的纯度的增益 ，其实都是对分类误差的一种衡量，不同指标也对应这不同类型的决策树方法。

使用信息增益做特征划分的缺点是：信息增益偏向取值较多的特征。当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。

C4.5决策树的指标：信息增益比

相应的，使用信息增益比缺点是：信息增益比偏向取值较少的特征。综上两种指标，可以在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

Cart决策树的指标：基尼系数（分类树） 或 平方误差损失（回归）

基尼系数表征的也是事件的不确定性（不纯度），也都可以看做是对分类误差率的衡量。

我们将熵定义式中的“-log(pi)”替换为 1-pi 也就是基尼系数，因为-log(pi)的泰勒近似展开第一项就是1-pi。基尼系数简单来看就是熵的“平替版”，在衡量分类误差的同时，也简化了大量计算。

（注：由于分类误差为分段函数=1-max(p, 1-p) ，不便于微分计算，实际中也比较少直接用）

2.3 优化算法

确认学习目标，而依据这个指标去学习具体树结构的方法（优化算法），基本上有几种思路：

暴力枚举：尝试所有可能的特征划分及组合，以找到目标函数最优的树结构。但在现实任务中这基本是不可能的。自上而下的贪心算法：每一步（节点）都选择现在最优（信息增益、gini、平方误差损失）的特征划分，最终生成一颗决策树，这也是决策树普遍的启发式方法，代表有：cart树、ID3、C4.5树等等随机优化：随机选择特征及划分方式，通常这种方法单树的生长较快且复杂度较高。模型的随机性、偏差比较大（模型的方差相对较小，不容易过拟合，但是bias较大），所以常用集成bagging的思路进一步优化收敛。代表有：Extremely randomized trees（极端随机树）、孤立森林等等.

总结

​

技术交流

欢迎转载、收藏、有所收获点赞支持一下！

目前开通了技术交流群，群友已超过2000人，添加时最好的备注方式为：来源+兴趣方向，方便找到志同道合的朋友

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。