Amazon AS：Decision Tree 与 Random Forest，分裂、Bagging 和 OOB 如何解释？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 题目只列decision tree/random forest问句；本文训练合同为数值特征二分类CART与bootstrap森林，不推断原面试库实现。
• 分裂以加权Gini下降选择，叶子用类别频率；缺失值、类别特征、样本权重和概率汇总需单独定义，不能套一个默认到全部库。
• 用于时间或用户分组数据时，普通逐行bootstrap/OOB并不自动满足独立验证需求。

解题路线

1. 节点标签比例p_k，Gini=1−Σp_k²。候选切分把样本分为L/R，收益为G_parent−(|L|G_L+|R|G_R)/n。最大下降只优化当前节点，贪心不保证整棵树全局最优；回归常用平方误差，不能直接用类别Gini解释。
2. 数值特征按值排序，考虑相邻不同取值之间的阈值；累计类别计数可在线更新左右不纯度。特征值相同不能假装把相同值拆到两边。约束min_samples_leaf、max_depth并做剪枝/验证，纯叶子并不代表泛化好。
3. Bagging对训练样本有放回采样，每棵树拟合自己的样本；森林还在每次节点分裂随机抽候选特征，使树的误差较少相关。多个不稳定树平均可降方差，但不能保证无偏、不能消除共同泄漏或共同系统错误。
4. 回归若每棵预测误差同方差σ²且两两相关ρ，平均误差方差=σ²[ρ+(1−ρ)/M]。M增大只能消掉独立部分，相关部分形成下限。分类多数投票并不能机械套这个数值预测公式；减少候选特征也可能削弱单树，应同时看单树能力和相关性。
5. 一个n样本bootstrap中某行未出现概率(1−1/n)^n约e^−1。OOB对每行只汇总没训练过它的树，再与其标签比较。树太少时某行没有OOB票；重复实体、时间依赖或预处理全局泄漏仍可能使OOB乐观。
6. 特征重要性区分分裂不纯度下降和验证集permutation效果。高基数特征常更易找到下降，相关特征互相替代又会弱化单列打乱效果；不要把重要性当因果效应。可按业务成组置换并核时间切分。
7. 训练后记录树数、深度、节点数、叶子样本分布和校准表现；概率可平均叶子类别概率，或定义硬投票频率，这两者不完全一样，必须先讲实现合同。森林原论文参考：https://www.stat.berkeley.edu/users/breiman/randomforest2001.pdf。

手动走一遍

4行标签[0,0,1,1]，特征x=[1,2,3,4]。根Gini=0.5，阈值2.5得到两纯节点，加权Gini=0，收益0.5；阈值1.5得到1行纯与3行[0,1,1]，加权Gini=1/3，收益1/6。假设M=100、σ²=1、ρ=0.2，平均方差0.208；增加到1000树是0.2008，收益远小于把树相关性降低。数值是独立训练示例。

规模与取舍

平衡树每层扫描n行、候选f特征并按具体排序实现计成本；常见连续特征朴素实现约O(M·f·n·log²n)，重用排序/直方图可不同，最坏深度n会恶化。预测每行O(M·h)，空间O(所有节点)。不能只报O(log n)忽略全部树和退化深度。

易错点与追问

容易失分的边界

• 忽略左右节点样本权重。
• 混淆每树抽一次特征与每节点抽特征。
• 用OOB代替时间外测试。
• 把分裂重要性说成因果解释。
• 宣称加树必定解决过拟合或类别不均衡。

继续深挖

• 相关特征让permutation importance偏低怎么查？
• 森林如何输出概率并校准？
• bootstrap对稀少正例有什么风险？
• 深度不设限与min leaf有什么关系？