决策树依次询问关于特征的是非问题来作预测,每条问题把一个特征与一个阈值比较。它是既非线性、又易于阅读、求值成本又低的模型的标准例子,也是集成方法的基本单元。这里的树属 CART 类型:二叉、轴向、贪心生长。本节与随机梯度及线性分类器两节互补,那两节中拟合出的函数来自连续优化;树则由组合式搜索构造,主要风险并非优化器不佳,而是过拟合,并以剪枝加以控制。
树、不纯度与分裂准则
定义 31.1.1
(轴向二叉树及其预测)
树把特征空间划分为若干区域,每片叶子对应一个。内部节点检验规则 (特征下标 、阈值 ):满足的观测值去左子节点,其余去右子节点。若叶子含训练观测值下标集 ,则分类时预测 中的多数类(并规定固定的平局规则),回归时预测均值 。
定义 31.1.2
(节点不纯度与分裂增益)
对含 个训练点、各类比例为 的节点,基尼(Gini)不纯度为 ,熵为 ()。一次分裂把 个点送往左边、 个送往右边,两边都非空,其增益为
对两类且第一类比例为 ,。树的生长过程在每个节点选取增益最大的特征与阈值,只考虑排序后相邻且不同的特征值之间的阈值,并递归下去,直至停止规则生效,例如节点纯净或节点大小达到下限。
概念视角组合
把基尼不纯度看成分歧的概率
独立地从节点中有放回地抽两点,它们属于同一类的概率是 ,所以 就是两点类别不同的概率。若 个点的类别计数为 ,则 个有序对中有 对类别相同、 对不同,故 。
定理 31.1.3
(分裂永不增加不纯度)
不纯度函数 在概率单纯形上是凹函数。因此对每次分裂都有 ,且等号成立当且仅当左右两边的类比例都等于父节点的类比例。
证明
(基尼不纯度的凹性)
函数 是线性函数平方之和,故为凸函数,所以 是凹函数。父节点的比例向量是两个子节点向量的凸组合 。由 Jensen 不等式,,即 。平方函数严格凸,所以等号恰在 时成立,这时两者都等于 。
等号的情形很重要:一次分裂的增益可以为零,而更深的分裂却有用。
反例模式
增益为零就停止,会错过异或模式
设想一个断言:若根节点上没有任何分裂有正增益,继续分裂就不会有用。取四个点 ,标签依次为 。根节点的类比例为 ,所以 。分裂 把标签 送往左边、 送往右边,两个子节点的 都是 ,所以 ;分裂 得到相同的值。因此“没有正增益就停止”的规则只会输出单个叶子,训练误差为 。但先按 分裂,再在两个子节点各按 分裂,得到四片纯叶子,训练误差为 。某一层的增益为零,只说明没有任何单个问题能立刻带来好处。修正的办法是改用其他停止准则,例如节点纯或节点大小下限,再用剪枝控制树的大小。
回归树
对数值响应,节点的不纯度取为其关于节点均值的平方误差和 。
定理 31.1.4
(均值最优,且分裂增益有闭式)
对任意实数 ,,所以使平方误差最小的叶值是均值。若一次分裂把 分为非空的 与 ,大小为 ,,则
证明
(分裂的方差分解)
把 写成 ,并注意 ,即得第一个恒等式。把它分别应用于 (取 )与 (取 )并相加:。因为 ,有 与 。最后两项之和为 。
证明透视
为什么两部分都以父节点均值重新对齐
证明中唯一不显然的一步,是把单集恒等式用于 与 时,两次都取同一个中心 ,而不是直接比较 与 。恒等式对每个 都成立,它的交叉项 会消失,因为一组数对自身均值的离差之和为零。共同的中心把 拆成 加两项组间平方和,所以增益恰是组间平方和。关系 是父节点均值唯一被当作加权平均来用的地方;它使两个偏差都是同一个差 的倍数,因子 即由此而来。定义 、 的均值需要它们非空;若其中一部分为空,增益为 ,与 一致。证明没有用到分裂是轴向的,也没有用到它如何选出,所以对 的每一种二分都成立。
因子 表明,在均值差相同时,平衡的分裂比只剥离一个点的分裂获得更大的增益。
代价复杂度剪枝
完全生长的树可以精确拟合训练数据,却泛化不佳。代价复杂度剪枝对叶子数目施加惩罚。设树 的叶集为 ,训练误差为 (误分类比例或均方误差),每片叶子的惩罚为 ,定义
对内部节点 ,以 表示把其下子树 合并为单个叶子后的误差,以 表示其叶子数目。
定理 31.1.5
(合并开始有利的阈值)
对 的子树 ,把它合并为一片叶子会严格降低 ,当且仅当 ,其中
证明只需一行:合并使 改变 ,它为负恰当 。最弱连接剪枝反复合并 最小的节点,每次合并后重新计算 ,得到一列嵌套的树。 的取值,亦即这列树中选哪一棵,应该用留出数据或交叉验证来决定,而不是用训练误差。
例题
例题 31.1.6
(一维样本上的基尼分裂)
取 ,标签为 。父节点有三个 ,所以 。候选阈值为 。阈值 给出由四个 组成的纯净左子节点,以及右子节点 ,其 ,。增益为 。阈值 给出六个点中有一个 的左子节点,,以及纯净的右子节点,所以 。其余阈值更低: 分别为 。所以根节点在 处分裂。
误分类个数不能区分最好的两个候选:两者都恰留下一个错误。基尼增益偏好 的分裂,因为它的纯净子节点较大(四个点而非两个),使加权不纯度更少。右子节点 在 上,,最佳分裂在 ,分为 与 ,增益为 ;阈值 与 各自只得 。
例题 31.1.7
(一次回归分裂与一个剪枝序列)
取 ,。总均值为 ,。在 与 之间分裂,得 与 ,均值分别为 与 ,各自 。增益为 ,而恒等式给出 。其他切分点的增益为 。
剪枝方面,设一棵含 个训练点的树,根下有两棵子树: 有 片叶子、 个错误,合并成一片叶子则有 个错误; 有 片叶子、 个错误,合并则有 个错误。若仅合并根得 个错误,则 ,,。最小的是 ,所以先合并 。此时树有 片叶子,误差为 ,故 ,根成为下一个最弱连接。合并根后只剩一片叶子,所以序列为:完整的树、合并了 的树,以及单个叶子。
例题 31.1.8
(平局、零增益阈值与纯节点)
取 ,标签为 。根节点 ,。阈值 给出纯的左子节点 ,以及右子节点 ,其 ,所以 。由对称,阈值 也得 。阈值 给出 与 ,各自 ,所以 :两边的类比例都等于父节点,正是定理的等号情形。最好的两个阈值平局,需要固定的平局规则;取较小的阈值,根节点便在 处分裂。
右子节点 的标签为 ,。阈值 给出 与 ,增益 ;阈值 给出 与 ,两边都纯,增益为 。所以在 处分裂,三片叶子的预测为: 时 , 时 , 时 ,训练误差为 。每片叶子都纯,;纯节点的任何分裂都有 ,又 ,所以该节点保持为叶子。
常见错误与细节
常见错误
(贪心增益、训练误差与树序列很容易被误解)
训练误差为零的树不一定好。增益是贪心的:增益为零的分裂仍可能需要,而最佳的第一次分裂也未必属于最佳的树。以最小化训练误差来选 ,永远得到完整的树,因为最大的树 最小;选择必须使用独立数据。分裂阈值必须落在不同特征值之间,否则分裂可能把相等的输入分开。最后,树是不稳定的:数据的小改动可以改变根节点的分裂,从而改变整棵树。
常见错误
(子节点不纯度必须按大小加权)
把两个子节点的不纯度不加权地取平均,会高估只剥离少数点的分裂。设父节点两类各有五个点,把一个第一类的点送往左边,其余 送往右边。左边 ,右边 。未加权平均为 ,会让人以为增益约为 。正确的加权增益是 。
练习
快速检查
(某节点的类别计数为 。求其基尼不纯度。)
把各类比例平方,再用一减去总和。
解答 · 答案
各类比例为 ,所以 。
快速检查
(某节点两类各有 个点。一次分裂把 送往左边、 送往右边。计算增益。再计算异或样本的根节点在单一特征上分裂的增益。)
每个子节点的不纯度要乘以它占全部点的比例。
解答 · 答案
父节点 。每个子节点 或 ,所以 ,加权子节点不纯度为 。增益为 。对含四个点、两类各两个的异或样本,父节点 ;按任一特征分裂,得两个子节点,各含每类一个点,,所以增益为 。
快速检查
(设按 排序后 。求父节点的 SSE、三种分裂各自的增益,以及最佳分裂。并以闭式核对其中一个增益。)
各部分的 SSE 要对它自己的均值计算。
解答 · 答案
均值为 ,父节点 SSE 为 。在第一个点之后分裂,得 与 ,SSE 为 与 ,增益为 。在第二个点之后, 与 的 SSE 各为 ,增益为 。在第三个点之后, 的 SSE 为 , 为 ,增益为 。最佳分裂在第二个点之后,增益为 。闭式核对:。
快速检查
(节点 有 ,其子树有 片叶子,。求 ,并说明在 与 时该节点是否被合并。)
比较 与 。
解答 · 答案
。 时保留子树; 时合并。