决策树（DecisionTree）原理、公式与实战
决策树（Decision Tree）是机器学习中最直观、可解释性最强且应用最广泛的算法之一，它模拟人类做决策的过程——通过一系列”是与否”的判断，逐步缩小范围，最终得出结论。集成算法如：RF、GBDT、Xgboost、LightGBM都是以决策树为基础构建的。
决策树本质上是用一系列超平面对特征空间进行递归划分的方法。每一次分裂，都把当前空间一分为二，最终每个叶子节点都对应特征空间中一个不相交的区域。预测时，样本从根节点出发，根据每一维特征的取值不断向下走，最终落入某个叶子节点，这个叶子节点的类别（或数值）就是模型给出的预测结果。用一句话概括：决策树是从根节点到叶子节点的一条决策路径，所有训练数据最终都会落入某个叶子节点中。
决策树的三个组成部分：
- 根节点：树的起点，也是第一个用于分裂的特征
- 非叶子节点：代表一次特征判断，是决策过程的中间步骤
- 叶子节点：决策树的终点，给出最终的分类结果或预测值
那根节点该选哪个特征？下一层节点又该选哪个特征？ 答案是：通过量化每个特征带来的”纯度提升”（信息增益、信息增益率或基尼系数），选出提升最大的那个特征作为分裂依据。
几个关键认识：
- 决策树既能做分类，也能做回归。用于分类的叫分类树，预测的是离散标签；用于回归的叫回归树，预测的是连续数值。
- 决策树是一种基于概率分析、以树形结构呈现的有监督学习算法，每个叶子节点代表一种类别（分类树）或一个预测值（回归树）。
- 单棵决策树很容易过拟合，因此实际工程中很少直接使用单棵决策树做预测，而是用多棵树组成集成算法（如随机森林、GBDT、XGBoost）来降低方差、提升泛化能力。
- 预测时一个样本只会进入一个叶子节点，每个叶子节点可能包含多个训练样本，我们用这些样本的统计结果（如：分类树时的类别频率、 回归树时的均值）来决定该叶子的预测输出。
前置知识：信息论基础
信息量
设想两个事件：
- 事件 A：巴西队获得世界杯冠军
- 事件 B：中国队获得世界杯冠军
直觉上，事件 B 一旦发生，带给我们的”信息量”要远大于事件 A。原因很简单：事件 A 发生的概率本来就大，事件 B 发生的概率很小。越不可能发生的事件一旦发生，携带的信息量就越大；越大概率发生的事件，携带的信息量反而越小。 也就是说，信息量与事件发生的概率成反比关系。
信息量的数学定义为：
$$I(x) = -\log p(x)$$
其中 $p(x)$ 是事件 $x$ 发生的概率，取值范围是 $[0,1]$。当以 2 为底取对数时，信息量的单位是比特（bit）。可以看出，$p(x)$ 越小，$I(x)$ 越大，符合我们的直觉。
信息熵（Entropy）
信息量描述的是单个事件，而信息熵是所有可能事件信息量的期望，用来衡量整个随机变量的不确定性：
$$H(X) = -\sum_{i=1}^{n} p(x_i) \log p(x_i)$$
信息熵的性质：
- 熵越大，不确定性越大：随机变量各种取值越接近等概率分布，熵越大；当所有取值等概率出现时，熵达到最大值。
- 熵越小，纯度越高、越稳定：某些取值概率很大、某些取值概率很小时，随机变量的分布越”确定”，熵越小。
- 随机变量的取值个数越多，可能的状态数越多，熵通常也就越大，系统的混乱程度越高。
对于只有两种取值（如是/否）的二分类情形，设正例概率为 $p$：
$$H(p) = -p\log_2 p - (1-p)\log_2(1-p)$$
- 当 $p=0$ 或 $p=1$ 时，$H(p)=0$，此时随机变量完全没有不确定性（结果已经确定）；
- 当 $p=0.5$ 时，$H(p)=1$，达到最大值，此时不确定性最大。
推广到一般情形：当类别数为 $n$，且每个类别的概率均为 $1/n$（均匀分布）时，熵取得最大值，此时不确定性最强。
联合熵
联合熵（Joint Entropy）用来度量一对随机变量 $(X,Y)$ 组成的联合分布系统的不确定度。设联合分布为 $p(x,y)$，则：
$$H(X,Y) = -\sum_{x}\sum_{y} p(x,y)\log p(x,y)$$
联合熵描述的是这一对随机变量平均所需要的信息量。
条件熵
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下，随机变量 $Y$ 的不确定性，即给定 $X$ 的每一个取值后，$Y$ 的信息熵的加权和：
$$H(Y|X) = \sum_{x} p(x)\, H(Y|X=x)$$
条件熵还有一种等价表达：
$$H(Y|X) = H(X,Y) - H(X)$$
即：条件熵 = 联合熵 − 单独一个变量的信息熵。这个式子的直观含义是：$(X,Y)$ 一起发生所包含的总信息量，减去 $X$ 单独发生所包含的信息量，剩下的就是”在已知 $X$ 的前提下，$Y$ 新带来的信息量”，这正是条件熵的本质。
理解了信息熵和条件熵，我们就可以定义决策树选择特征的核心指标——信息增益了。
决策树的构建流程
一棵决策树的生成主要包含三个环节：
- 特征选择：从众多特征中选出一个作为当前节点的分裂标准。评估标准不同，衍生出不同的决策树算法（ID3、C4.5、CART）。
- 决策树生成：根据选定的特征评估标准，自上而下递归地生成子节点，直到数据集不可再分则停止生长。递归是理解树结构生成过程最直接的方式。
- 剪枝：决策树天然容易过拟合，通常需要通过剪枝来缩小树的规模，缓解过拟合问题。
连续特征的处理
无论是分类树还是回归树，遇到连续型特征时都需要先做**离散化（二分）**处理，通用做法是：
- 将该连续特征的所有取值从小到大排序；
- 取相邻两个取值的平均数作为候选切分点（若有 $m$ 个不同取值，则产生 $m-1$ 个候选切分点）；
- 遍历所有候选切分点，分别以”大于切分点”和”小于等于切分点”将样本一分为二，计算信息增益（或基尼系数下降量）；
- 选择使信息增益最大（或基尼系数最小）的切分点作为该特征的最优分裂点。
决策树的损失函数
决策树整体的损失函数通常用基尼系数的加权平均来表示：
$$C(T) = \sum_{t=1}^{|T|} \frac{N_t}{N} H_t(T)$$
- $|T|$：叶子节点的个数；
- $t$：第 $t$ 个叶子节点；
- $N_t$：第 $t$ 个叶子节点的样本数；
- $N$：所有样本总数；
- $H_t(T)$：第 $t$ 个叶子节点的纯度指标（信息熵 / Gini 系数 / 错误率均可）。
考虑到树的复杂度会影响过拟合风险，实践中常见的是加入正则项的损失函数：
$$C_\alpha(T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha|T|$$
其中 $\alpha \geq 0$ 是控制模型复杂度的参数，$\alpha$ 越大，惩罚力度越强，最终得到的树越简单。这个带正则项的损失函数正是后剪枝算法判断是否剪枝的理论依据。
决策树是停止生长的条件
递归过程必须有明确的终止条件，否则将无限分裂下去：
- 一个节点中所有样本都属于同一类别（注意：如果只用这一条作为唯一停止条件，容易导致树的节点数过多，造成过拟合）；
- 当前节点样本数小于某个阈值，且迭代次数达到给定值时，停止构建，此时用该节点中出现频次最高的类别 $\max(p(i))$ 作为该节点的预测类别；
- 没有特征可用于继续划分该节点的样本，此时该节点的类别取样本数最多的那一类；
- 没有样本能满足剩余特征的取值条件，同样取样本数最多的类别作为该节点类别。
经典决策树：ID3、C4.5、CART
不同种类的决策树算法，核心区别仅仅在于选择分裂特征所使用的量化标准不同：
| 算法 | 分裂标准 |
|---|---|
| ID3 | 信息增益（Information Gain） |
| C4.5 | 信息增益率（Gain Ratio） |
| CART | 基尼系数（Gini Index） |
ID3：信息增益
信息增益衡量的是：使用特征 $A$ 对数据集划分后，类别 $Y$ 的不确定性减少了多少。也就是选择不同特征 $A$ 作为分裂节点时，标签 $Y$ 的熵值发生了多大的变化。每次迭代都选择信息增益最大的特征作为当前节点的分裂属性。
信息增益的计算公式为：
$$\text{Gain}(D, A) = H(D) - H(D|A)$$
其中：
- $H(D)$ 是数据集 $D$（原始，未分裂）的信息熵；
- $H(D|A)$ 是以特征 $A$ 划分之后的条件熵，也称为按特征 $A$ 分裂后的加权平均熵（决策树的损失函数之一），公式为：
$$H(D|A) = \sum_{v} \frac{|D_v|}{|D|} H(D_v)$$
即根据特征 $A$ 的每个取值 $v$ 把数据集切分成若干子集 $D_v$，每个子集按其样本占比加权，求熵的加权平均。
信息增益越大，说明用该特征分裂后损失的不确定性（获得的纯度提升）越大，该特征就越应该排在决策树的上层。分类树中，每个叶子节点最终的预测类别取该叶子节点中样本数最多的类别（众数）。
ID3 的缺陷
信息增益天然偏向于取值较多的特征。极端情况下，如果给数据集加一列唯一 ID（1,2,3,4,5…），以 ID 作为分裂特征后，每个子节点都只有一个样本，熵全部为 0，信息增益达到理论最大值——但 ID 显然不是一个有意义的特征，这种分裂对模型毫无泛化能力。为了解决这个问题，C4.5 算法引入了信息增益率。
C4.5：信息增益率
C4.5 在 ID3 的基础上做了改进，把信息增益除以特征本身的”固有值”（自身的熵），相当于对取值过多的特征施加一个惩罚项：
$$\text{GainRatio}(D, A) = \frac{\text{Gain}(D, A)}{\text{IV}(A)}$$
其中 $\text{IV}(A)$（Intrinsic Value，属性 $A$ 的固有值/自身熵）定义为：
$$\text{IV}(A) = -\sum_{v} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}$$
属性 $A$ 的取值可能性越多（即分支数越多），$\text{IV}(A)$ 通常也越大，从而对信息增益产生更强的抑制作用。仍以 ID 为例：虽然用 ID 分裂带来的信息增益很大，但除以 ID 自身极大的熵值之后，信息增益率会大幅下降，从而避免模型偏向这种无意义的高基数特征。
C4.5 在特征选择上使用信息增益率最大的属性作为分裂点。除此之外，C4.5 相较 ID3 还有三大优势：
- 在树的构造过程中会进行剪枝优化；
- 能够自动完成连续属性的离散化处理；
- 能够自动处理缺失值。
C4.5 如何处理缺失值
C4.5 的缺失值处理分两个子问题：
（1）属性上存在缺失值，如何选择分裂特征？
思路是：只用没有缺失值的那部分样本子集 $D'$ 计算信息增益率，再按 $D'$ 占整体样本 $D$ 的比例做加权折算。
举例：某数据集共 7 个样本，其中”温度”这一特征有 1 个样本缺失，剩下 6 个样本构成 $D'$。假设按温度（高/中/低）划分后计算出：
$$\text{Gain}(D', \text{温度}) = \text{Ent}(D') - 0.792 = 1.0 - 0.792 = 0.208$$
温度自身的属性熵为 1.459，因此：
$$\text{Gain\_ratio}(D', \text{温度}) = 0.208 / 1.459 = 0.1426$$
由于 $D'$ 只有 6 个样本，$D$ 有 7 个样本，缺失比例意味着 $D'$ 的权重为 $6/7$，因此最终折算到全体样本 $D$ 上的信息增益率为：
$$\text{Gain\_ratio}(D, \text{温度}) = \frac{6}{7} \times 0.1426 = 0.122$$
这样，即便某个属性存在部分样本缺失，依然可以计算出信息增益率，用于属性选择。
（2）已经确定了分裂属性，但某些样本在该属性上恰好缺失，该如何分配这些样本？
处理方式是：把该样本同时划分到所有分支中，但赋予不同的权重（权重等于每个分支中已有样本数占总样本数的比例）。这样，如果后续还要继续往下分裂，计算条件熵时就需要把该样本自身的权重也考虑进去。这部分内容更严谨的推导可参考《机器学习》（西瓜书）决策树一章。
CART：基尼系数
CART（Classification And Regression Tree，分类回归树）使用基尼系数作为衡量数据纯度的指标（而不是熵）。CART 的两个重要特点：
- 既能做分类，又能做回归（分类用基尼系数，回归用均方误差）；
- 只能构建二叉树，每次分裂只产生两个子节点。
基尼系数的定义（$k$ 分类问题）：
$$\text{Gini}(D) = \sum_{i=1}^{k} p_i (1 - p_i) = 1 - \sum_{i=1}^{k} p_i^2$$
基尼系数衡量的是”从数据集中随机抽取两个样本，其类别标签不一致的概率”。概率 $p$ 越接近 1（数据越纯），基尼系数越接近 0；数据越混乱，基尼系数越接近其最大值。
按特征 $A$ 分裂后的基尼增益（分裂前后基尼系数的下降幅度）定义类似于信息增益：
$$\text{Gini\_Gain}(D, A) = \text{Gini}(D) - \sum_{v} \frac{|D_v|}{|D|} \text{Gini}(D_v)$$
CART 算法在每次分裂时选择使基尼增益最大（即分裂后基尼系数下降最多）的特征和切分点作为当前的分裂依据。
三个纯度指标（信息熵、Gini 系数、错误率）的共同特点是：值越大表示数据越”不纯”，值越小表示越”纯”。三者可以相互替代作为决策树的分裂评价标准，只是计算方式和对极端分布的敏感度略有不同。
ID3、C4.5、CART 树对比
| 对比维度 | ID3 | C4.5 | CART |
|---|---|---|---|
| 分裂标准 | 信息增益 | 信息增益率 | 基尼系数 |
| 树的结构 | 不一定是二叉树 | 不一定是二叉树 | 一定是二叉树 |
| 是否支持回归 | 否 | 否 | 支持 |
| 连续值处理 | 不支持 | 支持 | 支持 |
| 缺失值处理 | 不支持 | 自动处理 | 支持 |
| 剪枝 | 不涉及 | 支持 | 支持（后剪枝为主） |
| 对高基数特征的偏好 | 严重偏向 | 已缓解 | 较均衡 |
| 适用规模 | 小规模数据集 | 小规模数据集 | 应用最广泛 |
几点重要结论：
- ID3 和 C4.5 都只适合在小规模数据集上使用，且都属于单变量决策树（每次只用一个特征分裂）；
- 当某个特征的取值比较多时，优先考虑 C4.5，因为 ID3 在这种场景下效果会明显变差；
- 决策树分类算法整体上更适合小数据量场景（数据能放进内存）；
- CART 是三种算法中工程实践里最常用的一种，因为它同时支持分类和回归，并且天然支持连续值和剪枝；
- 三种算法的本质区别只在于评价当前树分裂效果的标准不同：ID3 用信息增益、C4.5 用信息增益率、CART 用基尼系数；
- CART 构建的一定是二叉树，而 ID3 和 C4.5 构建的可能是多叉树。
决策树的剪枝：防止过拟合
决策树如果不加限制地生长，会对训练集拟合得”面面俱到”，但在测试集上表现很差，也就是过拟合。剪枝的目的正是缩小树的规模、缓解过拟合，主要分为两种策略。
预剪枝（Pre-Pruning，工业界常用）
预剪枝是在建树过程中就设置规则，提前阻止树的过度生长：
- 限制树的最大深度：树深超过阈值则该节点不再分裂；
- 限制叶子节点的最少样本数：若某节点分裂后子节点的样本数小于阈值（如总样本的 1%），则不再分裂；
- 限制叶子节点的最大个数：叶子节点总数超过阈值则停止分裂；
- 限制信息增益率或基尼系数的阈值：低于给定阈值则不再分裂（此法实践中不太常用，因为阈值不易设定，且局部增益小不代表后续分裂无价值）。
预剪枝的优点是计算开销小、训练速度快；缺点是可能存在”局部最优陷阱”——某次分裂当下增益不大，但继续往下分裂却可能带来显著提升，预剪枝会提前掐断这种可能性，导致欠拟合风险。
后剪枝（Post-Pruning）
后剪枝是先完整地建好一棵决策树，然后自下而上地对每个非叶子节点进行考察，判断是否将其”剪掉”（即把该子树替换为一个叶子节点）。
损失函数公式：
$$C_{\alpha}(T) = C(T) + \alpha \cdot \vert{}T_{leaf}\vert{}$$
变量标注与说明：
$C(T)$：损失函数
$$\text{损失函数} = \text{叶子节点样本数} \times \text{gini系数 \quad 或 \quad 叶子节点样本数} \times \text{熵值}$$
$\alpha$：系数（超参数/惩罚因子）
$\vert{}T_{leaf}\vert{}$：叶子节点个数
$C_\alpha(T)$：分别计算某节点剪枝前（保留子树）和剪枝后（该节点变为叶子）的损失函数值
通过最小化损失函数 $C_{\alpha}(T)$ 来确定是否剪枝。在节点分裂前计算 $C_{\alpha}(T)$ 的值，分裂后再计算一次，如果分裂后的值大于分裂前的值，就可以进行剪枝（即放弃分裂，保留父节点作为叶节点）。
后剪枝是指让决策树先充分生长（直到无法再分或达到止步条件），然后自底向上评估子树。如果将某个子树折叠回单个叶子节点能降低整体损失，就将其剪掉。
公式的含义与权衡（Trade-off）：
$$C_{\alpha}(T) = \underbrace{C(T)}_{\text{拟合误差}} + \underbrace{\alpha \cdot \vert{}T_{leaf}\vert{}}_{\text{模型复杂度惩罚}}$$
- $C(T)$：衡量树对训练数据的拟合程度。树越深、分裂越细，数据不纯度（Gini系数或熵）越低，$C(T)$ 越小。
- $\alpha \cdot \vert{}T_{leaf}\vert{}$：控制模型的复杂度。叶子节点越少，树越简单，泛化能力越强。
- $\alpha$ 的作用：$\alpha$ 是调优参数。若 $\alpha = 0$，表示不考虑模型复杂度，只追求数据拟合；$\alpha$ 越大，对节点过多的惩罚力度越重，倾向于生成更小、更平滑的树。
决策逻辑：
决策树通过计算“剪枝前”与“剪枝后（或分裂前/后）”的总损失值 $C_{\alpha}(T)$。如果复杂树的损失反而大于简单树（说明增加分支带来的拟合收益掩盖不了复杂度增加带来的惩罚），就选择剪枝，以防止过拟合。
后剪枝通常比预剪枝欠拟合风险更低、泛化性能更好，但计算开销也更大，因为需要先生成完整的树再自底向上遍历评估。
CART 算法常用的后剪枝方式是：先生成完整的决策树，再枚举所有可能的剪枝方案，用交叉验证评估每种剪枝方案在验证集上的表现，选择泛化能力最好的那一种作为最终模型。
决策树做预测
决策树的预测的过程其实很简单：一个新样本进来，从根节点开始，按照每个内部节点的判断条件，一步一步往下走，走到哪个分支完全由这个样本自身的特征值决定。最终，这个样本只会落到一个叶子节点上，不会同时属于两个叶子——树结构本身保证了这一点，因为每次分裂产生的子区域是互不重叠的。
关键在于：一个叶子节点里往往不止一个训练样本，训练阶段有一批数据最终都落进了同一个叶子。预测输出就是靠这批样本的统计结果得出来的：
- 分类树：看这个叶子节点里各类别出现的频率，取频率最高（也就是样本数最多）的那个类别作为预测结果，本质上是投票，少数服从多数；
- 回归树：直接取这个叶子节点里所有样本目标值的均值作为预测结果。
所以严格来说，决策树的”学习”过程，就是想办法把训练样本切分成一个个尽可能”纯”的小组（叶子节点），预测时只是把新样本对号入座，找到它该待的那个小组，然后把这个小组早就算好的统计值报出来。
这里有个容易被忽略但挺重要的点：决策树不适合用梯度下降来求解。原因也不复杂——树的分裂是一次次离散的”是否满足某个条件”的判断，输出结果随着分裂点、分裂特征的变化是阶跃式的、不连续的，压根没法对它求导。梯度下降依赖的是损失函数对参数连续可导，而决策树的结构本身就是一堆分段常数拼起来的，中间全是断层，谈”梯度”没有意义。这也是为什么决策树的构建靠的是贪心搜索（每一步找当前最优的分裂特征和分裂点），而不是像神经网络那样靠反向传播一点点调参数。
回归树
前面讨论的都是分类树：用信息增益、信息增益率、基尼系数来评价分裂效果，本质上都是基于概率进行判断，叶子节点的预测值取该节点中样本数最多的类别（众数）。
回归树则用于预测连续数值。回归树叶子节点的预测值，取该叶子节点内所有样本目标值的均值：
由于目标值是连续的，回归树通常采用 MSE（均方误差） 作为评价分裂效果的指标，而不是信息熵或基尼系数。实践中，回归树一般只使用 CART 算法构建（二叉树)。
回归树的分裂原理
回归树采用启发式的方法进行分裂：假设有 $n$ 个特征，每个特征 $j$ 有若干个可能的取值，遍历所有特征及其所有可能的切分点 $s$，尝试用 $(j,s)$ 将当前空间一分为二，计算划分后的损失，选择使损失函数最小的 $(j,s)$ 作为当前节点的分裂依据。
设输入空间被最终划分为 $M$ 个区域 $R_1, R_2, \ldots, R_M$，每个区域的输出值（预测值）取该区域内所有样本目标值 $y$ 的均值：
$$c_m = \text{avg}(y_i \mid x_i \in R_m)$$
损失函数采用平方损失：
$$L = \sum_{x_i \in R_m} (y_i - c_m)^2$$
对于任意一个候选切分变量 $j$ 和切分点 $s$，将空间划分为两个区域：
$$R_1(j,s) = \{x \mid x_j \le s\}, \quad R_2(j,s) = \{x \mid x_j > s\}$$
目标函数是求使两个区域平方损失之和最小的 $(j,s)$：
$$\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]$$
这个过程递归地进行下去，直到满足停止条件（如区域内样本数过少、达到最大深度、或损失下降不再显著），最终生成的树就是最小二乘回归树。
回归树与线性回归
回归树和线性回归都能处理连续值预测问题，但二者的建模方式截然不同：
- 线性回归假设特征与目标之间存在（近似）线性关系，用一条直线（或超平面）去拟合整体数据分布，模型形式简洁、可解释性强，但难以捕捉非线性、分段的模式；
- 回归树通过不断切分特征空间，用分段常数（每个区域内的均值）去逼近真实的函数关系，天然能够拟合非线性、非单调的模式，但预测结果呈”阶梯状”，在区域边界处会有跳变，不如线性回归平滑。
在实践中，如果数据的真实关系接近线性，线性回归通常表现更好、更稳定；如果数据存在复杂的非线性或交互效应，回归树（及其集成版本如随机森林、GBDT）往往更有优势。
分类树 vs 回归树
| 对比维度 | 分类树 | 回归树 |
|---|---|---|
| 目标变量 | 离散变量（类别） | 连续变量（数值） |
| 评价指标 | 信息增益 / 信息增益率 / 基尼系数 | MSE（均方误差） |
| 叶子节点预测值（得分函数） | 该节点样本的众数（出现次数最多的类别） | 该节点样本目标值的均值 |
| 损失函数 | 同一层所有分支基尼系数（或熵）的加权平均 | 同一层所有分支的平方差损失之和 |
| 分裂准则 | 比较分裂前后基尼系数（或熵）的下降量，下降越多越优先选择 | 使用最小方差作为分裂规则，只能生成二叉树 |
| 剪枝方式（以 CART 为例） | 后剪枝：生成完整树后，枚举所有可能的剪枝方案，用交叉验证选择泛化能力最好的方案 | 同左 |
决策树构建实例
用信息增益构建分类树
下面通过经典的”打篮球”数据集，完整演示 ID3 算法（信息增益）构建分类树的过程。
| outlook | temperature | humidity | windy | play |
|---|---|---|---|---|
| sunny | hot | high | FALSE | no |
| sunny | hot | high | TRUE | no |
| overcast | hot | high | FALSE | yes |
| rainy | mild | high | FALSE | yes |
| rainy | cool | normal | FALSE | yes |
| rainy | cool | normal | TRUE | no |
| overcast | cool | normal | TRUE | yes |
| sunny | mild | high | FALSE | no |
| sunny | cool | normal | FALSE | yes |
| rainy | mild | normal | FALSE | yes |
| sunny | mild | normal | TRUE | yes |
| overcast | mild | high | TRUE | yes |
| overcast | hot | normal | FALSE | yes |
| rainy | mild | high | TRUE | no |
数据集：14 天的天气与是否打球的记录
特征：4 种环境变量（outlook 天气、temperature 温度、humidity 湿度、windy 是否有风）
标签：是否打球（Yes / No）
目标：构造一棵决策树
setp1：计算未分裂时的整体熵值：
14 天中有 9 天打球、5 天不打球：
$$H(D) = -\frac{9}{14}\log_2\frac{9}{14} - \frac{5}{14}\log_2\frac{5}{14} = 0.940$$
setp2：计算以 outlook（天气）为分裂特征时的条件熵：
outlook 有三个取值：sunny、overcast、rainy。
- outlook = sunny 时（5 个样本，2 打球 3 不打球）：
$$H(\text{sunny}) = -\frac{2}{5}\log_2\frac{2}{5} - \frac{3}{5}\log_2\frac{3}{5} = 0.971$$
- outlook = overcast 时（4 个样本全部打球，纯度最高）：$H(\text{overcast}) = 0$
- outlook = rainy 时（5 个样本）：$H(\text{rainy}) = 0.971$
三种取值在数据集中出现的概率分别为 $5/14, 4/14, 5/14$。
Setp3：计算按 outlook 分裂后的加权平均熵：
$$H(D|\text{outlook}) = \frac{5}{14}\times 0.971 + \frac{4}{14}\times 0 + \frac{5}{14}\times 0.971 = 0.693$$
setp4：计算信息增益：
$$\text{Gain}(\text{outlook}) = H(D) - H(D|\text{outlook}) = 0.940 - 0.693 = 0.247$$
即系统的熵值从原始的 0.940 下降到了 0.693，信息增益为 0.247。
用同样的方法，可以计算出其余三个特征的信息增益：
| 特征 | 信息增益 |
|---|---|
| outlook | 0.247 |
| temperature | 0.029 |
| humidity | 0.152 |
| windy | 0.048 |
outlook 的信息增益最大，因此选择 outlook 作为根节点。之后在每个子节点（sunny / overcast / rainy 分支）内，用剩余的特征重复上述计算过程，递归选出二级节点、三级节点，直到满足停止条件。
ID3 的问题在上述例子中的体现：
如果给这份数据再加一列 ID（取值为 1、2、3……14，每个样本各不相同），用 ID 作为分裂特征时，每个分支只有一个样本，熵全部为 0，信息增益达到最大值 0.940——远超 outlook 的 0.247。但显然 ID 对预测是否打球毫无意义，这正是前文提到的 ID3 偏向高基数特征的缺陷，也是 C4.5 引入信息增益率的动机所在。
构建最小二乘回归树
训练数据见下表，目标是得到一棵最小二乘回归树。
| $x$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $y$ | 5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 | 8.90 | 8.70 | 9.00 | 9.05 |
选择最优切分变量 $j$（也就是使用哪个特征进行切分）与最优切分点。在本数据集中，只有一个变量，因此最优切分变量自然是 $x$。我们假设 9 个切分点分别为：
$$[1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5]$$
损失函数定义为平方损失函数 $Loss(y, f(x)) = (f(x) - y)^2$，将上述 9 个切分点依次代入下面的公式，其中 $c_m = \text{ave}(y_i \mid x_i \in R_m)$：
$$\min_{j, s} \left[ \min_{c_1} \sum_{x_i \in R_1(j, s)} Loss(y_i, c_1) + \min_{c_2} \sum_{x_i \in R_2(j, s)} Loss(y_i, c_2) \right]$$
当取 $s = 1.5$ 时，$R_1 = \{1\}$，$R_2 = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$，这两个区域的输出值分别为：
$$c_1 = 5.56, \quad c_2 = (5.70 + 5.91 + 6.40 + 6.80 + 7.05 + 8.90 + 8.70 + 9.00 + 9.05) / 9 = 7.50$$
同理等于 2.5, 3.5, …, 9.5 时，得下表：
| $s$ | 1.5 | 2.5 | 3.5 | 4.5 | 5.5 | 6.5 | 7.5 | 8.5 | 9.5 |
|---|---|---|---|---|---|---|---|---|---|
| $c_1$ | 5.56 | 5.63 | 5.72 | 5.89 | 6.07 | 6.24 | 6.62 | 6.88 | 7.11 |
| $c_2$ | 7.50 | 7.73 | 7.99 | 8.25 | 8.54 | 8.91 | 8.92 | 9.03 | 9.05 |
当 $s = 1.5$ 时把 $c_1, c_2$ 的值代入到目标函数：
$$g(1.5) = (5.56 - 5.56)^2 + [(5.70 - 7.50)^2 + (5.91 - 7.50)^2 + (6.40 - 7.50)^2 + (6.80 - 7.50)^2 + (7.05 - 7.50)^2 + (8.90 - 7.50)^2 + (8.70 - 7.50)^2 + (9.00 - 7.50)^2 + (9.05 - 7.50)^2] = 0 + 15.72 = 15.72$$
注：
后面几个数 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05 分别减去平均数 7.50 再平方，得：3.244, 2.532, 1.212, 0.492, 0.204, 1.957, 1.437, 2.247, 2.399，再求和就是 15.72；前面的数 5.56 的均值也是 5.56，所以用同样的方法计算得到 0；所以最终就是 $0 + 15.72 = 15.72$。
同理，可获得下表：
| $s$ | 1.5 | 2.5 | 3.5 | 4.5 | 5.5 | 6.5 | 7.5 | 8.5 | 9.5 |
|---|---|---|---|---|---|---|---|---|---|
| $m(s)$ | 15.72 | 12.07 | 8.36 | 5.78 | 3.91 | 1.93 | 8.01 | 11.73 | 15.74 |
显然取 $s = 6.5$ 时 $m(s)$ 最小，因此，第一个划分变量 $j$ 为 $x$，$s = 6.5$。
用选定的 $(j, s)$ 划分区域，并决定输出值，两个区域分别是：
$R_1 = \{1, 2, 3, 4, 5, 6\}$，$R_2 = \{7, 8, 9, 10\}$，输出值 $c_m = \text{ave}(y_i \mid x_i \in R_m)$，$c_1 = 6.24$，$c_2 = 8.91$。
继续上面步骤对 $R_1$ 继续进行划分：
| $x$ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| $y$ | 5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 |
取切分点 $[1.5, 2.5, 3.5, 4.5, 5.5]$，则各区域的输出值如下表：
| $s$ | 1.5 | 2.5 | 3.5 | 4.5 | 5.5 |
|---|---|---|---|---|---|
| $c_1$ | 5.56 | 5.63 | 5.72 | 5.89 | 6.07 |
| $c_2$ | 6.37 | 6.54 | 6.75 | 6.93 | 7.05 |
计算 $g(s)$：
| $s$ | 1.5 | 2.5 | 3.5 | 4.5 | 5.5 |
|---|---|---|---|---|---|
| $m(s)$ | 1.3087 | 0.7540 | 0.2771 | 0.4368 | 1.0644 |
$s = 3.5$ 时 $g(s)$ 最小。
同样的方法，之后的过程不再赘述。
假设在生成 3 个区域之后停止划分，那么最终生成的回归树形式如下：
$$T(x) = \begin{cases} 5.72 & x \le 3.5 \\ 6.75 & 3.5 < x \le 6.5 \\ 8.91 & x > 6.5 \end{cases}$$
决策树总结
- 决策树是用超平面递归划分特征空间的有监督学习算法，既能分类也能回归；
- 判断分裂效果的核心是信息论中的信息熵、条件熵，由此衍生出**信息增益（ID3）→ 信息增益率（C4.5）→ 基尼系数（CART）**三代分裂标准，一代比一代更成熟；
- 决策树天然容易过拟合，必须依靠预剪枝（建树过程中限制深度/样本数/节点数）或后剪枝（建完整树后自底向上评估是否剪枝）来控制模型复杂度；
- 连续特征需要先离散化处理，缺失值可以通过样本权重折算的方式处理（C4.5 的经典做法）；
- 回归树用 MSE 作为分裂评价指标，叶子节点预测值取均值，本质是用分段常数函数逼近真实的回归关系；
- 实际工程中，CART 是应用最广泛的决策树算法，也是随机森林、GBDT、XGBoost 等集成模型的基础组件——吃透单棵决策树的原理，是理解这些更强大模型的第一步。
优点
可解释性强
决策过程天然符合人的思考方式，业务人员可以直接理解模型原因。
可以处理非线性关系
线性模型y = wx+b只能学习线性边界，而决策树可以形成复杂非线性边界。
不需要特征归一化
决策树只关心x < threshold，不关心具体数值尺度。
缺点
容易过拟合
如果树不断生长，模型可能记住训练数据，而不是学习规律。
对数据变化敏感
训练数据稍微变化，树结构可能完全改变。
单颗决策树泛化能力有限
实际工业中通常不会直接使用单棵树，一般会使用基于决策树的集成算法。如：RF、GBDT、Xgboost、LightGBM
