1. 剪枝 (Pruning)
1.1 为什么需要剪枝？
决策树在训练时，如果任由其生长，可能会为了拟合训练数据中的每一个细节（包括噪声）而变得非常复杂。这样的树在训练集上表现完美，但在未见过的测试集上往往表现很差，也就是过拟合。
例子：
沿用之前的打球数据集（天气与打球的关系），假如我们添加了一个特征'今天是否是我的幸运日'，而这个特征在训练集中纯属巧合地与打球结果相关，决策树可能会用它来划分，导致模型在真实数据上失效。
剪枝就是通过删除树中那些对预测能力贡献不大、主要拟合了噪声或个别样本的枝叶，来简化模型，提高泛化能力。
1.2 剪枝的类型
主要分为预剪枝和后剪枝。
预剪枝 (Pre-pruning)
在决策树生长过程中，提前停止分裂。
- 方法：设定一个阈值，比如信息增益小于某个值、节点包含的样本数少于某个数、树达到一定深度等，就停止分裂，将该节点直接作为叶节点，其类别为多数类。
- 优点：效率高，边建树边剪枝。
- 缺点：可能过早停止，导致欠拟合；阈值难以把握。
后剪枝 (Post-pruning)
先让树充分生长（甚至过拟合），然后自底向上对非叶节点进行考察，判断将其替换为叶节点是否能提升泛化性能。
- 常用方法：代价复杂度剪枝 (Cost Complexity Pruning) 或 错误率降低剪枝 (Reduced Error Pruning)。
- 步骤：
- 生成一棵完全生长的树。
- 从底向上，尝试将某个子树替换为一个叶节点（叶节点的类别取该子树中样本最多的类别）。
- 用验证集评估替换前后的误差：如果替换后误差不增大（或下降），则进行剪枝，否则保留原树。
- 优点：更可靠，通常比预剪枝效果好。
- 缺点：需要额外的验证集，计算开销大。
1.3 直观理解
想象一棵长满枝叶的树，每个枝叶代表一个决策规则。剪枝就像园艺师修剪掉那些'无用'或'有害'的枝条，让树的主干更清晰，生命力更强（泛化能力更好）。
2. 随机森林 (Random Forest)
随机森林是一种集成学习方法，它通过构建多棵决策树并将它们的预测结果进行投票（分类）或平均（回归）来获得最终输出。
2.1 核心思想
- 集成学习：多个弱学习器组合成一个强学习器。如果每棵树都有些许差异，它们集体决策会比单棵树更稳定、准确。
- Bagging (Bootstrap Aggregating)：对原始训练集进行有放回采样，生成多个不同的子训练集，每棵树在不同的子集上训练。
- 随机特征选择：在每个节点分裂时，不是从所有特征中选最优，而是随机选择一部分特征（通常是 sqrt(总特征数) 或 log2(总特征数)），然后从中选最优特征分裂。这增加了树之间的多样性。
2.2 构建过程
- 假设原始训练集有 N 个样本，M 个特征。
- 对于每一棵树（共 T 棵）：
- 从原始训练集中有放回地抽取 N 个样本，形成一个自助样本集 (bootstrap sample)。未被抽到的样本（约 1/3）称为袋外数据 (OOB)，可用于评估模型。
- 在构建树的每个节点时，随机选择 m 个特征（m << M），然后根据信息增益等准则从这 m 个特征中选择最佳分裂特征。
- 每棵树充分生长，通常不进行剪枝。
- 预测时，分类问题采用多数投票，回归问题采用平均值。
