📑 本页目录(点开跳转)
决策树 · 怎么选第一刀
怎样从旧订单里学出「这单会超时吗」的规则?
回归课预测过一个数值,也在选读里用分布描述过预测的不确定性。现在换一个目标:订单送达前,只预测「超时」或「准时」。本章用到占比、平均值和平方。
读完你能顺着一棵树做预测,手算并验证两种切法的分数,也能算出回归树叶子里的预测值。
用一条订单走完一棵树
假设 20 笔历史订单中,10 笔超时、10 笔准时。给所有订单同一个预测,在这批数据里只能答对一半。我们有下单时就知道的两个特征:配送距离和是否高峰。先用距离把订单分组,看看同组能不能用一个预测。
决策树(Decision Tree)把这种判断写成一连串问题。起点叫根节点,答案对应的路线叫分支,停止提问并给出预测的地方叫叶子。图里每片叶子把订单数最多的类别作为预测。
一层可以问距离,下一层可以只在其中一个分支问高峰。不同分支能用不同的规则处理。现在你会沿树做预测了,接着看图里的第一问是怎么选出来的。
手算哪一个问题分得更好
这批演示数据的距离只有 2 和 6 公里,取中间的 4 公里就能把两种距离分开。另一个候选是「是否高峰」。下面的条形显示两个问题各自把同一批订单分成了什么样。
按距离分
≤ 4 公里 · 1 超时 / 9 准时
> 4 公里 · 9 超时 / 1 准时
按高峰分
非高峰 · 4 超时 / 6 准时
高峰 · 6 超时 / 4 准时
基尼不纯度(Gini Impurity)衡量一组的标签有多混杂。从同一个节点随机抽一单,放回后再抽一单。抽到不同类别的概率就是基尼。
先算反面的情况:两次都是第 k 类的概率,是该类占比 pk 乘自己。把每一类的这个概率加起来,就得到两次同类的概率。用 1 减去它,就是两次异类的概率。
D 是当前非空节点里的样本,K 是类别数,k 从第 1 类数到第 K 类。二分类时只加超时、准时两项。结果没有单位,二分类的取值在 0 到 0.5 之间。全为同类时是 0,超时和准时各占一半时是 0.5。
切前的两类比例都是 10 ÷ 20 = 0.5,基尼是 1 − 0.5² − 0.5² = 0.50。
切后,每单都只去一个分支。比如 20 单里有 5 单进入左组,那么随机抽一单,抽中左组的机会是 5 ÷ 20。按这个机会给各组的基尼加权,就能衡量随机一单所在分支有多混杂。GL、GR 分别是左右组的基尼,wL、wR 是各组人数除以切分前的总人数。
- 按距离。一组的占比是 0.1 和 0.9,另一组刚好反过来。两组的基尼都是 1 − 0.1² − 0.9² = 0.18。
加权后是 (10 ÷ 20) × 0.18 + (10 ÷ 20) × 0.18 = 0.18。 - 按高峰。两组的比例分别是 0.4 / 0.6 和 0.6 / 0.4。两组的基尼都是 1 − 0.4² − 0.6² = 0.48。
加权后是 (10 ÷ 20) × 0.48 + (10 ÷ 20) × 0.48 = 0.48。
从同样的 0.50 出发,距离让基尼下降 0.32,高峰让它下降 0.02,所以这一层先问距离。两组恰好一样大才各占一半。练习里会遇到一大一小的两组。
这个分数描述训练样本。高基数特征(High-cardinality Feature)指取值种类很多的特征,例如每单不同的订单 ID。能按 ID 拆出许多小组的算法,容易把已有标签记下来。二叉树每次只分两组,但取值多的数值特征往往有更多候选阈值,仍可能碰巧找到加权基尼很低的切法。
进阶扩展 · ID3 与 C4.5 怎样给同一刀打分
用熵度量标签的混杂
基尼是一种计分方法。熵(Entropy)把每一类的意外程度按它出现的概率平均。概率每减半一次,意外程度多 1 bit,例如概率 1、1/2、1/4 分别对应 0、1、2 bit。这对应以 2 为底的对数取负号。
对节点 D 的每个类别 k,用该类占比 pk 给意外程度加权。没有出现的类别贡献记为 0,这相当于约定 0 log₂ 0 = 0。
$H(D)=-\sum_k p_k\log_2p_k$
原始 ID3 选择信息增益(Information Gain)最大的特征。a 是所问的特征,v 遍历它拆出的各支,Dv 是第 v 支里的订单。竖线表示样本数。用父节点的熵减去各支熵按人数加权后的结果。
切前超时和准时各占一半,熵是 −0.5 log₂ 0.5 − 0.5 log₂ 0.5 = 1 bit。把 2 公里和 6 公里当成两个取值来分组,一边的标签占比是 0.1 和 0.9,熵约为 −0.1 × (−3.322) − 0.9 × (−0.152) ≈ 0.469 bit。另一边占比对调,熵相同。增益是 1 − (0.5 × 0.469 + 0.5 × 0.469) ≈ 0.531 bit。
用增益率考虑分组方式
若按订单 ID 分成 20 支,每支一单,各支标签熵是 0,信息增益是 1 bit。增益率(Gain Ratio)用信息增益除以分支熵 IV。分支熵也用上面的熵公式,把标签占比换成每支人数占比 qv,加总范围也换成所有分支。
$IV(a)=-\sum_v q_v\log_2q_v$
距离分为等大的两支,分支熵是 −2 × 0.5 × log₂ 0.5 = 1 bit,增益率约为 0.531 ÷ 1 = 0.531。订单 ID 分成等大的 20 支,分支熵是 −20 × 0.05 × log₂ 0.05 ≈ 4.322 bit,增益率约为 1 ÷ 4.322 = 0.231。这里只比较两种切法的分数。
只有一支时,IV = 0,比值未定义。分支熵很小时比值也可能偏大。C4.5 比较增益率之前会先筛选信息增益足够的候选,仍需要控制树的复杂度。Quinlan 原论文第 7 节 · 标签熵、交叉熵与 KL 散度 · 从课程开头读
按订单 ID 直接拆多组需要算法支持类别的多路切分。下文的 CART 每次二分。真遇到取值很多的类别时,可参考特征工程中的类别特征处理。
我们已经用训练样本选出了距离。接着跑一次同样的计算,再看分数还能下降时,树是否应该继续长。
跑一遍切分,判断何时停
下方 Python 代码固定使用刚才的 20 单,无需第三方包。每行是「距离、高峰标记、超时数、准时数」。0 表示非高峰,1 表示高峰;把标记和 0.5 比较,就能分开两组。
counts 算分支人数,gini 算一支的混杂程度,score 按人数合并。最后分别试两问,按分数从小到大打印。这段代码只接收例子里保证两边都非空的两个问题。真实的树会跳过让某一边为空的阈值。
Python · 比较距离和高峰
# 距离、高峰、超时数、准时数
orders = [
(2, 0, 0, 5), (2, 1, 1, 4),
(6, 0, 4, 1), (6, 1, 5, 0),
]
def counts(rows):
late = sum(row[2] for row in rows)
on_time = sum(row[3] for row in rows)
return late, on_time
def gini(late, on_time):
n = late + on_time
return 1 - (late / n)**2 - (on_time / n)**2
def score(column, threshold):
left, right = [], []
for row in orders:
if row[column] <= threshold:
left.append(row)
else:
right.append(row)
branches = [counts(left), counts(right)]
total = sum(late + ok for late, ok in branches)
return sum(
(late + ok) / total * gini(late, ok)
for late, ok in branches
)
scores = [
(score(0, 4), "配送距离"),
(score(1, 0.5), "是否高峰"),
]
for value, name in sorted(scores):
print(f"{name}: {value:.2f}")
运行结果
配送距离: 0.18 是否高峰: 0.48
和手算一样,距离排在前面。用这两个分支的多数类别,树就能按前面的图做预测。
要是继续生长,距离右支里的 10 单还可以按高峰分成两组,每组 5 单。max_depth=1 限制一条路最多问一层。即使放宽深度,min_samples_leaf=6 也会挡住这一刀,因为分出的两片叶子都只有 5 单。
右支分出的两组分别是 4 单超时、1 单准时,以及 5 单都超时。加权基尼从 0.18 降到 0.5 × (1 − 0.8² − 0.2²) + 0.5 × 0 = 0.16。两组仍预测超时,原来判错的那单依旧判错。这一刀的基尼更低,训练准确率没有变化。
树切得太细,可能贴合训练数据里的偶然差异,到了新订单上反而判得更差。这叫过拟合(Overfitting)。深度和叶子大小由训练前设定,比较这些设置时用验证数据。最后留一份测试数据评估选定的方案。
第 1 章的历史实验中,不限深度的单树训练准确率是 100%,留出的测试集是 91.8%。这是一次切分的观察。评估课的交叉验证会讲怎样比较不同深度。
进阶扩展 · 实际建树有哪些设置
min_samples_split 限制父节点至少有多少样本才允许尝试分裂,max_leaf_nodes 限制整棵树的叶子数。还可以用剪枝把已经长出的部分分支删掉。
scikit-learn 使用优化过的二叉 CART,分类默认用 gini,回归默认用 squared_error。类别特征需要先编码。scikit-learn 决策树文档
对本例的精确阈值切分,公里换成米会保留距离的顺序,4 公里那刀等价于 4000 米那刀。因此比较这种切分无需先标准化距离。
用基尼挑第一问,用深度和样本数限制后续提问。下一步仍用同样的分组办法,看看叶子怎样给出一个数值。
算出回归树叶子的预测值
分类与回归树(Classification and Regression Trees,CART)每次提出一个问题,把当前样本分成两支。上面是分类情形。假如现在要估计配送耗时,每片叶子要给这组订单报一个共同的分钟数,切分的好坏就要用预测误差来比较。
用均方误差(Mean Squared Error,MSE)比较预测。每单的实际耗时是 yi,模型给它的预测是 ŷi,i 遍历参与评分的 n 笔订单。每单先相减再平方,避免低估与高估互相抵消,然后除以总订单数。这里误差的单位是分钟的平方。
当一片叶子用同一个预测时,取这组的均值会让平方误差最小。原因是实际值相对均值的偏差之和为 0。把共同预测从均值挪开时,展开各单的误差平方,交叉项加起来为 0,平均误差只多出「挪动量的平方」。
- 切前。四单的实际耗时是 12、14、22、24 分钟。均值是 (12 + 14 + 22 + 24) ÷ 4 = 18 分钟。
MSE = (6² + 4² + 4² + 6²) ÷ 4 = 104 ÷ 4 = 26。 - 切后。在 2.5 公里切开。左叶预测 (12 + 14) ÷ 2 = 13 分钟,右叶预测 (22 + 24) ÷ 2 = 23 分钟。
MSE = (1² + 1² + 1² + 1²) ÷ 4 = 1。
平方误差回归树逐个比较合格的切点,选择让本节点平方误差下降最多的那一刀。本例的 2.5 公里是中间两个距离的中点。
其余切点是 1.5 和 3.5 公里,都会留下一组只有一单、另一组有三单。试切在 1.5 公里,两叶均值是 12 和 20 分钟,MSE 是 (0² + 6² + 2² + 4²) ÷ 4 = 14。另一刀也可用同样的步骤验证。
下一课的梯度提升决策树(Gradient Boosting Decision Tree,GBDT)会一棵一棵地加入新树。新树的叶子输出数值,用来修正现有预测。现在先用练习把本章的切分和叶子预测串起来。
用练习串起切分与预测
先自己算或说出理由,再点选项。也可以直接展开答案与解析。
单选1. 假设拿一个新特征来切同一批订单。小组有 2 单且都超时,大组有 8 单超时、10 单准时。切后加权基尼约为多少?
看答案与解析
答案:B
小组基尼是 0。大组基尼约为 1 − (8 ÷ 18)² − (10 ÷ 18)² ≈ 0.494。按人数加权是 (2 ÷ 20) × 0 + (18 ÷ 20) × 0.494 ≈ 0.444。0.247 是把两个大小不同的组各给一半权重。
单选2. 为什么订单 ID 这类高基数特征会诱骗树?
看答案与解析
答案:C
它能把训练样本切成很多极小分支,训练纯度很高,却没有学到可泛化的规律。
单选3. max_depth 与 min_samples_leaf 各在防什么?
看答案与解析
答案:B
前者限制问题的层数,后者禁止只有极少样本的叶子;两者都在防背答案。
单选4. 为什么经典 GBDT 会用叶子输出数值的树?
看答案与解析
答案:C
每棵新树要为现有预测提供数值修正,回归树的叶子可以输出这样的数值。
单选5. 一个节点里有 8 单超时、2 单准时,基尼是多少?
看答案与解析
答案:A
1 − 0.8² − 0.2² = 1 − 0.64 − 0.04 = 0.32。
回顾与下一课
回头讲一遍:提出候选问题,算每组的分数,按人数加权,再选下降最多的一刀。走到分类叶子取多数类别,平方误差回归叶子取组内平均。训练分数再好,也要用没参与拟合的数据检验。
下一课集成学习与 GBDT会讲多棵树怎样配合。随后,评估与过拟合会用验证数据检查模型在新样本上的表现。