从分类到划分
近邻根据查询点附近的标签预测,朴素贝叶斯(Bayes)则使用分解后的概率模型。分类树采取另一种思路:反复把特征空间切成与坐标轴平行的区域,再为每个区域指定一个标签。树以贪心方式生长:在每个节点,选择使该节点训练标签的不纯度下降最多的一次划分。
本节研究二元标签 和基尼(Gini)不纯度。我们先证明划分增益的精确公式,再给出每一步均确定的拟合规则,手算一棵完整的树,最后讨论训练集上的下降能说明什么、不能说明什么。
节点与基尼不纯度
定义 5.6.1
(节点、标签比例与基尼不纯度)
节点是包含 个元素的训练对 的有限多重集。若其中有 个标签为 ,其标签比例为 ,基尼不纯度为
这里的 是经验比例,只描述节点中这组有限的标签。它有一个具体的概率解释:从节点的经验标签分布中有放回地、独立地抽取 ,每次抽到 的概率都是 。两次标签不同恰好是先 后 或先 后 ,所以
有放回是关键。若 时不放回地抽取,概率为 ,一般与上式不同。
以下两种理解容易混淆:
常见错误
(把基尼不纯度当作训练误分类率)
节点预测多数标签时,误分类比例为 ,而不是 。当 时,;由对称性,对每个 都有 ,只有 时相等。例如 时, 而误分类率为 。
常见错误
(把叶节点比例当作经过校准的概率)
一个叶节点只有两个训练点,且标签均为 ,则 ;但这不意味着新点落入该叶时标签以概率 为 。校准是关于新数据上预测的性质,需要在留出数据上检验。
;它恰在纯节点 处为零,在 处达到最大值 。
划分与增益恒等式
定义 5.6.2
(划分与基尼增益)
一次划分把父节点分为两个非空子节点 ,其中 。记
基尼增益定义为父节点不纯度减去子节点按大小加权的不纯度:
统计标签 的个数得 ,除以 即得
定理 5.6.3
(基尼增益恒等式)
对任何分成两个非空子节点的划分,
因此 ,且 当且仅当 。
证明
(直接展开与全方差公式)
直接展开。 令 、。由 和 ,
因此
展开 ,并用 ,便有
条件方差。 从父节点均匀抽取一个训练点,记标签为 ,所在子节点为 。 是均值为 的伯努利(Bernoulli)变量,故 ;对每个子节点也有相应等式。全方差公式给出
于是 。后者以概率 取值 ,以概率 取值 ,其方差为 。由于两个子节点非空,,故等号条件成立。
证明透视
增益恒等式依靠什么
两种论证都只用到父节点与子节点之间的一条联系:计数恒等式 ,即父节点比例是子节点比例按大小加权的平均。其余都是对单一函数 的代数运算。
关键一步是 为二次函数。由于 是加权平均, 中的线性部分相互抵消,只剩二次部分 ,也就是两个子节点比例的加权方差。正是 的严格凹性,使这个差在 时必为正。
两个子节点非空这一条件用了两次:它使 有定义,也给出 ,这就是“仅当”方向的全部内容。若把 换成误分类率 ,论证便不成立:该函数虽然是凹函数,但在 两侧各自是线性的,所以只要 位于 的同一侧,差就是零。下面第一个反例正是这种情况。
公式表明:两个子节点中标签 的比例相差较大、且大小不过分失衡时,增益较大。这个量完全由有限训练样本计算,因而是经验不纯度的下降。
概念视角算法
Gini 划分就是最小二乘划分
把标签当作数值,并用每个子节点的均值去拟合该节点。子节点的平方误差就是 , 同理。因此加权子节点不纯度等于两均值拟合总平方误差的 倍;Gini 增益最大的划分,恰好是以平方误差为损失的回归树在 标签上会选择的划分。叶节点比例 就是这个最小二乘拟合值。
总体版本会把经验比例换成未知的条件概率,例如 ;也可以使用另一准则——总体条件熵。训练增益只是对这类量的估计,节点越小,估计可能越嘈杂。因此 并不保证测试误差下降。
一套确定的拟合规则
为使结果可复现,预先固定所有选择。特征均为数值型,编号 。节点深度是从根开始经过的划分次数,根的深度为 。
- 候选阈值。 对每个特征 ,将当前节点中的不同观测值从小到大排列,取相邻不同值的中点为候选阈值。阈值 将 送到 ,将 送到 。中点严格位于两个观测值之间,故两个子节点非空。
- 选择。 选取增益最大的正增益候选;若并列,先取特征编号最小者,再取阈值最小者。
- 停止。 节点纯、没有正增益候选,或者深度达到拟合前固定的上限 时,将其作为叶节点。
- 叶节点预测。 预测多数标签;若 ,预测 。
计算量。 在大小为 的节点中对每个特征排序,耗时 。排序后从左到右扫描,维护左侧标签 的累计个数,即可对每个阈值用 时间求值,总计 。同一深度的节点包含互不重叠的数据子集,因此逐节点重新排序每层至多花费 。实际总量还取决于节点大小和是否预排序等实现选择。类别型特征需要另外规定划分方法,此处不讨论。
外推。 查询点超出某特征的训练范围时,仍按阈值规则进入该特征最左或最右区域。这只是规则的结果,并不证明数据范围外的标签规律仍然成立。
例题 5.6.4
(特征之间的并列改变样本以外的预测)
取 中四点:、、、。根节点 、。
沿特征 从小到大,标签为 。阈值 对应 ,增益依次为 、,以及由对称性得到的 。沿特征 的顺序是 ,标签为 ,三个增益同样是 。
最大值 由 和 同时取得。并列规则取特征编号较小者,所以拟合出的树是 、,两个叶节点均为纯节点,训练误差为零。
被舍弃的划分给出相同的训练集划分 ,对应的树是 、,训练误差同样为零。但在查询点 ,选中的树预测 ,被舍弃的树预测 。训练标签无法在两者之间作出选择;并列规则本身是拟合模型的一部分。
例题 5.6.5
(重复的特征值留下不纯叶节点)
取 ,标签 。父节点 、。只有两个不同值,所以唯一候选是 。
左子节点包含 处的两个点,标签 ,故 、;右子节点是 处的单个点,故 。直接计算 ;用恒等式得 。增益为正,所以根节点划分。
左子节点的 只有一个不同值,没有候选阈值,于是成为 的叶节点,按平票规则预测 。训练误差为 。任何阈值树都无法做得更好,因为特征值相同而标签不同的两个点必然落入同一个叶节点。这是下文所证纯度结果的边界情形:那里要求特征值互不相同,而此处这一假设不成立。
完整手算一棵树
例题 5.6.6
(一维分类树的手算)
取 、标签 ,深度限制不构成约束。父节点 ,故 。
根节点。 候选阈值为 。下表每行都可用 核对。
| 左侧标签 | 子节点加权 | |||||
|---|---|---|---|---|---|---|
最大增益 在 和 处并列,规则选较小的 。左子节点 的标签均为 ,成为叶节点。
右子节点。 其点为 ,标签 ,所以 ,候选阈值为 。
- :左侧 为纯节点;右侧 的 ,加权后为 ,增益 。
- :左侧 的 ,加权后为 ;右侧 为纯节点。增益 。
- :左侧 的 ,加权后为 ;右侧 为纯节点。增益 。
因此选择 。右孙节点 标签均为 ;左孙节点 标签为 ,其唯一阈值 产生两个纯叶节点,增益为 。
拟合区域:
最深叶节点的深度为 ,因此任意 均重现这棵树。训练误差为零,但这不提供经过校准的概率: 和 附近的两个区域各自只依靠一个观测点。
反例与局限
反例模式
基尼不纯度下降,分类误差却不变
将大小为 的父节点分成各含 个点的两个子节点。左侧有一个标签 ,故 ;右侧有两个,故 。父节点 。两个子节点的 分别为 ,加权平均为 ,增益是 。
三个节点均预测 。父节点错分 个点,两个子节点合计错分 个点,训练误分类率仍为 。基尼不纯度是平滑的替代指标,即使预测标签没有改变,它也会奖励子节点比例的分离。
这个反例针对准则本身。下一个反例针对停止规则:只要没有单次划分具有正增益,规则就会停止。
反例模式
零增益停止会错过交互作用
考虑四个等权重点:、、、。无论按哪个特征在 处划分,两个子节点都有 ,增益为零。上述规则于是停在根节点;按照平票规则,根预测 ,训练误差为 。
但一棵深度为 的树先按第一个特征划分,再在两个子节点各按第二个特征划分,就能完全拟合四个点。失败来自贪心的正增益停止规则,并不意味着树无法表示这个模式。
训练纯度也可能通过记住样本的偶然细节得到。下面在明确的模型假设下说明这一点。
定理 5.6.7
(记忆不能创造信号)
设训练数据为 ,测试对为 。假设 是公平伯努利变量,且与整个元组 独立,其中 包含预测器的内部随机性。若 用 和 拟合,则
证明
(条件化论证)
固定 、 以及预测器的内部随机性后,预测 就是固定标签 。由于 公平且与所有被条件化的变量联合独立,。再对 和内部随机性取平均,结果仍为 。
本节的拟合规则确实能够记住样本,下面的结果说明这一点。
命题 5.6.8
(互不相同的特征值迫使叶节点全纯)
设某特征 在 个训练点上的取值两两不同,且深度上限满足 。则确定性拟合规则产生的树的叶节点全部为纯节点,因此训练误差为零。
证明
(隔离最小值所在的点)
设大小为 的节点不纯,含 个标签 ,。特征 上把 最小的点单独分出的候选划分有 。若该点标签为 ,则 ,;若标签为 ,则 ,。两种情况都有 ,由增益恒等式,该候选的增益为正;因此除非节点深度等于 ,它一定会被划分。
每次划分都产生两个非空子节点,所以由归纳法,深度为 的节点至多含 个点。不纯节点至少含两个点,故其深度至多为 ;深度上限从不会使不纯节点停止。任何划分的子节点在 上的取值仍两两不同,论证可以重复。沿每条路径节点大小严格递减,所以拟合必然终止,且每个叶节点都是纯的。纯叶节点预测自身的标签,因此没有训练点被错分。
即使训练标签也是独立公平抛硬币的结果,由记忆结果,这棵零训练误差树的独立测试误差仍为 。这些是假设,并不是对某个具体数据集的断言。
验证时的纪律
任何从数据中学习参数的预处理,都必须只在每个训练折内拟合,包括填补缺失值、缩放参数和阈值搜索。单个特征经过严格递增变换后,树能形成的训练集划分不变;填补缺失值却可能改变这些划分。
、最小叶节点大小或剪枝程度的选择属于模型选择,需要验证数据。所有选择固定前不能使用最终测试集。基于划分的特征重要性描述的是拟合树如何使用训练数据,本身不具有因果含义。
练习与解答
练习 5.6.9
(对上面的四个 XOR 点,分别计算按单个特征划分时根节点的增益,说明拟合规则为何停止,并给出零训练误差的深度 树。)
基础
解答(3)
- 1
计算按特征 的划分
取 , 的标签为 , 的标签为 。因此 ,。
- 2
应用停止规则
没有正增益候选,根成为预测 的叶节点。
依据: 特征 对称,其唯一划分的增益也为零。
- 3
给出零误差的树
先按 划分,再在两侧各按 划分,每个叶节点恰有一个点,均为纯节点。正增益规则无法看到零增益的第一步能为后续完美划分铺路。
练习 5.6.10
(大小为 的父节点分为各含 个点的子节点,。用两种方法计算 ,并比较训练误差。)
基础
解答(3)
- 1
直接计算
、、,所以 。
- 2
用恒等式计算
。
- 3
比较训练误差
三个节点均预测 ,父节点错分 个点,子节点合计错分 个,划分前后的误分类率均为 。
练习 5.6.11
(对 、,列出阈值 的计数并核对增益。然后交换所有标签,讨论变化。)
核心
解答(4)
- 1
列出计数
父节点 ;左侧 ;右侧 。
- 2
核对增益
,所以 。
- 3
交换标签
关键一步
各增益及所选划分顺序均不变。但平票叶节点的预测另当别论。
依据: ,且两个比例都换成补数时 不变。
- 4
检查平票叶节点
取 时,节点 为叶节点,标签 ,预测 ;交换后标签为 ,仍预测 。用原始标签解释,交换后的预测对应原来的类别 。因此固定的平票规则在重标记下并不对称。
练习 5.6.12
(数据集中每人有多行记录,随机按行划分使同一个人同时出现在训练集和验证集。解释问题并提出合适的流程。)
综合
解答(3)
- 1
诊断泄漏
深树可能隔离出个人特有的特征组合。同一个人的验证行可能落入用其训练行拟合的叶节点,因此验证分数可能反映对熟悉个体的记忆;若部署目标是新个体,估计可能过于乐观。
- 2
按组划分并在折内拟合
关键一步
应按人分组划分,使每个人的所有行都在同一个折内。每个训练折内部拟合缺失值填补、缩放和阈值搜索,再对留出的组求值;根据验证结果选择 或剪枝程度,最后才在由未见过的人组成的独立测试集上评估一次。
- 3
说明流程估计的对象
此流程对新人的表现只有在各人可视为来自同一总体的独立抽样等条件下才具有相应解释。这是数据收集方式的假设,划分本身不能证明它成立。