一、决策树要解决什么问题
机器学习中有一类问题叫作监督学习:我们手里有一些已知答案的数据,希望机器从中总结规律,遇到新数据时能够给出预测。
例如,一个银行积累了若干贷款申请记录。每条记录包含申请人的年龄、是否有工作、是否有自己的房子、信用情况,以及过去是否批准了贷款。我们想把这些记录交给机器,让它学会判断新申请应该属于“批准”还是“不批准”这两个类别。
决策树的做法很像一个不断提问的人:
- 先问一个对判断结果很有帮助的问题。
- 根据答案,把人分成不同的小组。
- 如果某组已经很容易判断,就直接给出结论。
- 如果某组仍然分不清,就继续问下一个问题。
一棵可能的树长这样:
flowchart TD
A{"有自己的房子吗?"}
A -->|"有"| B["批准贷款"]
A -->|"没有"| C{"有工作吗?"}
C -->|"有"| D["批准贷款"]
C -->|"没有"| E["不批准贷款"]
拿三个新申请人试试看:
- 小明有房子,但没有工作:沿着第一个问题的“有”分支走,预测批准。
- 小红没有房子,但有工作:先走“没有”,再走“有”,预测批准。
- 小刚既没有房子,也没有工作:连续走两个“没有”,预测不批准。
这就是决策树的直觉:把数据按特征逐层划分,让每个最终的小组尽可能有明确的预测结果。
这里的规则只是一份小型教学数据可能学出的结果,并不是现实银行应当采用的放贷政策。真实贷款审批还要考虑法律、合规、公平性和很多其他因素。
决策树可以做两类任务:
- 分类:预测类别,例如“批准/拒绝”“垃圾邮件/正常邮件”“猫/狗”。
- 回归:预测数值,例如房价、温度或销售额。回归树也是决策树的一种,后面会专门介绍。
二、决策树的结构、规则和概率解释
2.1 组成一棵树的几个部件
决策树中通常有以下元素:
| 名称 | 英文 | 通俗解释 |
|---|---|---|
| 根节点 | Root node | 从哪里开始问问题,例如“有房子吗” |
| 内部节点 | Internal node | 还需要继续判断的问题,例如“有工作吗” |
| 分支/有向边 | Branch/Directed edge | 问题的一种答案以及下一步要走的方向 |
| 叶节点 | Leaf node | 不再继续提问,直接给出最终预测的地方 |
这里的“特征”就是数据里能用来提问的属性,例如年龄、面积、工作情况;“类别”是我们要预测的答案,例如是否批准。
2.2 决策树就是一组 if-then 规则
从根节点走到一个叶节点,就得到一条规则:
如果 有自己的房子,那么 批准贷款。
如果 没有自己的房子 且 有工作,那么 批准贷款。
如果 没有自己的房子 且 没有工作,那么 不批准贷款。
所以,一棵分类决策树可以写成一组 if-then 规则。
如果每个节点的所有可能答案都有对应分支,且新样本的必要特征都已知,这组规则具有两个性质:
- 互斥:一个样本不会同时沿着两条不同的完整路径走到终点。
- 完备:一个样本一定有一条从根节点到叶节点的路径可以走。
例如,“有房子”和“没有房子”互斥;两种情况合起来又覆盖了是否有房子的所有已知情况。
2.3 决策树也可以理解为一组条件概率
设:
- $X$ 表示一个样本的特征,例如年龄、工作、房产等。
- $Y$ 表示样本类别,例如“批准”和“拒绝”。
机器最终想知道的是:
\[P(Y\mid X)\]读作“已知特征 $X$,属于类别 $Y$ 的概率”。
举例:某个叶节点里有10个训练样本,其中9个属于“批准”,1个属于“拒绝”。根据这组训练样本估计:
\[P(Y=\text{批准}\mid X\text{落入该叶节点})\approx\frac9{10}=0.9\]如果要输出一个确定类别,就选择概率最大的类别,也就是“批准”。
需要区分两个概念:
- 叶节点的类别:通常是样本最多的类别。
- 叶节点的类别概率:各类别在这个叶节点中的比例估计。
因此,决策树既可以解释为一套判断规则,也可以解释为把特征空间切成若干区域,并在每个区域给出一个类别概率分布。
2.4 “划分特征空间”到底是什么意思
假设预测房价时只考虑房屋面积和房龄。把每套房子画成平面上的一个点,横坐标是面积,纵坐标是房龄。
如果第一问是“面积是否大于80平方米”,相当于用一条竖线把平面分成两块。如果某一块再问“房龄是否超过10年”,就相当于用一条横线继续切分。
每问一个问题,就缩小一次可能的区域;每条完整路径对应一个最终区域。这个几何解释对后面的CART回归树尤其有用。
三、训练决策树:从一堆数据到一套规则
现在的问题是:机器凭什么知道先问“有没有房子”,而不是先问“年龄”?
它不能靠直觉,需要通过数据计算。
一般的建树过程如下:
- 把所有训练样本放在根节点。
- 对每个候选特征,尝试用它把数据分组。
- 计算哪种分组能让各组的类别更明确。
- 选出当前最好的特征,形成分支。
- 在尚未分清的子组里继续重复上述过程。
- 当满足停止条件时,让当前节点变成叶节点。
但“类别更明确”到底怎样衡量?
这需要一些数学指标。接下来会从信息熵开始,一步步推到信息增益、信息增益比和基尼指数。
还有一个重要特点:多数经典建树算法使用贪心策略。每次只选当前最好的划分,而不会事先枚举世界上所有可能的树再找全局最优。
原因是,找一棵整体最优的决策树涉及非常庞大的组合搜索;通常的算法要在计算成本和结果质量之间做取舍。
四、完整例子:15位贷款申请人
为了让后面的每个公式都能落在具体数据上,我们固定使用下面这15条教学样本。
有四个输入特征:
- 年龄:青年、中年、老年。
- 有工作:是、否。
- 有自己的房子:是、否。
- 信贷情况:一般、好、非常好。
目标类别只有两个:是否批准贷款。
| 编号 | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 批准贷款 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
先数一数最后一列:
- 批准:9人。
- 拒绝:6人。
- 总人数:15人。
我们把这15条训练记录的集合记为 $D$,即:
\[|D|=15\]其中 $\lvert D\rvert$ 表示集合 $D$ 中的样本数量。后面公式里出现的竖线,如 $\lvert D_i\rvert$,也都是“集合里有多少个样本”的意思。
这是整篇教程的核心例子。读到后面的计算时,可以随时回来查看这些原始数据。
五、信息熵:怎样用数字表示混乱程度
5.1 先不看公式,只看直觉
有三个盒子,每个盒子放10张卡片。红卡代表“批准”,蓝卡代表“拒绝”。
盒子A:10张红卡,0张蓝卡。
随便抽一张,你知道一定是红卡。结果完全确定。
盒子B:9张红卡,1张蓝卡。
大概率能猜中红卡,但仍然有一点不确定。
盒子C:5张红卡,5张蓝卡。
红蓝各占一半,最难猜。
我们希望用一个数字表示“不确定程度”:
\[\text{盒子A的混乱程度}<\text{盒子B的混乱程度}<\text{盒子C的混乱程度}\]这个数字就是信息熵(entropy)。
一句话记忆:熵越大,类别分布越混杂;熵越小,类别越确定。
5.2 信息熵公式
如果一个随机变量 $X$ 可能取 $n$ 个值,第 $i$ 个值出现的概率为 $p_i$,它的熵定义为:
\[\boxed{H(X)=-\sum_{i=1}^{n}p_i\log_2p_i}\]各个符号的意思:
| 符号 | 意思 |
|---|---|
| $H(X)$ | 随机变量 $X$ 的信息熵 |
| $p_i$ | 第 $i$ 种结果出现的概率 |
| $\sum$ | 把所有可能结果的对应项加起来 |
| $\log_2$ | 以2为底的对数 |
| 前面的负号 | 让最终熵为非负数 |
如果你不熟悉对数,可以先记住几个值:
\[\log_2 1=0,\qquad\log_2\frac12=-1,\qquad\log_2\frac14=-2\]为什么用对数?信息论中,一个罕见事件发生时通常会带来更多“意外信息”。事件概率为 $p$ 时,它的信息量可以写为 $-\log_2p$;而熵就是对所有结果的信息量按概率取平均。于是得到 $-\sum p_i\log_2p_i$。
这里的对数底数取2,因此熵的单位可以叫作比特(bit)。使用其他底数不会改变在同一底数下对特征优劣的基本比较思路。
特别规定:当 $p_i=0$ 时,$p_i\log p_i$ 按极限记为0。因此某个类别完全没出现,不会导致计算出错。
5.3 二分类的熵怎么计算
如果只有“批准”和“拒绝”两类,批准概率为 $p$,拒绝概率就是 $1-p$。公式简化为:
\[\boxed{H(p)=-p\log_2p-(1-p)\log_2(1-p)}\]情况一:两类各占一半。
\[\begin{aligned} H(0.5)&=-0.5\log_20.5-0.5\log_20.5\\ &=-0.5(-1)-0.5(-1)\\ &=1 \end{aligned}\]情况二:一类占90%,另一类占10%。
\[H(0.9)=-0.9\log_20.9-0.1\log_20.1\approx0.469\]情况三:全部属于同一类。
\[H(1)=0\]所以,对于二分类:
- $p=0$ 或 $p=1$ 时,熵为0,完全确定。
- $p=0.5$ 时,熵为1,最不确定。
- $p$ 越接近0.5,类别越混杂;越靠近0或1,类别越纯净。
多分类时同理,只不过熵的最大值是 $\log_2K$,其中 $K$ 是类别数量,最大值出现在各类概率相同时。
5.4 计算15位贷款申请人的原始熵
现在回到数据集 $D$。批准占 $9/15$,拒绝占 $6/15$。
\[\begin{aligned} H(D) &=-\frac9{15}\log_2\frac9{15}-\frac6{15}\log_2\frac6{15}\\ &\approx0.971 \end{aligned}\]这个0.971的意思是:在还没有询问任何特征的时候,贷款结果有较高的不确定性。
下一步要做的事,就是找到一个问题,把这0.971尽可能明显地降下来。
六、条件熵和信息增益:怎样选择第一个问题
6.1 条件熵是什么
假设先问:“有自己的房子吗?”
15个人被分成两组:
| 组别 | 人数 | 批准 | 拒绝 | 组内熵 |
|---|---|---|---|---|
| 有房子 | 6 | 6 | 0 | 0 |
| 没房子 | 9 | 3 | 6 | 约0.918 |
有房子这组全部批准,已经没有混乱,所以熵为0。
没房子这组,批准概率为 $3/9$,拒绝概率为 $6/9$,因此:
\[\begin{aligned} H(D_{\text{无房}}) &=-\frac39\log_2\frac39-\frac69\log_2\frac69\\ &\approx0.918 \end{aligned}\]但是,我们需要一个数字评价“按有无房子分组”之后整体还剩多少混乱。此时不能简单计算 $(0+0.918)/2$,因为两个组人数不同。
正确做法是按照每组样本数占总样本数的比例,加权平均:
\[\begin{aligned} H(D\mid\text{房子}) &=\frac6{15}\times0+\frac9{15}\times0.918\\ &\approx0.551 \end{aligned}\]这就是条件熵。
通俗理解:知道了一个特征,并按该特征分组后,对类别仍然有多少不确定性。
一般公式是:
\[\boxed{H(D\mid A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)}\]其中:
- $A$:用来分组的特征。
- $D_i$:按照特征 $A$ 的第 $i$ 个取值分出来的子集。
- $\lvert D_i\rvert/\lvert D\rvert$:该子集所占的样本比例。
- $H(D_i)$:该子集内部类别的熵。
计算时只需记住:先算各组的熵,再按组的大小加权。
6.2 信息增益是什么
原来的熵是:
\[H(D)=0.971\]知道有无房子之后,条件熵是:
\[H(D\mid\text{房子})=0.551\]减少了多少?
\[0.971-0.551=0.420\]这0.420就是“有自己的房子”这个特征带来的信息增益(information gain)。
一般公式:
\[\boxed{g(D,A)=H(D)-H(D\mid A)}\]它等于:
分组前的不确定性 − 分组后的平均不确定性。
因此:信息增益越大,说明这个特征越能帮助我们区分类别。
信息论里,类别 $Y$ 和特征 $A$ 之间的这个差值也可以理解为互信息 $I(Y;A)$ 的经验估计。
6.3 如果先问“有工作吗”呢
根据原始数据:
- 有工作的5个人全部批准,组内熵为0。
- 没工作的10个人中,4人批准、6人拒绝。
没工作的组内熵为:
\[H(D_{\text{无工作}}) =-\frac4{10}\log_2\frac4{10}-\frac6{10}\log_2\frac6{10} \approx0.971\]按工作分组后的条件熵:
\[H(D\mid\text{工作}) =\frac5{15}\times0+\frac{10}{15}\times0.971 \approx0.647\]信息增益:
\[g(D,\text{工作})=0.971-0.647\approx0.324\]“有工作”也能减少混乱,但效果不如“有自己的房子”:
\[0.324<0.420\]6.4 四个特征都算一遍
同样地,可以把“年龄”和“信贷情况”也按各自取值分组,得到:
| 特征 | 分组后的条件熵(约) | 信息增益(约) |
|---|---|---|
| 年龄 | 0.888 | 0.083 |
| 有工作 | 0.647 | 0.324 |
| 有自己的房子 | 0.551 | 0.420 |
| 信贷情况 | 0.608 | 0.363 |
第一层应该选择哪个特征?
答案是有自己的房子,因为它的信息增益最大。
不难理解:只问一个“有没有房子”,有房子的6个人就已经全部分清;剩下9个人还需要进一步判断。
6.5 “经验熵”与“经验条件熵”是什么意思
如果我们知道真实世界中每种结果的准确概率,计算出的就是理论上的熵。
但实际机器学习一般不知道真实概率,只能用训练数据估计。例如15人里9人批准,就估计批准概率为 $9/15$。
使用这种从样本估计出来的概率计算得到的熵,叫作经验熵;由样本分组比例计算的条件熵,叫作经验条件熵。
名字听起来复杂,实质就是:概率不是凭空已知的,而是用手头数据的频率估出来的。
七、信息增益比:为什么要惩罚分得太碎的特征
7.1 信息增益的一个缺点
假设除了年龄、工作和房产,我们还把每个人的“唯一编号”作为一个特征。
因为每个人编号不同,按编号分组会产生15个小组,每组只有1个人。每组的类别都确定,熵为0。
因此这个特征的信息增益会达到原始熵:
\[g(D,\text{编号})=H(D)-0=0.971\]这比“有自己的房子”的0.420还大。
可编号只是一个身份标识,对从没见过的新申请人通常没有预测意义。这里暴露了信息增益的偏好:它倾向于选择取值种类较多、可以把训练数据分得很碎的特征。
7.2 信息增益比的公式
为了校正这种偏好,可以引入信息增益比(information gain ratio):
\[\boxed{g_R(D,A)=\frac{g(D,A)}{H_A(D)}}\]分子还是信息增益;分母 $H_A(D)$ 是特征 $A$ 自身取值分布的熵:
\[H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}\]怎么理解分母?
- 一个特征只有少数几种取值,分母可能较小。
- 一个特征有很多种取值,而且各取值的样本分布比较均匀,分母就可能很大。
用信息增益除以它,就能惩罚一部分“单靠取值很多而获得高信息增益”的特征。
例如15个编号各出现1次,编号特征的熵为:
\[H_{\text{编号}}(D)=-15\times\frac1{15}\log_2\frac1{15}=\log_2 15\approx3.907\]编号的信息增益比约为:
\[g_R(D,\text{编号})=\frac{0.971}{3.907}\approx0.249\]而“有自己的房子”这个特征,两组分别有6人和9人,其取值熵为:
\[H_{\text{房子}}(D) =-\frac6{15}\log_2\frac6{15}-\frac9{15}\log_2\frac9{15} \approx0.971\]对应的信息增益比:
\[g_R(D,\text{房子})\approx\frac{0.420}{0.971}\approx0.433\]这时房产特征就明显优于没有泛化意义的编号。
信息增益比并非完美指标,它可能反过来偏好取值较少的特征。实际的C4.5通常还会结合信息增益等条件筛选候选特征,不能简单理解为“只看一个分数就永远没有问题”。
八、ID3算法:一步步把树长出来
前面解决了“怎样评价一个特征好不好”的问题。现在把这个评价方法写成真正的建树算法。
8.1 ID3的核心规则
在当前节点,计算所有候选特征的信息增益,选择信息增益最大的那个特征进行划分。然后对子节点重复这个过程。
这里的“当前节点”很重要:进入某个子节点后,只考虑流入这个子节点的那部分训练数据,而不是每次都重新拿全部15个人计算。
8.2 第一步:选择根节点
我们已经算过全部15人的信息增益:
| 特征 | 信息增益 |
|---|---|
| 年龄 | 0.083 |
| 有工作 | 0.324 |
| 有自己的房子 | 0.420 |
| 信贷情况 | 0.363 |
于是根节点选择“有自己的房子”。
它产生两个分支:
- 有房子:6个人全部批准,可以直接形成“批准”叶节点。
- 没房子:9个人中3人批准、6人拒绝,还不能直接给出足够明确的结论。
8.3 第二步:只在“没有房子”的9个人中继续选择
记这9个人构成的子数据集为 $D_2$。现在:
\[H(D_2)=-\frac39\log_2\frac39-\frac69\log_2\frac69\approx0.918\]“有自己的房子”已经在上一层使用过,因此这里考虑剩下的三个特征:年龄、工作、信贷情况。
计算得到:
| 在 $D_2$ 中考虑的特征 | 信息增益(约) |
|---|---|
| 年龄 | 0.251 |
| 有工作 | 0.918 |
| 信贷情况 | 0.474 |
“有工作”的信息增益达到0.918,恰好等于当前整个子集的熵。这意味着一问“有没有工作”,剩余的混乱就全部消除了。
核对原始数据:
- 没房子但有工作:编号3、13、14,共3人,全部批准。
- 没房子又没工作:其余6人,全部拒绝。
所以再分一次就结束了。完整树为:
flowchart TD
A{"有自己的房子吗?"}
A -->|"是"| B["批准"]
A -->|"否"| C{"有工作吗?"}
C -->|"是"| D["批准"]
C -->|"否"| E["拒绝"]
注意,ID3并不要求把所有特征都用上。这里没有使用年龄和信贷情况,因为只靠房产、工作两个特征就能把训练样本分清。
8.4 算法什么时候停止
递归地划分总要有停止条件,常见情况包括:
- 当前数据全部属于同一类别:直接建立该类别的叶节点。
- 没有剩余候选特征:把当前样本中占比最高的类别作为叶节点结果。
- 最优信息增益也很小:继续划分没有太大价值,可以设置阈值 $\varepsilon$,当 $\max_A g(D,A)<\varepsilon$ 时停止,输出多数类。
没有任何特征能够区分的两条训练样本,可能仍然拥有不同标签。此时决策树无法凭空制造新的信息,只能采用多数类等策略给出预测。
8.5 用伪代码理解ID3
建立决策树(数据集D, 候选特征集合A):
如果D里的样本全部属于同一类别:
返回该类别的叶节点
如果A为空:
返回D中多数类别对应的叶节点
对A中的每一个特征计算信息增益
找到信息增益最大的特征A_best
如果信息增益小于停止阈值:
返回D中多数类别对应的叶节点
创建一个以A_best为判断问题的内部节点
对A_best的每种取值:
取出与该值对应的子数据集
对该子数据集递归调用“建立决策树”
返回建立好的树
这里省略了空分支、缺失值等工程细节,但已经包含ID3的核心逻辑。
8.6 为什么说建树是“局部最优”
假设根节点有两个候选特征。A带来的当前信息增益比B高,于是贪心算法选择A。但未来继续划分后,以B开头的整棵树可能更浅,或者在测试数据上的表现更好。
ID3在根节点并不知道未来所有分支的结果。它只选择当前看起来最有效的问题,所以叫作局部贪心选择。
这并不等于算法没有用。相反,贪心选择让决策树能以可接受的计算成本,得到通常相当有用的模型。
九、C4.5算法:对ID3的改进
9.1 为什么要改进ID3
我们前面看到,如果某个特征拥有大量不同取值,例如唯一编号,信息增益可能很高,却无法很好地预测未来数据。
所以C4.5保留了“自上而下、递归分组”的基本思路,但改进了选择分裂特征的标准。
它使用的信息增益比为:
\[g_R(D,A)=\frac{H(D)-H(D\mid A)}{H_A(D)}\]分母的存在,让多取值特征不再可以只依靠“把训练样本分得特别碎”轻易获胜。
9.2 C4.5的建树步骤
它和ID3很像:
- 检查当前数据是否已经足够纯净。
- 评价剩余候选特征。
- 按信息增益比等准则选择合适的划分特征。
- 根据所选特征划分数据。
- 对子数据集继续递归。
因为核心建树方式类似,理解了ID3后,理解C4.5主要需要把握评价特征的指标变了。
在完整算法中,C4.5还可以处理连续属性、缺失值,并配合剪枝技术。不同教材的精简版实现不一定覆盖这些细节;这里重点讨论它的特征选择思想。
9.3 一个容易混淆的问题
“信息增益大”与“信息增益比大”不是同一回事。信息增益直接看不确定性减少多少,信息增益比还会考虑特征取值分布的分散程度。
因此,两套指标有可能选择不同的根节点;它们的结果并不需要始终一致。
十、过拟合与剪枝:为什么树不能无限生长
10.1 训练准确率高,不代表预测新数据一定好
想象两位学生准备数学考试:
- 学生甲把练习册每道题的答案都背下来。
- 学生乙弄懂了题型和解法,即使练习中偶尔出错,也能够应对新题。
决策树也可能像学生甲一样“死记硬背”训练数据。
例如,数据里恰好有一位特征很特殊的申请人。如果我们为了让这一个训练样本也被正确分类,继续增加很多细碎分支,树在训练集上可能100%正确,但对新申请人反而判断得不稳。
这就叫作过拟合(overfitting):模型对训练数据拟合得过度,学习到了偶然噪声或特殊细节,泛化到未知样本时效果变差。
反过来,树如果只有一个叶节点,对所有人一律作出相同判断,通常又太简单。这种无法学到足够规律的情况叫作欠拟合(underfitting)。
所以真正的目标不是“树越深越好”,也不是“树越浅越好”,而是树的复杂程度适合当前问题。
10.2 两种抑制复杂度的方法
预剪枝(pre-pruning):建树时就设限。比如节点样本太少时不再划分、树达到最大深度就停止、信息增益太小时停止。
后剪枝(post-pruning):先长出一棵比较完整的树,再检查哪些分支没有足够价值,把它们删掉。
这两种方法都是为了解决过拟合,只是干预的阶段不同。
10.3 损失函数为什么加上复杂度惩罚
只看训练损失,复杂树往往更容易占优势:它可以不断细分训练数据,甚至记住异常样本。
于是引入代价复杂度损失:
\[\boxed{C_\alpha(T)=C(T)+\alpha|T|}\]其中:
- $T$:一整棵决策树。
- $C(T)$:这棵树对训练数据的拟合损失。
- $\lvert T\rvert$:叶节点数量,用来衡量树的复杂度。
- $\alpha\ge0$:复杂度惩罚系数。
可以把这个公式理解为:
总成本 = 预测不准确的成本 + 树太复杂的成本。
如果 $\alpha=0$,就不惩罚叶节点数量,树可能很大。
如果 $\alpha$ 很大,增加叶节点的代价很高,模型更倾向于一棵小树。
这里的 $C(T)$ 可以基于不同的训练损失定义。比如,在使用经验熵的一个分类树剪枝形式中:
\[C(T)=\sum_{\ell\in\mathcal L(T)}N_\ell H_\ell\]这里 $\mathcal L(T)$ 是叶节点集合,$N_\ell$ 是进入叶节点 $\ell$ 的训练样本数,$H_\ell$ 是该叶节点内的类别熵。
直观地看,一个叶节点内样本越混杂,它带来的分类损失越大;叶节点越多,复杂度惩罚也越大。
回归树常使用平方误差之和作为 $C(T)$;有些分类树剪枝方法使用错分误差。不同损失的数值尺度可以不同,但代价复杂度的数学结构保持相同。
10.4 用数字看“准确”与“简单”的权衡
假设两棵候选树:
| 项目 | 树A | 树B |
|---|---|---|
| 训练损失 $C(T)$ | 2 | 3 |
| 叶节点数量 $\lvert T\rvert$ | 10 | 4 |
若 $\alpha=0.5$:
\[C_{0.5}(A)=2+0.5\times10=7\] \[C_{0.5}(B)=3+0.5\times4=5\]树A的训练损失更小,但树B在这个复杂度惩罚下的综合损失更小,因此树B更合适。
这些数字只是帮助理解公式的例子,并非某个真实实验的结果。
十一、CART分类树:用基尼指数决定怎样分
11.1 CART和前两种算法的主要区别
CART是 Classification and Regression Tree 的缩写,中文叫“分类与回归树”。
它既可以做分类,也可以做回归。最重要的结构特点是:CART生成的是二叉树,每个内部节点都恰好进行一次二分。
例如,年龄有青年、中年、老年三个取值:
- ID3的简单多叉划分可以一次产生青年、中年、老年三个分支。
- CART可以考虑“青年/非青年”“中年/非中年”等二分方式,每次只保留两条分支。
对连续数值特征,比如面积,可以提出“面积 $\le80$ 平方米吗”这样的二元问题。
11.2 基尼指数:另一种混乱程度指标
CART分类树通常用基尼指数(Gini impurity)评价分组是否纯净。
假设有 $K$ 个类别,第 $k$ 类的比例为 $p_k$,定义:
\[\boxed{\operatorname{Gini}(D)=1-\sum_{k=1}^{K}p_k^2}\]二分类时,某一类概率为 $p$,另一类为 $1-p$:
\[\begin{aligned} \operatorname{Gini}(p) &=1-p^2-(1-p)^2\\ &=1-p^2-(1-2p+p^2)\\ &=2p-2p^2 \end{aligned}\]因此:
\[\boxed{\operatorname{Gini}(p)=2p(1-p)}\]看看三个例子:
| 类别比例 | 基尼指数 | 意味着什么 |
|---|---|---|
| 100%和0% | 0 | 完全纯净 |
| 90%和10% | 0.18 | 比较纯净 |
| 50%和50% | 0.5 | 二分类中最混杂 |
它和信息熵的变化规律相似,但数值尺度不同。比如50%对50%时,熵等于1,基尼指数等于0.5。
两者都是“越小越纯净”,只是具体计算方法不同。
11.3 CART怎样评价一次二分
假设某个划分方案把数据集 $D$ 分成 $D_1$ 和 $D_2$。划分后的加权基尼指数是:
\[\boxed{ \operatorname{Gini}(D,A) =\frac{|D_1|}{|D|}\operatorname{Gini}(D_1) +\frac{|D_2|}{|D|}\operatorname{Gini}(D_2) }\]这和计算条件熵的结构很像:
- 先分别计算两个子组的基尼指数。
- 再按子组样本比例加权平均。
- 选择加权基尼指数最小的划分。
注意区分两个方向:
- ID3比较信息增益,越大越好。
- CART分类树比较划分后的加权基尼指数,越小越好。
11.4 用15人贷款数据计算基尼指数
最初9人批准、6人拒绝,原始基尼指数为:
\[\begin{aligned} \operatorname{Gini}(D) &=1-\left(\frac9{15}\right)^2-\left(\frac6{15}\right)^2\\ &=1-0.36-0.16\\ &=0.48 \end{aligned}\]现在尝试按“有自己的房子”二分:
- 有房子:6人全部批准,基尼指数0。
- 没房子:9人中3人批准、6人拒绝。
没房子这组的基尼指数:
\[\operatorname{Gini}(D_{\text{无房}}) =1-\left(\frac39\right)^2-\left(\frac69\right)^2 =\frac49\approx0.444\]加权得到:
\[\begin{aligned} \operatorname{Gini}(D,\text{房子}) &=\frac6{15}\times0+\frac9{15}\times\frac49\\ &=\frac4{15}\approx0.267 \end{aligned}\]使用这组数据,对每个特征的所有候选二分方案进行比较,可以得到以下最优划分后的基尼指数:
| 特征 | 该特征最佳二分的加权基尼指数(约) |
|---|---|
| 年龄 | 0.44 |
| 有工作 | 0.32 |
| 有自己的房子 | 0.27 |
| 信贷情况 | 0.32 |
所以CART也会优先问“有没有自己的房子”。但要注意,这是因为这份数据恰好如此;换一份数据,ID3和CART完全可能得到不同的树。
11.5 CART怎样寻找切分点
对于二值特征(是否有房子),切分方式比较直接。
对于有多个取值的类别特征,CART需要比较不同的二分方案。对于连续特征,它还要寻找合适的数值阈值。
例如年龄是具体数值 $23,28,35,42,57$,可以考虑:
年龄 <= 25.5 ?
年龄 <= 31.5 ?
年龄 <= 38.5 ?
年龄 <= 49.5 ?
把样本按候选阈值分成两组,分别计算加权基尼指数,最后选最小的一种。
随着递归进行,每个新节点都重复这一过程,直到满足停止条件,例如当前节点已足够纯净、样本太少或树已达到设定深度。
十二、CART回归树:怎样预测一个数值
12.1 回归树的叶节点为什么是数字
分类树最后输出“批准”或“拒绝”,回归树最后输出具体数值。
比如预测房价,我们有4条训练数据:
| 房屋面积 | 真实房价 |
|---|---|
| 60㎡ | 100万元 |
| 70㎡ | 120万元 |
| 90㎡ | 200万元 |
| 110㎡ | 240万元 |
假设按面积是否超过80㎡二分:
第一组是60㎡和70㎡,其平均房价为:
\[c_1=\frac{100+120}{2}=110\text{万元}\]第二组是90㎡和110㎡,其平均房价为:
\[c_2=\frac{200+240}{2}=220\text{万元}\]于是回归树形成一条简单规则:
如果面积 <= 80㎡,预测房价110万元。
如果面积 > 80㎡,预测房价220万元。
为什么每组取平均值?因为当用一个固定数字预测这一组所有训练样本、并以平方误差之和衡量损失时,最优的固定数字就是这一组目标值的平均数。
12.2 什么是平方误差
假设真实房价为120万元,预测为110万元,误差是:
\[120-110=10\text{万元}\]平方误差为:
\[(120-110)^2=100\]如果预测200万元而真实只有120万元,平方误差就是:
\[(120-200)^2=6400\]可见,偏差越大,平方误差增长得越快。
对一个叶节点内所有样本,平方误差之和为:
\[\operatorname{SSE}=\sum_{i\in\text{该叶节点}}(y_i-c)^2\]其中 $y_i$ 是真实数值,$c$ 是这个叶节点给出的统一预测值。
12.3 为什么要选择合适的切分阈值
如果按80㎡二分:
第一组的平方误差和:
\[(100-110)^2+(120-110)^2=200\]第二组的平方误差和:
\[(200-220)^2+(240-220)^2=800\]所以总平方误差为:
\[200+800=1000\]如果换成“面积是否超过65㎡”,第一组只有100万元这一条记录;第二组的房价是120、200、240万元,平均约186.67万元。总平方误差会变成约7466.67,明显更大。
因此,80㎡这个阈值比65㎡更好。
真正的CART回归算法会考虑不同特征和不同切分点,寻找使平方误差之和最小的方案。
12.4 CART回归树的优化公式
设用第 $j$ 个特征的阈值 $s$ 将数据分成两组:
\[R_1(j,s)=\{x:x^{(j)}\le s\}\] \[R_2(j,s)=\{x:x^{(j)}>s\}\]这里 $x^{(j)}$ 表示样本 $x$ 的第 $j$ 个特征。
我们要选择 $j,s$ 和两组各自的预测值 $c_1,c_2$,让下面的量最小:
\[\boxed{ \min_{j,s}\left[ \min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 +\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2 \right] }\]不要被双重最小化吓住。它只是说:
- 假设先选一个特征和一个切分点。
- 分别求左右两组的最佳预测值(也就是两组各自的平均值)。
- 计算两组的平方误差之和。
- 换一个切分点重复计算。
- 选择总平方误差最小的方案,再对子组继续递归。
分类CART和回归CART的树形结构相同,主要差别在于:分类用类别纯度判断怎样切,回归用数值预测误差判断怎样切。
十三、CART代价复杂度剪枝:完整理解$g(t)$
这是理解CART算法时最容易卡住的一部分。我们会先看直觉,再解释每个符号,然后一步步推导公式,最后用数字说明为什么每次要剪 $g(t)$ 最小的子树。
13.1 剪枝面临的两难选择
假设某个节点下面已经长出一棵复杂的子树。它用好几个问题一步步判断样本。
现在有两个选择:
选择A:保留子树。
优点是更贴合训练数据,通常训练误差较小;缺点是叶节点较多,结构复杂。
选择B:剪掉子树。
把子树下面的所有分支删掉,让子树的根节点直接变成一个叶节点。优点是结构简单;缺点是许多本来分开的样本现在必须采用同一种预测,训练误差可能增加。
剪枝要解决的就是:训练误差多增加一点,能换来多少复杂度的下降?这个交换值不值得?
13.2 两个很容易混淆的记号:t和T_t
假设一棵树的某个部分如下:
flowchart TD
t["内部节点 t"]
a["内部节点 a"]
l1["叶节点1"]
l2["叶节点2"]
l3["叶节点3"]
t --> a
t --> l3
a --> l1
a --> l2
- 小写 $t$:我们正在考虑的一个内部节点。
- 大写 $T_t$:以 $t$ 为根的整棵子树,包括它下面的所有节点和分支。
如果把 $T_t$ 剪掉,保留的不是空白,而是一个单独的叶节点 $t$。这和直接把整个区域从世界上删除是两回事。
13.3 $C(t)$和$C(T_t)$分别是什么
$C(t)$:把节点 $t$ 变成一个叶节点之后,这一部分数据的训练损失。
例如,20个样本来到节点 $t$,其中15个是A类、5个是B类。若直接让 $t$ 作为叶节点,预测所有样本都是A类,那么有5个样本会错分。
如果暂时用“错分样本数”衡量损失,可以写:
\[C(t)=5\]$C(T_t)$:保留以 $t$ 为根的整棵子树时,这一部分数据的总训练损失。
假设子树继续问问题,分到3个叶节点以后,只错分1个样本,那么:
\[C(T_t)=1\]所以:
\[C(t)-C(T_t)=5-1=4\]这表示:如果把子树压缩成一个叶节点,训练损失将增加4。
这里用错分数量举例是为了让计算直观。实际剪枝可以使用统一定义的其他训练损失,例如叶节点经验熵加权和。关键是比较时前后采用同一种损失口径。
13.4 为什么分母是 $\lvert T_t\rvert-1$
设原来的子树有3个叶节点:
\[|T_t|=3\]剪枝后,整个子树压缩成节点 $t$,它现在是1个叶节点。
因此叶节点从3个变成1个,实际减少了:
\[3-1=2\]一般来说,叶节点减少量为:
\[\boxed{|T_t|-1}\]注意,$\lvert T_t\rvert$ 统计的是子树的叶节点个数,并不是包括内部节点在内的所有节点个数。
为什么不能直接除以 $\lvert T_t\rvert$?因为剪枝以后还剩下节点 $t$ 这个新叶节点,并不是把原来的叶节点数全部减少为0。
13.5 $g(t)$的直观含义
现在把分子和分母组合:
\[\boxed{g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}}\]它等于:
\[\boxed{ \frac{\text{剪枝增加的训练损失}}{\text{剪枝减少的叶节点数量}} }\]也就是:每减少一个叶节点,平均要牺牲多少训练集上的拟合效果。
代入刚才的数字:
\[g(t)=\frac{5-1}{3-1}=2\]这意味着,把这段子树剪掉,每减少一个叶节点,平均要增加2个单位的训练损失。
想象两棵候选子树:
- 子树A:每减少一个叶节点,就要增加10个单位的训练损失。
- 子树B:每减少一个叶节点,只增加1个单位的训练损失。
如果想简化整棵树,显然子树B更适合优先考虑剪掉。它损失的拟合效果相对较小,却能节省复杂度。
但“比较每个叶节点的平均代价”还不是完整的数学理由。下一步才是这个公式的关键。
13.6 $g(t)$为什么恰好是剪枝的临界值
先回顾代价复杂度损失:
\[C_\alpha(T)=C(T)+\alpha|T|\]现在只比较节点 $t$ 下面这部分结构。树的其他部分无论怎么选都不变,比较时可以抵消。
第一种方案:保留子树 $T_t$。
保留时,子树训练损失是 $C(T_t)$,叶节点有 $\lvert T_t\rvert$ 个,因此:
\[\boxed{C_\alpha(T_t)=C(T_t)+\alpha|T_t|}\]第二种方案:把子树剪成一个叶节点 $t$。
剪枝后训练损失是 $C(t)$,叶节点只有一个,因此:
\[\boxed{C_\alpha(t)=C(t)+\alpha}\]什么时候应该剪枝?
当剪枝后的综合损失更小时,即:
\[C_\alpha(t)<C_\alpha(T_t)\]把两个公式代进去:
\[C(t)+\alpha<C(T_t)+\alpha|T_t|\]把训练损失移动到左边,把复杂度惩罚移动到右边:
\[C(t)-C(T_t)<\alpha|T_t|-\alpha\]右边提取公因式 $\alpha$:
\[C(t)-C(T_t)<\alpha(|T_t|-1)\]假设此时 $\lvert T_t\rvert>1$,即原来的确有一棵可以剪掉的非平凡子树,两边除以 $\lvert T_t\rvert-1$:
\[\frac{C(t)-C(T_t)}{|T_t|-1}<\alpha\]观察左边,它正是 $g(t)$ 的定义。所以得到:
\[\boxed{g(t)<\alpha}\]这说明,当复杂度惩罚系数 $\alpha$ 超过 $g(t)$ 时,剪掉子树的综合损失会更小。
同样地:
\[\boxed{ \begin{cases} \alpha<g(t),&\text{保留子树更划算}\\ \alpha=g(t),&\text{保留和剪掉的综合损失相等}\\ \alpha>g(t),&\text{剪掉子树更划算} \end{cases}}\]因此,$g(t)$ 不只是一个“平均损失”,它还是这棵子树从值得保留变成值得剪掉的临界复杂度惩罚系数。
从代数上,也可以把两种方案的损失差写成:
\[\begin{aligned} C_\alpha(t)-C_\alpha(T_t) &=C(t)+\alpha-C(T_t)-\alpha|T_t|\\ &=[C(t)-C(T_t)]-\alpha(|T_t|-1)\\ &=(|T_t|-1)[g(t)-\alpha] \end{aligned}\]由于 $\lvert T_t\rvert-1>0$,损失差的正负完全由 $g(t)-\alpha$ 决定。这把前面的三种情况一次解释清楚了。
13.7 用具体数值验证临界值
继续使用我们刚才设定的例子:
\[C(t)=5,\quad C(T_t)=1,\quad |T_t|=3\]于是:
\[g(t)=\frac{5-1}{3-1}=2\]保留子树时:
\[C_\alpha(T_t)=1+3\alpha\]剪掉子树时:
\[C_\alpha(t)=5+\alpha\]我们改变 $\alpha$,看看结果:
| $\alpha$ | 保留子树:$1+3\alpha$ | 剪枝:$5+\alpha$ | 谁的综合损失更低 |
|---|---|---|---|
| 0 | 1 | 5 | 保留 |
| 1 | 4 | 6 | 保留 |
| 2 | 7 | 7 | 相等 |
| 3 | 10 | 8 | 剪枝 |
| 4 | 13 | 9 | 剪枝 |
这正好验证了:
- $\alpha<2$:保留子树。
- $\alpha=2$:两者打平。
- $\alpha>2$:剪掉子树。
所以 $g(t)=2$ 就是这棵子树的临界点。
13.8 为什么先找$g(t)$最小的节点
一棵完整决策树可能存在很多内部节点,它们分别对应不同的候选子树。
对每个内部节点计算 $g(t)$,假设得到:
| 候选子树 | 剪枝增加的训练损失 | 减少的叶节点数 | $g(t)$ |
|---|---|---|---|
| 以 $t_1$ 为根 | 8 | 2 | 4 |
| 以 $t_2$ 为根 | 3 | 3 | 1 |
| 以 $t_3$ 为根 | 6 | 2 | 3 |
先考虑从 $\alpha=0$ 开始,逐渐增大复杂度惩罚。
当 $0\le\alpha<1$ 时,这三个候选子树都还没到各自的剪枝临界值。
当 $\alpha=1$ 时,$t_2$ 首先达到临界值,剪掉它与保留它的综合损失相同;而 $t_1,t_3$ 仍然值得保留。
因此,$g(t)$ 最小的子树,是随着 $\alpha$ 增大最先失去保留价值的子树。
这就是最小代价复杂度剪枝中“优先剪最小 $g(t)$”的原因,通常也称为弱链接剪枝(weakest-link pruning)。
“弱链接”的意思不是“它必然预测得最差”,而是:与它节省的复杂度相比,它带来的额外训练拟合收益最不值得保留。
13.9 完整的CART剪枝算法:产生一系列由大到小的树
理解了临界值和最小 $g(t)$,完整过程就顺理成章。
第一步:生成一棵比较完整的CART树。
记作 $T_0$。它往往有较多分支,对训练数据拟合得比较好。
第二步:计算所有内部节点的 $g(t)$。
找出最小值:
\[\alpha_1=\min_{t\in\text{内部节点}}g(t)\]这个值是当前树的第一处剪枝临界值。
第三步:剪去对应的最弱子树。
将被选中的子树压缩成一个叶节点,得到更小的树 $T_1$。如果出现相同的最小临界值,需要按算法规则处理并列候选,形成相应的下一棵候选树。
第四步:在新的树上重新计算 $g(t)$。
因为之前剪掉的分支会改变某些祖先子树的结构和损失,不能简单地把第一次计算的所有分数一直用到底。
再次找到最小临界值,继续剪枝,得到 $T_2$。
不断重复:
\[\boxed{T_0\supset T_1\supset T_2\supset\cdots\supset T_m}\]这里的包含符号表示:后一棵树是前一棵树通过剪枝得到的子树结构。随着过程推进,树越来越简单,最终可能只剩根节点。
同时得到一系列临界惩罚系数:
\[0\le\alpha_1\le\alpha_2\le\cdots\le\alpha_m\]直观地看:随着我们越来越不能容忍复杂的树,最优的候选结构会在这些临界点发生变化。
第五步:利用验证数据或交叉验证选择真正合适的树。
这一步很重要,因为剪得越多并不意味着预测一定越好。
假设得到几棵候选树:
| 候选树 | 叶节点数 | 训练准确率 | 验证准确率 |
|---|---|---|---|
| $T_0$ | 20 | 99% | 82% |
| $T_1$ | 15 | 97% | 86% |
| $T_2$ | 8 | 94% | 90% |
| $T_3$ | 4 | 87% | 85% |
| $T_4$ | 1 | 60% | 59% |
本表是为了解释选择逻辑而设定的示意数据,并非真实实验结果。
可以看到,$T_0$ 训练成绩很高,但验证成绩不理想,可能过拟合;$T_4$ 太简单,可能欠拟合;$T_2$ 的验证表现最好。
所以最后选择 $T_2$,而不是最复杂的树,也不是最简单的树。
13.10 $g(t)$和信息增益有什么不同
之前也有一个叫 $g$ 的公式:
\[g(D,A)=H(D)-H(D\mid A)\]现在剪枝又出现:
\[g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\]虽然符号相同,但含义不同:
| 项目 | 信息增益 $g(D,A)$ | 剪枝参数 $g(t)$ |
|---|---|---|
| 发生在什么阶段 | 建树 | 剪枝 |
| 解决什么问题 | 哪个特征最值得拿来分组 | 哪棵子树最先不值得保留 |
| 衡量什么 | 划分后不确定性减少多少 | 每减少一个叶节点,训练损失增加多少 |
| 选择方向 | 越大越优先 | 越小越先到达剪枝临界点 |
可以把两个阶段记为:
- 建树时问:多加一个判断问题能带来多少好处?
- 剪枝时问:少保留一些判断问题会损失多少好处?
13.11 用生活比喻再理解一次
把决策树想象成一个公司的管理结构。某个部门下面有3个小组。保留3个小组,工作损失很低,但管理结构复杂;合并成1个小组,管理简单,但工作质量可能下降。
假设保留时的损失是1,合并后的损失是5。合并减少了2个小组,所以每减少一个小组的平均损失是:
\[\frac{5-1}{3-1}=2\]如果公司对“少一个小组”的简化收益赋予的价值超过2个损失单位,合并就是划算的。
映射回CART:
- 小组对应叶节点。
- 工作质量损失对应训练损失。
- 减少管理层级的收益对应复杂度惩罚。
- 每减少一个小组的平均代价对应 $g(t)$。
- 公司愿意为结构简化付出的权重对应 $\alpha$。
这就是CART代价复杂度剪枝的本质:用一个明确的损失函数,衡量“更简单”是否值得“训练拟合变差”这个代价。
十四、三种算法的比较和整套学习流程
14.1 ID3、C4.5、CART放在一起比较
| 项目 | ID3 | C4.5 | CART |
|---|---|---|---|
| 典型特征选择标准 | 信息增益最大 | 信息增益比(常结合增益筛选) | 分类用基尼指数最小;回归用平方误差最小 |
| 树形结构 | 可以多叉 | 可以多叉 | 二叉树 |
| 分类 | 可以 | 可以 | 可以 |
| 回归 | 经典ID3不用于此 | 经典C4.5主要用于分类 | 可以 |
| 核心特点 | 简洁的递归分类树算法 | 缓解信息增益对多取值特征的偏好 | 统一处理分类与回归,配有代价复杂度剪枝 |
记忆时可以先抓住最有辨识度的部分:
- ID3:信息增益。
- C4.5:信息增益比。
- CART分类:基尼指数。
- CART回归:平方误差。
- CART剪枝:代价复杂度与 $g(t)$。
但不要把“分裂标准”和“剪枝标准”混为一谈。建树时使用基尼指数,不代表剪枝公式中的 $C(T)$ 就一定是同一个基尼指数;剪枝会使用明确规定的训练损失及复杂度惩罚。
14.2 从零训练一棵树,实际经历什么
不管采用哪种经典算法,可以按下面的顺序理解整个学习过程。
阶段一:准备训练数据。
每条数据必须包含可用于预测的特征,以及已知的目标类别或数值。训练数据质量会影响最终模型质量。
阶段二:选择分裂指标。
分类ID3选择信息增益,C4.5选择信息增益比,CART分类选择加权基尼指数,CART回归选择平方误差之和。
阶段三:生成根节点。
根据当前全部训练样本,找出最好的第一个判断问题。
阶段四:递归地继续划分。
把数据送到相应子节点,在每个子节点重新计算最优划分,直到达到停止条件。
阶段五:控制复杂度。
可以在建树过程中限制最大深度、叶节点最少样本数,也可以在建树后剪掉不划算的子树。
阶段六:用独立数据评价。
训练集上的表现只是参考。应该使用验证集、交叉验证以及最终未参与调参的测试集,评价模型对新数据的预测能力。
14.3 决策树的优点与局限
决策树的优点:
- 容易解释:可以把预测过程直接写成一连串判断条件。
- 适用范围广:分类、回归都可以用相应的树模型处理。
- 非线性表达能力较强:可以通过多次划分形成复杂的判断区域。
- 通常不要求特征标准化:基于阈值和分组的划分,不像某些距离型模型那样依赖特征量纲。
决策树的局限:
- 容易过拟合:不限制复杂度时,可能记住训练集里的特殊细节。
- 对数据变化敏感:少量样本变化有时会导致不同的根节点或不同的树结构。
- 贪心建树并不保证全局最优:局部最好的切分,不一定组成整体最好的树。
- 预测常呈分段常数形式:标准回归树在每个叶节点预测一个固定数值,拟合平滑变化关系时可能需要很多叶节点。
真实项目中还要注意缺失值、类别不平衡、特征泄漏和数据偏差。一个看起来很准确的模型,如果训练数据不代表实际应用场景,也可能在部署后失效。
14.4 用一句话串起整篇
决策树像一个通过数据学会提问的人。
训练时,它不断寻找一个能够更有效地区分类别、或者减少数值预测误差的问题。每个问题把数据分成更小的小组,直到最终可以直接给出预测。随后,我们还要检查这棵树是否问了太多没有必要的问题,通过限制复杂度或剪枝让它对新数据更可靠。
建树负责让规则有用,剪枝负责让规则不过度复杂。
十五、公式速查与符号说明
最后把全文的关键公式集中放在一起。
15.1 分类中的信息熵
\[\boxed{H(D)=-\sum_{k=1}^{K}p_k\log_2p_k}\]回答:当前类别分布有多混乱?
在二分类中,两类各半时熵最大、全部属于同一类时熵为0。
15.2 条件熵
\[\boxed{H(D\mid A)=\sum_i\frac{|D_i|}{|D|}H(D_i)}\]回答:按特征 $A$ 分组以后,平均还剩多少混乱?
15.3 信息增益
\[\boxed{g(D,A)=H(D)-H(D\mid A)}\]回答:这个问题让混乱减少了多少?
ID3选择信息增益大的特征。
15.4 信息增益比
\[\boxed{g_R(D,A)=\frac{g(D,A)}{H_A(D)}}\]回答:考虑特征取值分布的分散程度后,这个问题的区分能力如何?
C4.5的特征选择核心涉及信息增益比。
15.5 基尼指数
\[\boxed{\operatorname{Gini}(D)=1-\sum_{k=1}^{K}p_k^2}\]二分类时:
\[\boxed{\operatorname{Gini}(p)=2p(1-p)}\]回答:这一组样本的类别有多混杂?
CART分类树选择使划分后加权基尼指数最小的分法。
15.6 回归树的平方误差
\[\boxed{\operatorname{SSE}=\sum_i(y_i-\hat y_i)^2}\]回答:数值预测和真实值总共差了多少?
标准最小二乘回归树的叶节点输出该组训练目标值的平均数。
15.7 代价复杂度损失
\[\boxed{C_\alpha(T)=C(T)+\alpha|T|}\]回答:预测误差与树的复杂度加在一起,总成本是多少?
15.8 CART剪枝的临界参数
\[\boxed{g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}}\]回答:把一段子树压缩成一个叶节点时,每减少一个叶节点要增加多少训练损失?
更进一步,$g(t)$ 是保留与剪掉这段子树综合损失相等时的临界 $\alpha$:
\[\boxed{ \begin{aligned} \alpha<g(t)&:\ \text{保留更优}\\ \alpha=g(t)&:\ \text{两者相等}\\ \alpha>g(t)&:\ \text{剪枝更优} \end{aligned}}\]15.9 全文常见符号
| 符号 | 含义 |
|---|---|
| $D$ | 训练数据集 |
| $\lvert D\rvert$ | 训练样本个数 |
| $A$ | 一个候选特征 |
| $D_i$ | 按某个特征分出的第 $i$ 个子集 |
| $p_k$ | 第 $k$ 类样本所占比例 |
| $H(D)$ | 类别的信息熵 |
| $H(D\mid A)$ | 按特征 $A$ 分组后的条件熵 |
| $g(D,A)$ | 信息增益 |
| $g_R(D,A)$ | 信息增益比 |
| $T$ | 一整棵决策树 |
| $\lvert T\rvert$ | 整棵树的叶节点数量 |
| $t$ | 某个内部节点,也可表示剪枝后把它作为叶节点 |
| $T_t$ | 以节点 $t$ 为根的子树 |
| $C(t)$ | 把 $t$ 作为叶节点时的训练损失 |
| $C(T_t)$ | 保留整棵子树 $T_t$ 时的训练损失 |
| $\alpha$ | 树的复杂度惩罚系数 |
| $g(t)$ | 子树的有效复杂度参数、剪枝临界值 |