一连串问题形成分类器
决策树让观测值依次通过特征测试。内部节点的测试选出子节点,叶节点则返回类别预测。数值测试如 ,会把特征空间分成区域。多层测试可描述单一测试无法表达的交互作用。
训练决策树,不只是把问题画出来。我们要决定叶的预测、候选划分的评分,以及何时停止或简化树。这些选择处理不同问题:划分可改善训练分数,却未必改善新观测的预测;贪心规则也可能错过有用的交互作用。
使用有限训练样本 ,标签为 。观测值有各自索引,因此允许重复特征向量,甚至允许它们有不同标签。本节特征都完整可见,数值为有限实数。每个考虑的划分,其训练子节点都非空;缺失值处理是另一项建模选择。
叶节点的最佳常数预测
命题 3.2.1
(多数预测使叶节点训练错误最少)
设非空叶节点有 个标签 1、 个标签 0 的训练观测。常数预测 1 会错 个,常数预测 0 会错 个。因此零一损失下,最少的错误数是 ,由预测多数类取得。平局时固定一个规则,例如两类数目相同就预测 0。
证明
(数出每个常数预测的错误)
常数预测恰好在另一类的观测上出错。预测 1 会在 个标签 0 的观测上出错,预测 0 会在 个标签 1 的观测上出错。二元标签只有这两个常数预测,所以最小值是 ,而多数类能够取得它。
这证明固定叶区域内的局部最优,不证明区域选得好,也不证明训练多数会是总体多数。经验比例 是有用摘要,却不自动是未来数据上已校准的概率。
熵度量经验标签的不确定性
定义 3.2.2
(二元熵与划分信息增益)
对 的节点,设 ,定义
以连续延拓约定 。纯节点熵为 0,两类平衡的节点熵为 1 比特。
候选测试把节点分成非空子节点,以 索引,大小为 、标签 1 比例为 。信息增益为
权重 不可省略。如果从本节点均匀选一个训练观测,它以该概率到达子节点 。这个和是得知测试结果后,平均剩余的标签熵。如果小子节点与大子节点权重相同,就在计算另一个量,甚至会改变胜出的划分。
命题 3.2.3
(信息增益不为负)
沿用定义中的记号,且每个子节点都非空,则
此外, 恰好当每个子节点的标签比例都与父节点相同,即对所有 有 。
证明
(二元熵的凹性)
节点中的每个观测恰好属于一个子节点,所以父比例是加权平均 。对 ,
由于 在 上连续,它在该区间上严格凹。权重 都为正,总和为 1,所以 Jensen 不等式给出 ,即 。等号恰好在所有 相同时成立,而共同值必须等于它们的加权平均 。又因子熵非负,有 。
证明透视
划分与严格凹性用在哪里
关键一步是把 写成各子节点比例的加权平均。这个等式成立,是因为子节点把节点划分:标签 1 的数目相加,各 的总和是 。若某观测被送到两个子节点,或不被送到任何子节点,权重总和便不再是 1,等式也就失效。
凹性只给出 。严格性加上正权重(来自非空子节点),才使等号成为关于数据的陈述:只有当划分没有改变任何子节点的标签比例,增益才为零。
这说的是已观测样本的分布,不声称总体标签依赖该特征,也不保证估计出的正增益会在新数据中持续。
小而纯的子节点可误导未加权分数
例题 3.2.4
(在相同八条观测上比较两个测试)
根节点有两个二元特征 :
| 观测 | 标签 | ||
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 |
| 7 | 0 | 1 | 0 |
| 8 | 0 | 1 | 0 |
根有两类各四条,熵为 1。测试 会隔离一条纯标签 1,另一子节点有七条,其中三个 1、四个 0。测试 则给出两个四条子节点,两类数目分别为 及 。
| 测试 | 正确加权子熵 | 信息增益 |
|---|---|---|
信息增益选 。其多数叶在八条中错两条。 划分错三条:大子节点预测 0,错分余下三个 1。如果根直接作常数叶,不论平局时选哪类都错四条。
如果错把两个子熵直接平均, 会得到 ,低于 的 。错误规则因此偏好 ,使一条观测与其余七条合计有相同影响。
熵与训练误分类是不同准则。对一般候选划分,较小熵不一定代表多数预测错误更少。例子同时报告两项分数,不表示两种目标可以互换。
数值划分必须尊重重复值
对数值特征,以 送左, 送右。按该特征排序节点观测,并把相同值分组。如果互异值为 ,就只有 种非平凡训练划分。每个满足
的阈值,都给出相同训练划分。取 是一种精确约定,也可以取中点;但对介于两值之间的新观测,两种选择的预测可能不同。必须存储实际阈值,预测时也使用相同不等号。
相同特征值不能由此测试分开。在排序后两条相同值之间放边界,只会产生任何阈值都无法重现的虚构划分。
扫描互异值分组时,保持两类标签的前缀计数。每次把整组从右移左,更新两边数目;只在两边都非空时计算加权熵。
BEST_THRESHOLD(observations):
sort by this feature; keep all equal values in one group
left0, left1 = 0, 0
right0, right1 = total counts of labels 0 and 1
bestGain = -INFINITY
bestThreshold = NONE
for each value group except the final group:
move the group's label counts from right to left
gain = parentEntropy - sizeWeightedChildEntropy
if gain > bestGain:
bestGain = gain
bestThreshold = this group's feature value
return the best threshold, or NONE if there is only one distinct value
命题 3.2.5
(阈值扫描对每个可行划分恰好检查一次)
设节点有 个观测,数值特征有 个互异值 。两边都非空的划分 恰有 种:对 ,左边由值为 的观测组成。扫描对每一种各评估一次,所以在精确得分下,它返回增益最大的划分,增益并列时返回阈值最小者。
证明
(阈值与值分组一一对应)
若 或 ,其中一边为空。若 且 ,左边恰好是前 个值分组,所以不同的 给出不同划分。扫描逐组移动,因此第 次移动后,计数就描述第 种划分,并由此计算增益。对全部 取最大值,就是对全部划分取最大值。只在严格改善时更新最佳值,会保留递增顺序中第一个最大者,亦即阈值最小者。移动分组时每个观测只被处理一次,所以排序之后,计数更新需 。
阈值按递增顺序扫描,而且只有严格改善才更新最佳值,因此此版本在同增益时选较小阈值。也可以另定固定平局规则。此叙述指精确数学分数;数值实现要规定精度与平局策略。本节点排序需 ,之后计数扫描需 。如果 个特征各自排序,单一节点的简单界是 。整棵树训练会在之后节点重复工作,所以这不自动是全部训练成本。深度 的树,预测时至多做 次常数时间测试。
概念视角几何
把决策树看成特征空间中的方盒
从几何上看,由 构成的决策树用平行于坐标轴的超平面切割特征空间。每片叶子是一个方盒,即若干区间(部分可无界)的乘积,树在每个方盒上预测同一个常数。对单个特征的扫描,就是在已出现的取值之间,搜索一个切割平面的 个不同位置。下面的 XOR 决策树有四片叶子,分别对应两个特征切出的四个格子。
例题 3.2.6
(含重复值的阈值扫描)
取数值 ,标签为 。节点有两个 1 和三个 0,熵为 。互异值有四个,所以有三种可行划分。值为 3 的两个观测必须留在一起。
| 阈值 | 左边标签 | 右边标签 | 加权子熵 | 增益 |
|---|---|---|---|---|
扫描存储增益最大的 。把两个值为 3 的观测分开,意味着同一个测试中值 3 同时出现在两边,任何阈值都做不到,所以该划分不在这三种之内。只需计算 个增益,而不是四个。
例题 3.2.7
(同一特征值上的标签冲突)
取观测 。根节点有两个 1 和一个 0,熵为 。唯一可行的划分是 对 。左子节点的标签为 ,熵为 1,右子节点是纯的,所以增益为 。
左子节点不能再分,因为它的两个观测特征值相同。按预测 0 的平局规则,该叶会把标签为 1 的观测判错,所以整棵树在三个观测中错一个。只使用 的任何树都不可能更好:它对两个 的观测给出相同预测,而它们的标签不同,所以至少有一个错。剩下的错误是数据的性质,不是训练过程的缺陷。
零即时增益也可能隐藏交互作用
反例模式
XOR 需要两层,但每个第一步增益都为零
取全部四个二元特征组合,标签如下:
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
根的两类平衡,按任一特征划分后,两个子节点也各自平衡,所以第一步信息增益为零。如果规则是最佳增益不为正就停止,就会留下训练错误率为 的根分类器。
但先测试 ,再于两个子节点测试 ,就得到四个纯叶及零错误。第一步没有改善即时熵分数,却让之后的划分能使用有用结构。一步贪心选择不是搜索全部小型树的全局方法。
允许零增益划分可帮助此例,但不会消除停止规则的需要。深度上限、最小子节点大小、没有可用测试或标签已纯,都可以是停止原因。如果相同特征向量的标签冲突,任何只用这些特征的确定性测试序列,都不能把那些观测分开。
训练改善不等于泛化证明
假设二元特征 与总体标签 是独立公平比特,训练行与未来观测都从此联合分布独立抽取。 时,样本以正概率碰巧每条都满足 ,且两个特征值都出现。按 划分会产生纯训练叶及零训练错误;但新观测中,预测 的规则仍以概率 错误,因为独立性给出 。
因此,即使训练增益达最大可能值,也就是未必等于 1 比特的父熵,仍不证明预测准确。应分清训练、验证及测试角色:用训练数据拟合,用验证数据选复杂度,保留未使用的测试集作最后评估。训练不纯度分数不能代替这些独立的观测。
简化已长成的树,一种方法是加入大小惩罚,比较候选子树。设
其中 是训练误分类比例, 是叶数。考虑把有 个叶的子树折叠为一个多数叶,仍使用原本到达此子树的相同观测;折叠错误数就是该区域的 。旧训练错误数为 ,折叠后为 。总训练样本数为 ,目标改变量是
错误数要除以整个训练样本大小 ,不是只除以子树样本数。其余树部分不变,在比较中抵消。如果这是所选剪枝目标,差值非正就折叠,等号时采用偏好较小树的平局规则。这精确比较两个候选,不声称任意局部剪枝顺序能找到全局最佳树,也不声称某个 保证低测试错误。可用验证数据协助选择复杂度。
常见错误
(把子树错误数除以子树样本数)
设 ,某个覆盖 40 个观测的子树有 个叶,,,。正确的改变量是 ,所以按偏好较小树的平局规则,该子树会被折叠。若错误地把错误数差除以 40,会得到 ,因而错误地保留子树。 的每一项都以整个训练样本为尺度。
叶子的常数与不纯度须一起替换,但加权减少量的结构不变。
通往推广的路径
类别更多或响应为数值时,哪些部分会改变?
叶子的常数与不纯度须一起替换,但加权减少量的结构不变。
有 个类别时,熵变为 ,叶子预测出现次数最多的类别。若响应为实数并采用平方误差,叶子上的最佳常数是其响应的平均值,对应的不纯度是它们的方差,而划分后方差的加权减少量同样非负,因为总方差可拆成子节点内部与子节点之间两部分。划分的论证不变;只需替换叶子规则和不纯度。
有解练习
快速检查
(1. 按观测数加权子熵)
平衡节点有十条观测。候选划分把一条标签 1 单独放入纯子节点,另一子节点有四个 1、五个 0。求信息增益。如果错用两个子熵的未加权平均,会报告什么增益?
解答 · 解答 1
正确剩余熵为 ,增益约 。未加权平均为 ,得到错误增益 。两者父熵都用 1;差别全来自给大小一的子节点不合理的一半权重。
快速检查
(2. 拒绝把相同特征值分开的划分)
排序数值为 ,标签为 。用 测试时,列出全部不同且两边非空的训练划分及增益。为什么排序第二条之后看似全纯的划分不可用?
解答 · 解答 2
可用 及 ,分别代表区间 与 。每种都有一个纯单元素子节点,及一个标签比例为 或 的三条子节点,增益同为 。阈值不能把一个 2 放左、另一个 2 放右。两行之间看似增益 1 的划分,只是排序假象,不是有效特征测试。
快速检查
(3. 求 XOR 样本的最小深度)
只允许测试个别二元特征。证明深度一的树不可能完全分类四条 XOR,并给出能做到的深度二树。严格正增益停止规则会怎样?
解答 · 解答 3
深度一只有根测试及常数子预测,只能测 或 。两种情况的每个子节点都各含一个标签 0、1,因此每个常数叶错一条,四条中共错两条。深度二可在根测 ,两个子节点再测 ,四叶标记 ,就完全正确,所以最小深度是二。正增益停止规则不会走第一个零增益划分,停在深度零,错误率为 。
快速检查
(4. 比较剪枝时不要改变分母)
训练共有 条。五叶子树错 12 条,折叠为一个多数叶则错 20 条。分别在 与 比较两候选,其余树部分不变。
解答 · 解答 4
折叠的目标改变为 。 时是 ,折叠降低目标; 时是 ,此比较应保留子树。两者都用相同整体样本分母 100。这只选出两个带惩罚训练候选中较好的一个,本身不证明哪个在新数据上错得较少。