第 6 讲
决策树
从条件路径到区域划分与剪枝
果实分选中的监督信号
| 糖度 | 硬度 | 标签 |
|---|
| 8 | 0.70 | 不合格 |
| 13 | 0.40 | 合格 |
| 15 | 0.85 | 不合格 |
从样本中学习条件与分支。
教学构造数据；硬度指数取 $[0,1]$，标签及阈值仅用于算法说明。
从根节点到叶节点的预测路径
树路径对应的矩形区域
$$x_{\text{糖度}}>10$$ $$\land$$ $$x_{\text{硬度}}\leq0.65$$
每次划分只作用于当前节点的区域。
叶节点中的类别统计
类别混合程度与节点不纯度
$$H(p)=-\sum_kp_k\log_2p_k$$
信息熵（entropy）
$$G(p)=1-\sum_kp_k^2$$
基尼不纯度（Gini impurity）
信息增益的加权计算
$$\mathrm{Gain}=H(D)-\frac{|D_L|}{|D|}H(D_L)-\frac{|D_R|}{|D|}H(D_R)$$
Quinlan (1986). Induction of Decision Trees.
连续阈值与划分质量
12 个固定合成样本；扫描相邻糖度的中点，实时计算子节点比例与加权不纯度。
连续特征的候选划分点
取不同数值
→
按大小排序
→
相邻数值中点
→
计算划分质量
节点划分的贪心搜索
$$(j^*,t^*)=\arg\max_{j,t}\ \mathrm{Gain}(D;x_j\leq t)$$
局部选择降低搜索成本；整棵树通常不保证全局最优。
递归生长与停止条件
标签已纯
当前节点只含一类。
无有效划分
特征无法继续区分。
达到复杂度限制
深度或叶样本量约束。
停止时，以当前节点的类别统计生成叶节点。
树深度与局部细分
复杂度增加时，关注验证误差与叶节点样本量。
深度、决策区域与验证误差
合成分选样本，含随机标签翻转；区域图显示训练点，误差曲线由实际树预测计算。
基于验证集的后剪枝
$$\text{若}\quad\mathrm{Err}_{\mathrm{val}}(\text{叶})\leq\mathrm{Err}_{\mathrm{val}}(\text{子树}),\quad\text{接受剪枝}$$
后剪枝前后的实际预测
固定深度上限 7；两图显示同一组训练点；验证样本仅用于决定剪枝。
回归树中的分段常数预测
$$\hat y_{\text{叶}}=\frac1{|D_{\text{叶}}|}\sum_{i\in D_{\text{叶}}}y_i$$
按平方误差下降选择划分。
分类与回归树（Classification and Regression Trees, CART）。Breiman 等，1984
树模型的解释范围与限制
| 限制 | 含义 |
|---|
| 训练样本扰动 | 树结构可能改变 |
| 深树与小叶 | 解释与估计不稳定 |
| 单特征划分 | 斜边界需要多次切分 |
| 路径相关性 | 不能直接推出因果 |
树学习的计算链与参考文献
第 6 讲结束
← → 翻页 · o 总览 · s 演讲者视图 ·
f 全屏 · 网址后加 ?print-pdf 可导出 PDF
机器学习 · 研究生 第 6 讲 决策树
https://kaizhao.net/teaching/shu-ml-grad