机器学习：8.决策树

决策树

一.树的定义

二.信息熵

1. 决策树模型怎么玩

• 决策树的预测阶段，每进来一个样本，根据判断节点实际情况，对对应的特征进行判断，直到走到标记节点。

• 如何构建决策树

• 按顺序对每一个特征进行判断(低效)
• 每个判断节点都尽可能让一半进入A分支，另一半进入B分支(高效)

2. 信息熵定义

(1).熵的定义

在信息论与概率统计中，熵(entropy)是表示随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，其概率分布为

$$P(X=x_i)=p_i,i=1,2,\dots ,n$$

则随机变量X的熵定义为

$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$

熵越大，则随机变量的不确定性越大。其中$0\le H(P)\le \log n$

注：均匀分布的时候熵最大。

(2).熵的类别

经验熵,经验条件熵,特征熵

习题：

我们有10个苹果，1个好苹果A，9个坏苹果B。熵的计算如下：

$$H(P)=-\sum _{i=1}^n{p}_i\log p_i=-[P(A)\log P(A)+P(B)\log P(B)]$$

$$=-[\frac{1}{10}\log \frac{1}{10}+\frac{9}{10}\log \frac{9}{10}]=0.47$$

1个坏苹果9个好苹果时，我们可以认为大部分都是坏苹果。内部并不混乱，确定性很大，熵就小。

如果5个好苹果5个坏苹果呢？

$$H(P)=-\sum _{i=1}^n{p}_i\log p_i=-[P(A)\log P(A)+P(B)\log P(B)]$$

$$=-[\frac{5}{10}\log \frac{5}{10}+\frac{5}{10}\log \frac{5}{10}]=1$$

5个坏苹果5个好苹果时，里面就有点乱了，我们并不太能确定随机的一个苹果是好苹果还是坏苹果，熵就大。

3.信息增益定义

(1).定义

信息增益：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

(2).公式

特征A对训练集D的信息增益$g(D,A)$，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

$$g(D,A)=H(D)-H(D|A)$$

(3).算法

输入：训练数据集 $D$ 和特征 $A$

输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$

(4).结合“挑苹果”实例理解

以图中按“颜色” (特征 A) 挑选苹果的决策树为例：

• 初始状态 $H(D)$：一无所知时的不确定性
  在最顶层的根节点，面对的是全部 10 个苹果(5 个好，5 个坏)。此时我们完全不知道随便拿出一个是好是坏，不确定性达到峰值。

  $$H(P)=-\sum _{i=1}^n{p}_i\log p_i=-[P(A)\log P(A)+P(B)\log P(B)]$$

  $$=-[\frac{5}{10}\log \frac{5}{10}+\frac{5}{10}\log \frac{5}{10}]=1$$

  此时的经验熵为：$H(D)=1$。

• 引入特征 A 后的状态 $H(D|A)$：知道“颜色”后的不确定性

  现在，得知了苹果的“颜色”特征，并将 10 个苹果分成了两拨：

  • 左侧红色分支 ($D_1$): 分配到了4个苹果。包含1个好苹果，3个坏苹果。这4个红苹果内部依然存在不确定性，记作 $H(D_1)$。
  • **右侧绿色分支 ($D_2$)😗*分配到了6个苹果。包含 4个好苹果，2个坏苹果。这 6个绿苹果内部的不确定性记作 $H(D_2)$。

此时，整体的经验条件熵 $H(D|A)$，就是按颜色分开后，这两个分支不确定性的加权平均(数量越多的分支，在总体里的权重越大)：

$$H(D|A)=\frac{4}{10}H(D_1)+\frac{6}{10}H(D_2)$$

信息增益 $g(D,A)$就是不确定性下降了多少。将最初的混乱程度 $H(D)$，减去按照颜色分拨之后的总混乱程度 $H(D|A)$，得到的差值就是信息增益：

$$g(D,A)=H(D)-H(D|A)$$

总结：

一开始面对一筐苹果，你完全猜不透好坏(此时 $H(D)$ 最大，最懵)。
现在你引入了“颜色”这个特征，把苹果按红绿分开。分开后你发现规律了：红苹果里坏的概率很大(3/4)，绿苹果里好的概率很大(4/6)。你心里对苹果好坏的判断突然清晰了不少，整体的“懵圈程度”下降了($H(D|A)$ 变小了)。

原先的懵圈程度，减去现在的懵圈程度，这个下降的幅度，就是“颜色”这个特征给你带来的“信息增益”。 信息增益越大，说明按“颜色”来挑选苹果这个决策越明智！

4.信息增益比定义

(1).作用

如果以信息增益为划分依据，存在偏向选择取值较多的特征，信息增益比是对这一问题进行矫正。

(2).公式

信息增益比：特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的值熵 $H_A(D)$ 之比：

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

其中，分母 $H_A(D)$ 的计算公式为：

$$H_A(D)=-\sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$

(3).原理

为什么它能矫正“偏向取值较多的特征”？
假设我们有一个特征叫“苹果编号”（1号到10号）。

• 如果用这个特征来划分，每个分支只有 1 个苹果。此时条件熵 $H(D|A)=0$（因为每个分支里就一个苹果，好坏是100%确定的）。
• 这会导致信息增益 $g(D,A)$ 达到最大值！决策树会误以为“编号”是一个超级好的特征。但显然“编号”对泛化毫无用处。

为了惩罚这种“把数据切得太碎”的特征，我们引入了分母 $H_A(D)$：

• 当一个特征取值非常多时，数据被切分得很散，此时算出来的特征自身的信息熵 $H_A(D)$ 就会非常大。
• 在公式 $g_R=\frac{g}{H_A(D)}$ 中，除以一个很大的数，就把原来虚高的信息增益给“压下来”了，起到了惩罚作用。

比如银行信贷用身份证划分这个例子

三.决策树的生成

1. ID3

输入：训练数据集 $D$，特征 $A$，阈值 $\epsilon$；

输出：决策树 $T$

2. C4.5

就是把ID3的信息增益换成了信息增益比

输入：训练数据集 $D$，特征 $A$，阈值 $\epsilon$；

输出：决策树 $T$

3. CART 算法(分类树部分)

核心思想：把 ID3/C4.5 的信息熵换成了“基尼指数（Gini Index）”，并且 CART 默认生成的是二叉树。注：在 CART 算法中，用过的特征可以再用！

(1). 基尼指数定义

基尼指数： 在分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为：

$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$

直观理解： 基尼指数表示在样本集合中一个随机选中的样本被分错的概率。

结论：基尼指数越小，数据集越纯（与信息熵的性质一致）。

(2). 数据集$D$的基尼指数

对于给定的样本集合 $D$，其基尼指数为：

$$Gini(D)=1-\sum _{k=1}^K{\left(\frac{|C_k|}{|D|}\right)}^2$$

(其中 $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集)

(3). 给定特征 $A$ 的基尼指数 (Gini_index)

如果我们在特征$A$的条件下，将数据集$D$进行划分（以二分法为例，划分为 $D_1$ 和 $D_2$），则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为：

$$Gini\_index(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)=\sum P(A=a)\cdot Gini(D|A=a)$$

(4). 算法生成逻辑

• 递归的过程： 与 ID3/C4.5 类似，从根节点开始递归建树。
• 最优属性选择： 在所有可能的特征 $A$ 以及它们所有可能的切分点中，选择使得划分后基尼指数 $Gini\_index(D,A)$ 最小的特征及其切分点作为最优划分属性。

输入：训练数据集 $D$，停止计算的条件（如基尼指数阈值 $\epsilon$ 或结点中样本个数下限）；

输出：CART 决策树 $T$

四. 决策树的剪枝与过拟合

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据分类却没有那么准确，即容易出现过拟合现象。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化，这个过程称为剪枝（Pruning）。

1. 构建决策树的损失函数(纯经验损失)

如果不考虑树的复杂度，决策树在训练集上的损失函数定义为所有叶子节点的“不纯度”的加权和：

$$C(T)=\sum _{t=1}^{|T|}N(t)\cdot H(t)$$

• $|T|$：表示决策树的叶子结点个数。
• $t$：表示树的某一个具体的叶子结点。
• $N(t)$：是该叶子结点 $t$ 内包含的样本个数。
• $H(t)$：是该叶子结点 $t$ 的不纯度度量 (Impurity)。
• 注意：$H(t)$ 是一个广义符号。在 ID3/C4.5 中，它是经验熵；在 CART 分类树中，它是基尼指数 $Gini(t)$。

注：如果训练目标仅仅是 ${\min }_{T}C(T)$，模型会倾向于把每个叶子节点分到只有 1 个样本（此时无论算熵还是算基尼指数，$H(t)$ 都等于 0，$C(T)=0$），从而导致严重的过拟合。

2. 决策树的正则化函数 (结构风险最小化)

为了防止过拟合，我们需要在损失函数中加入表示“树复杂度”的正则化惩罚项：

$$C(T)=\sum _{t=1}^{|T|}N(t)\cdot H(t)+\lambda \cdot |T|$$

其中：

• $\lambda$：表示正则化超参数（常写作 $\alpha$ 或 $\lambda$），用于控制惩罚力度，$\lambda \ge 0$。
• $|T|$：表示叶子结点个数，代表了树的整体复杂度。树越庞大，$|T|$ 越大。

核心机制与结论：

正则化函数本质上是在“模型对训练数据的拟合程度”与“模型的复杂度”之间进行权衡。

• 当 $\lambda \to +\infty$ 时： 惩罚极其严厉。此时为了让损失函数最小，只能拼命压缩叶子节点的数量，树最终只保留根节点（变成单节点树）。
• 当 $\lambda \to 0$ 时： 几乎没有惩罚。退化为只考虑经验损失，树会尽可能拟合数据集（容易过拟合）。
• 剪枝策略： 从整棵树开始，尝试剪掉某些子树。如果剪掉某棵子树后，整体的正则化损失函数 $C(T)$ 变小了，那就说明剪裁是划算的，坚决剪掉！

五. 连续值属性的处理

现实任务中常会遇到连续属性（如温度、密度、收入等），决策树处理连续值的最经典策略是采用二分法（Bi-partition）。此方法在 C4.5 和 CART 算法中被广泛使用。

1. 连续值的离散化（寻找切分点）

给定样本集 $D$ 和连续属性 $A$：

$$T_A=\left\{\frac{a_i+a_{i+1}}{2}\mid i=1,2,\dots ,n-1\right\}$$

(注：在工程优化中，为了减少计算量，通常只取目标标签发生改变的相邻值的中点作为候选切分点。)

2. 计算信息增益选定最优阈值

把每一个候选划分点 $t$ 都看作是一个布尔属性（即取值为“$\le t$”和“$>t$”两类）：

像考察离散属性一样，遍历集合 $T_A$ 中的每一个候选点，计算对应的信息增益（或基尼指数），选择使得纯度提升最大的点作为该连续属性的最优切分点。

信息增益计算公式变为：

$$g(D,A)=\underset{t\in T_A}{\max }\left(H(D)-\left(\frac{|D_t^{-}|}{|D|}H(D_t^{-})+\frac{|D_t^{+}|}{|D|}H(D_t^{+})\right)\right)$$

3. 核心特权：连续属性可重复使用

• 离散属性的消耗性： 在多叉树（如 ID3/C4.5）中，离散属性（如“颜色”）用作划分节点后，在其后代节点中将不再可用。
• 连续属性的复用性： 与离散属性不同，一连续属性仍可以作为其后代结点的划分属性。
• 直观理解： 在父节点按“温度 $\le 60$”切分后，在左子树中，依然可以针对剩下的样本继续按“温度 $\le 45$”进行更细粒度的二次切分。

六. 缺失值的处理

在现实任务中，常会遇到不完整样本，即样本的某些属性值缺失。如果直接放弃不完整样本，会造成数据信息的极大浪费。C4.5算法引入了==“样本权值”==的概念来优雅地处理缺失值。

核心设定： 赋予每个样本 $x$ 一个权重 $w_x$，初始状态下，所有样本的权重 $w_x=1$。

1. 缺失属性的特征选择 (怎么算信息增益？)

问题：如果在属性 $A$ 上有样本缺失值，如何计算属性 $A$ 的信息增益？

定义无缺失子集 $\tilde{D}$： 给定数据集 $D$，定义 $\tilde{D}$ 为 $D$ 中在属性 $A$ 上没有缺失值的样本子集。

基于 $\tilde{D}$，我们定义三个重要的比例：

新的信息增益计算公式：

$$Gain(D,A)=\rho \times Gain(\tilde{D},A)$$

$$Gain(\tilde{D},A)=Ent(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_{v}Ent({\tilde{D}}^v)$$

• $Ent(\tilde{D})$就是经验熵

直观理解：
算信息增益时，先只用那些“完好无缺”的样本（$\tilde{D}$）正常算一遍信息增益。
算完之后，因为这个特征有缺失，我们要打个折扣。打折的系数就是 $\rho$。缺失得越严重，$\rho$ 越小，这个特征最终的信息增益就越低，也就越不容易被选为切分节点。

2. 缺失属性的样本划分 (遇到缺失样本怎么分叉？)

问题：如果已经决定按属性 $A$ 进行划分，但样本 $x$ 恰好在属性 $A$ 上的值是缺失的，它该进入哪个子节点？

• 情况 1：样本 $x$ 在属性 $A$ 上无缺失。
  正常处理，按照它的真实取值划入对应的子结点，并且样本权值 $w_x$ 保持不变。

• 情况 2：样本 $x$ 缺失属性 $A$ 的值。
  此时，我们让该样本同时进入所有子结点！就像火影忍者里的“影分身”，但分身出来的权重不再是 1。
  进入取值为 $a^v$ 的分支子节点时，该样本的权值调整为：

  $$w_x\leftarrow {\tilde{r}}_v\cdot w_x$$

大白话解析（影分身之术）：
假设我们在按“温度”分叉。对于已知温度的样本，60% 去了“高温”分支（即 ${\tilde{r}}_1=0.6$），40% 去了“低温”分支（即 ${\tilde{r}}_2=0.4$）。
这时来了一个不知道温度的样本 $x$（初始权重为 1）。
决策树的做法是：把这个样本切成两份，让 0.6 个 $x$ 走向高温分支，0.4 个 $x$ 走向低温分支。
这样，缺失值样本带着不同的概率权重，参与到了后续所有分支的学习中。

七. 集成学习与随机森林(Random Forest)

单棵决策树容易过拟合，且边界只能是横平竖直的阶梯。为了突破单模型的性能天花板，我们引入了集成学习。

1. 集成学习(Ensemble Learning)核心思想

集成学习的目标是通过构建并结合多个机器学习器如多棵决策树）来完成学习任务。

• 提升性能： “三个臭皮匠，顶个诸葛亮”。将多个弱学习器组合成一个强学习器，大幅提升整体的预测精度。
• 消除偏差： 利用模型之间的多样性（差异性）。不同的树会在不同的数据区域犯错，将它们组合起来可以相互抵消误差，使得最终的决策边界更加平滑且精准。

2. 随机森林的三大核心机制

随机森林 = 多棵决策树 + 随机性。 它通过以下三个核心步骤来保证每棵树都不一样（保证多样性）：

(1). 自助采样 (Bootstrap Sampling) —— 数据的随机性

每棵树的训练数据都不是全量数据，而是通过有放回的抽样构建出来的子数据集。

• 做法： 从原始的数据集中，每次随机抽取一个样本放入子集，再把这个样本放回原数据集（意味着下次还能被抽到）。重复这个过程，直到子数据集的数据量和原数据集数据量相同。
• 结果： 在构建出的子数据集中，有些原始样本会重复出现，而有些原始样本则从未被抽中。这保证了每棵树看到的训练数据都是有差异的。

(2). 待选特征的随机选取 —— 属性的随机性

这是随机森林相比于普通“树的集合”最精妙的一笔。

• 做法： 在单棵决策树（如 CART）中，节点分裂时会遍历所有的特征寻找最优切分点。但在随机森林中，节点分裂时，会先从所有特征中随机抽取一部分特征（比如总共有 100 个特征，随机抽出 10 个），然后再在这 10 个特征中寻找最优分裂属性。
• 作用： 进一步强行让每棵树长得不一样，极大提升了系统的多样性，防止模型过度依赖某几个所谓的“强特征”。

(3). 多数表决 (Majority Voting) —— 结果的整合

当成百上千棵各不相同的树都建好之后，预测阶段采用民主集中制。

• 分类问题： 少数服从多数。每棵树投出一票（如 Class 1），最终得票最多的类别就是整个森林的预测结果。
• 回归问题： 取平均值。把所有树输出的连续数值加起来求平均。

3. 随机森林的绝对优势

由于引入了双重随机性（数据随机 + 特征随机），随机森林拥有极佳的模型性质：

• 原理： 在进行 Bootstrap 有放回抽样时，数学上可以证明，有大约 36.8% 的原始样本从未被抽入某棵树的训练集中。
• 包外估计 (Out-of-Bag Estimate, OOB)： 这 36.8% 没被抽中的数据（包外数据），天然就可以作为这棵树的“测试集”！因此，随机森林在训练的同时，就能用这些没有参与训练的数据来自己评估自己的性能，极其高效！