1 决策树

决策树是一种模拟人类“分而治之”决策逻辑的树形模型，其核心优势在于直观易懂和解释性强。

它通过一系列“如果…那么…”的规则对数据进行分割，最终到达一个结论。

这种结构使其能同时胜任分类（预测类别标签）与回归（预测连续值）任务。

一棵决策树由以下关键部件构成：

• 根节点：代表整个数据集的起始点，包含了第一个也是最重要的特征判断。
• 非叶子节点（决策节点）与分支：树的躯干。每个非叶子节点都代表对一个特征的测试；每个分支则代表该测试的一个可能结果（例如，“天气=晴朗”或“收入>5万”），并将数据导向下一个节点。
• 叶子节点（终结点）：树的末端，不再进行进一步划分。每个叶子节点会赋予一个最终的预测值（分类中的具体类别，或回归中的具体数值）。

模型的工作流程清晰分为两阶段：

1. 训练阶段：从带有标签的训练数据中，自动学习并构建出最优的树形结构。这涉及到递归地选择最佳分割特征和分割点。
2. 测试阶段：对于新样本，只需从根节点开始，根据其特征值选择对应分支向下遍历，最终到达的叶子节点的值即为模型预测结果。

2 决策树的构建：熵与信息增益

2.1 衡量标准：熵——混乱度的量化

构建决策树的核心在于如何选择分裂特征，目标是让分裂后的子集尽可能“纯净”。我们使用熵来量化一个数据集的混乱度或不纯度。

对于一个包含 K 个类别的数据集 D，其熵定义为：
$$H(D)=-\sum _{k=1}^K{p}_k{\log }_2{p}_k$$
其中，$p_k$ 是数据集中第 k 类样本所占的比例。

• 熵的意义：熵值越高，表示数据集的类别分布越均匀，不确定性越大。例如，一个集合中“是”和“否”各占一半，其熵达到最大值1。
• 熵的直观例子：如文档所述，集合 A [1,1,1,1,1,1,1,1,2,2]（主要类别是1）的熵值远低于集合 B [1,2,3,4,5,6,7,8,9,1]（类别繁多且分散）。我们的目标是通过特征分裂，使子集的熵降低。

2.2 决策准则：信息增益——分裂效果的度量

为了评估使用某个特征 A 进行分裂的效果，我们计算信息增益。它表示分裂前后，系统不确定性减少的量，即“获得”的信息量。

信息增益的公式为：
$$Gain(D,A)=H(D)-H(D|A)$$
其中：

• $H(D)$ 是分裂前数据集 D 的熵。
• $H(D|A)$ 是特征 A 给定条件下 D 的条件熵。它是按特征 A 的每个取值 $a_v$ 划分出的子集 $D_v$ 的熵的加权和：
  $$H(D|A)=\sum _{v=1}^V\frac{|D_v|}{|D|}H(D_v)$$
  V 是特征 A 的取值个数，$|D_v|$ 是取值为 $a_v$ 的样本数。

信息增益越大，说明使用特征 A 进行分裂后，数据纯度提升得越多，该特征越适合作为当前节点的分裂依据。

2.3 构建实例详解：14天打球决策树

我们以文档中经典的“14天是否打球”数据集为例，演示如何选择根节点。数据包含 Outlook, Temperature, Humidity, Windy 四个特征，目标 Play 有两个类别：Yes 和 No。

1. 计算初始熵：14天中，9天打球(Yes)，5天不打球(No)。
   $$H(D)=-\frac{9}{14}{\log }_2\frac{9}{14}-\frac{5}{14}{\log }_2\frac{5}{14}\approx 0.940$$

2. 计算特征 Outlook 的信息增益：

   • Outlook 有 3 个取值：Sunny (5天), Overcast (4天), Rainy (5天)。
   • 计算每个子集的熵：
     • Outlook = Sunny: [2 Yes, 3 No] → $H(Sunny)=0.971$
     • Outlook = Overcast: [4 Yes, 0 No] → $H(Overcast)=0$
     • Outlook = Rainy: [3 Yes, 2 No] → $H(Rainy)=0.971$
   • 计算条件熵：
     $$H(D|Outlook)=\frac{5}{14}\times 0.971+\frac{4}{14}\times 0+\frac{5}{14}\times 0.971\approx 0.693$$
   • 计算信息增益：
     $$Gain(Outlook)=H(D)-H(D|Outlook)=0.940-0.693=0.247$$

3. 比较并选择根节点：用同样方法计算其他特征的信息增益：

   • Gain(Temperature) ≈ 0.029
   • Gain(Humidity) ≈ 0.152
   • Gain(Windy) ≈ 0.048
Outlook 的信息增益最大，因此被选为根节点。然后，我们在 Outlook 的每个分支下（如 Sunny 分支），对剩余的特征递归地重复此过程，构建出完整的树。

3 决策树算法变体与关键技术

3.1 主要算法家族

• ID3：最基础的算法，直接使用信息增益作为特征选择准则。但其倾向于选择取值数目多的特征（如“学号”），容易导致过拟合。
• C4.5：ID3的改进版。使用信息增益率来修正上述偏差。信息增益率是信息增益与特征本身熵的比值，能够减少对多值特征的偏好。其公式为：
  $$Gain\_Ratio(D,A)=\frac{Gain(D,A)}{H_A(D)}$$
  其中 $H_A(D)$ 是特征 A 的取值分布自身的熵。
• CART：使用基尼系数作为不纯度度量，定义为从数据集中随机抽取两个样本，其类别标签不一致的概率。对于数据集 D：
  $$Gini(D)=1-\sum _{k=1}^K{p}_k^2$$
  基尼系数越小，纯度越高。CART 每次都生成二叉树（“是”或“否”的分支），适用于分类和回归（此时使用方差最小化准则）。

3.2 连续值处理

决策树本质处理离散特征。对于连续特征（如“年龄”、“收入”），采用二分法进行离散化：

1. 将该特征的所有取值升序排序。
2. 取每两个相邻值的中点作为候选分割点。例如，排序后的年龄为 [22, 25, 30, 36]，则候选点为 23.5, 27.5, 33。
3. 计算以每个候选点进行分割（如“年龄 ≤ 27.5”）后的信息增益或基尼系数。
4. 选择使评估指标最优的那个候选点作为最终分割点。这是一个在有限候选集中寻找最优解的贪婪算法。

3.3 剪枝策略：对抗过拟合

决策树如果不加限制，会一直生长到每个叶子节点只包含一个样本，从而完美拟合训练数据（包括噪声），导致过拟合。

• 预剪枝：在树生成过程中就进行控制。常用条件包括：树达到最大深度；节点样本数低于阈值；分裂带来的性能提升（如信息增益）低于阈值。优点是训练快、减少过拟合风险；缺点是可能因“目光短浅”而欠拟合。
• 后剪枝：先构造一棵完整的树，再自底向上考察非叶子节点。如果将其子树替换为一个叶子节点（以该节点下多数类为预测结果）能提升模型在验证集上的性能，则进行剪枝。常用代价复杂度剪枝，其损失函数为：
  $$C_{\alpha }(T)=C(T)+\alpha \cdot |T_{leaf}|$$
  其中 $C(T)$ 是模型在训练数据上的预测误差（如误分类数），$|T_{leaf}|$ 是树的叶子节点总数，$\alpha$ 是权衡系数。通过调整 $\alpha$，可以在模型复杂度和拟合精度之间取得平衡。

4 集成算法概述

单一模型（弱学习器）的能力可能有限且不稳定。集成学习通过构建并结合多个学习器来完成学习任务，通常能获得比单一学习器显著优越的泛化性能。

三大主流范式及其目标：

1. Bagging：并行训练多个同质且相互独立的弱学习器，通过投票（分类）或平均（回归） 聚合结果。核心目标是降低模型方差，对不稳定的基学习器（如决策树）效果提升尤为明显。
2. Boosting：串行训练多个同质的弱学习器，每个新学习器都根据前序模型的错误进行调整，赋予错误样本更高权重，并最终对所有学习器进行加权组合。核心目标是降低模型偏差，将一系列“弱”模型提升为“强”模型。
3. Stacking：分层训练异质的基学习器。第一层用不同算法训练多个模型，第二层则以第一层模型的预测结果作为新特征，训练一个元学习器进行最终决策。目标是综合不同模型的优势。

5 Bagging与随机森林

5.1 Bagging原理

Bagging 是 Bootstrap Aggregating 的缩写。其核心步骤是：

1. 自助采样：从原始训练集 D 中，进行 M 轮有放回的随机采样，得到 M 个大小约为 n 的 Bootstrap 样本集。
2. 并行训练：用这 M 个样本集独立地训练 M 个基学习器。
3. 聚合输出：对于分类任务，采用投票法；对于回归任务，采用平均法。最终输出可表示为：
   $$f_{bag}(x)=\{\begin{array}{ll}\arg {\max }_c{\sum }_{m=1}^{M}I(f_m(x)=c),& \text{分类}\\ \frac{1}{M}{\sum }_{m=1}^M{f}_m(x),& \text{回归}\end{array}$$

5.2 随机森林——Bagging的卓越代表

随机森林是以决策树为基学习器的Bagging扩展，并引入了双重随机性以进一步增强模型多样性：

1. 样本随机：对每棵决策树，使用Bootstrap采样生成训练集。
2. 特征随机：在决策树每个节点进行分裂时，不是从所有 d 个特征中选择最优特征，而是先随机选取一个包含 k（通常 $k\approx {\log }_{2}d$ 或 $\sqrt{d}$）个特征的特征子集，再从这个子集中选择最优特征进行分裂。

优势：

• 强大的泛化能力：双重随机性有效降低了模型方差，减少了过拟合。
• 可处理高维数据：无需做严格的特征选择。
• 可评估特征重要性：通过观察特征在所有树中被用于分裂节点时带来的不纯度减少量的平均值，可以评估特征的重要性。
• 并行化友好：每棵树的训练相互独立，易于分布式计算。

6 Boosting与AdaBoost

6.1 Boosting原理

Boosting 是一种序列化学习机制。其通用思想是：在第 m 轮迭代中，训练一个新的弱学习器 $h_m(x)$，使其专注于修正当前集成模型 $F_{m-1}(x)$ 在前一轮产生的错误。其加法模型通常形式为：
$$F_M(x)=\sum _{m=1}^M\eta \cdot h_m(x)$$
其中 $\eta$ 是学习率，用于控制每棵树的贡献。

6.2 AdaBoost工作流程详解

AdaBoost（Adaptive Boosting）是Boosting家族中最经典的算法，特别适用于二分类问题。

1. 初始化权重：对于包含 N 个样本的训练集，初始化每个样本的权重 $w_i^{(1)}=\frac{1}{N}$。
2. 迭代训练（对于 m = 1 to M）：
   a. 训练弱分类器：使用当前样本权重分布 $w^{(m)}$ 训练一个弱分类器 $G_m(x)$（例如，一个深度很浅的决策树）。
   b. 计算分类错误率：$$e_m=\sum _{i=1}^N{w}_i^{(m)}I(G_m(x_i)\ne y_i)$$
   c. 计算该分类器权重：分类器 $G_m(x)$ 在最终集成中的话语权（权重）${\alpha }_m$ 由其错误率决定：$${\alpha }_m=\frac{1}{2}\ln \left(\frac{1-e_m}{e_m}\right)$$
   错误率越低，${\alpha }_m$ 越大。当 $e_m>0.5$ 时，${\alpha }_m<0$，但AdaBoost通常要求基学习器性能略优于随机猜测（$e_m<0.5$）。
   d. 更新样本权重：增加被 $G_m(x)$ 错误分类样本的权重，减小正确分类样本的权重，使得下一轮分类器更关注难分的样本：
   $$w_i^{(m+1)}=\frac{w_i^{(m)}\cdot \exp (-{\alpha }_m{y}_i{G}_m(x_i))}{Z_m}$$
   其中 $Z_m$ 是归一化因子，确保 $\sum w_i^{(m+1)}=1$。
3. 构建最终强分类器：M 轮迭代后，得到 M 个弱分类器及其权重，通过加权投票进行最终预测：
   $$F(x)=\text{sign}\left(\sum _{m=1}^M{\alpha }_m{G}_m(x)\right)$$

7 Stacking集成

7.1 核心思想与流程

Stacking 是一种更高级、更灵活的集成策略，旨在融合不同类型学习器的优势。

其标准的两层Stacking流程如下：

1. 第一层（基学习器层）：
   • 选择 K 个异质的学习算法作为基学习器（例如：决策树、支持向量机、K近邻、神经网络等）。
   • 使用原始训练集 D 训练所有这些基学习器。
2. 生成元特征：
   • 为了避免数据泄露，通常采用交叉验证（如5折）的方式生成第一层预测。具体来说，将训练集 D 分为5折，对于每个基学习器，轮流用4折训练，预测剩余1折，最终得到整个训练集 D 在未见过数据上的预测结果。这些预测结果构成新的特征矩阵。
   • 同时，每个基学习器在整个 D 上训练，用于预测最终的测试集。
3. 第二层（元学习器层）：
   • 将第一步生成的新特征矩阵（维度为 N × K，N是样本数，K是基学习器数）作为新的训练集。
   • 选择一个元学习器（通常是比较简单、不易过拟合的模型，如逻辑回归或线性回归），在这个新训练集上进行训练。
4. 预测：对于新样本，先由第一层所有基学习器生成预测，将这些预测作为特征输入训练好的元学习器，得到最终预测。

7.2 特点与应用

• 优势：能够从不同视角（不同算法）挖掘数据模式，理论上能获得非常强大的预测性能，是机器学习竞赛中的“夺冠利器”。
• 劣势：训练过程复杂，计算成本高昂，且模型可解释性差。
• 适用场景：当追求极致性能且计算资源充足时，Stacking是一个强有力的选择。