决策树
决策树每次问一个阈值问题：“这个坐标是否 ≤ 某个值？”训练扫描候选切分，贪心选择信息增益最大的项，再对子集递归。预测沿根到叶的路径回答问题，返回叶子的多数类。
本课只允许沿坐标轴切分，所以单个叶子对应轴对齐矩形；同类可占多个矩形。深度预算决定最多问几次。这两项约束决定了树能表达什么、会在哪些点上出错。
工作原理
含 a 个 A 和 b 个 B 的区域，其熵为：
H = −p_A log₂ p_A − p_B log₂ p_B
纯区域熵为 0，等量两类为 1 bit，零比例项按极限计为 0。切分的信息增益为父节点熵减去按样本数量加权的子节点熵。
对每个特征，排序不同坐标值，取相邻值中点作候选。只要阈值在同一对相邻值之间，训练点的分组就相同，因此一个中点足以代表该间隙。动画用区域下侧和左侧的柱形展示每个候选的增益。
选出最好切分后，两个子节点各看自己的样本。纯节点直接返回唯一类别；达到 depth==max_depth 时返回多数类。一般实现还须处理没有可用切分的混合节点，例如同坐标冲突标签，不能无限递归。本课数据没有这种冲突。
约定如下：≤ 走左子树；增益平手时先保留较低特征编号，再保留较低阈值，因为仅在严格更优时更新；多数票平手选 A。切线只穿过当前节点区域，不延伸到兄弟节点，矩形地图由这些条件推导而来。
逐步演示
默认 11 点，A 6、B 5，max_depth=2，查询 (3,3)。左边四个 A，右下四个 B，右上两个 A 和一个人为噪声 B (3,4)。
- 根节点 6:5，熵约
0.99bit。 - 扫描 x₁ 的六个竖直候选。
x₁≤−0.5最好：0.99−(4/11)×0−(7/11)×0.86≈0.44bit，左侧纯 A。 - 扫描 x₂ 的七个候选，最好是
x₂≤−2.5，增益约0.24，低于 x₁ 的结果。 - 提交
x₁≤−0.5，平面分成两个矩形，树产生根问题。 - 左侧四 A，熵 0，深度 1 就结束，叶子返回 A。
- 右侧 A 2、B 5，熵约
0.86。本节点 x₁ 最佳增益约0.08，x₂≤0.5增益约0.47，故选后者。横线只穿过右侧矩形。 - 右下四 B，纯叶，返回 B。
- 右上 A 2、B 1，仍混合，但深度已达 2，多数选 A。噪声点
(3,4)被判 A。共三个叶子，错误1/11。 - 查询
(3,3)先因3>−0.5走右，再因3>0.5进入右上叶，按 2:1 返回 A。这是该叶的训练计数，不是经过校准的 67% 概率。
深度与过拟合
把最大深度改为 3，右上区域可选 x₂≤3.5，增益约 0.92。噪声 B 独占一个细小叶子，训练错误降为零，但整片区域只有一个点支持。高增益和纯叶不等于可靠泛化。
深度 1 时右半区合成多数 B，牺牲两个真实 A，错 2 点；深度 2 错 1 点；深度 3 给噪声单独区域，错 0 点。延伸同一贪心树时，训练误差不增加，但不保证每加一层都下降。应通过验证选择深度，再用独立测试评价。剪枝、最小叶样本数、随机森林或梯度提升等可控制单树的方差，但并非无条件解决问题。
矩形与斜线的取舍
“两座岛”沿用线性分类器的点位，并把三类合并为两类。同类在两角，另一类在中间，线性凸区域不能同时避开走廊。树先问 x₁≤−1.5 隔出一岛，再问 x₂≤1.5 隔出另一岛，零错误。同类矩形的并集不要求凸。根节点两轴增益都为 0.31，按规则选较低轴。
“对角线”预设反过来：八点可由 x₂=x₁ 一条斜线分开，但树不能问斜向问题。贪心选 x₁≤−3、再 x₂≤−1、再 x₁≤1，形成阶梯；深度 3 后仍有一点错误。显示的虚线是线性模型的比较边界。数据是否符合允许的问题形状，会影响所需深度和叶子数。
计算成本
朴素候选扫描对每个阈值重新计数，单节点约 O(d n²)，另需排序；排序加累计计数等方法可改善。预测只走一条路径，为 O(depth)，不会重新扫描训练点。本课两个特征、十一点让所有候选都可核查。
边界情况
- 纯节点即使还有深度也停止；默认左块在深度 1 结束。
- 混合节点达到上限就多数投票，少数点被错分。
- 某轴只有一个值就没有中点候选。所有轴都无法分时，一般实现应返回多数叶；不能假设节点必然纯。
- 增益平手按特征编号、阈值排序决定；两岛根节点可见此情形。
- 多数平手选 A，是公开的约定，不是学出来的事实。
常见错误
- 以为树保存了矩形地图。它保存问题，地图由路径约束产生，所以切线不越过兄弟区域。
- 因为增益高就信任单点叶。样本支持数和验证表现也必须看。
- 把训练零错误当成功。对可由允许切分区分且标签一致的有限数据，足够深的树可记忆；不等于学到了泛化规则。
- 认为贪心能找到最小树。它锁定局部最佳切分，未做全局搜索。最优树构造的相关问题是 NP-hard，局部扫描是折中。
- 把叶子“2/3 是 A”读成校准概率。它只是一个小区域的训练频次。
简化范围
本课是使用熵和信息增益的二叉阈值树，接近 ID3 的选择思想，但采用连续特征中点切分。两个特征、深度限制、十一整数点方便手算。其他实现可用 Gini 不纯度，两种指标可能给不同排序，不能说完全相同。
d 维时仍一次比较一个坐标，单叶区域变成轴对齐超矩形。实际树还可能包含回归目标、缺失值策略、代价复杂度剪枝、最小叶样本限制，支持范围依实现而定。集成树用不同方式组合多棵树，处理单树的不稳定性。训练与评价流程可参见训练循环。