（四）决策树

1. 技术原理

决策树是一种监督学习算法，用于分类和回归任务。其核心思想是通过一系列的“if-then-else”条件筛选，对数据进行层层划分，最终形成一个树形结构。这个结构包括：

• 根节点 (Root Node)：代表整个数据集的起始点，包含所有样本。

• 内部节点 (Internal Node)：每个内部节点对应一个特征或属性上的判断条件（例如，“年龄是否大于30？”），根据特征的不同取值将数据引导至不同的分支。

• 叶节点 (Leaf Node)：树的终端节点，代表最终的决策结果（分类任务中是类别标签，回归任务中是预测值）

决策树的构建是一个递归分割的过程，目标是通过不断选择最优的特征进行划分，使得子节点的“纯度”越来越高（即同一节点内的样本尽可能属于同一类别或具有相似的数值）

1. 搭建过程：

1. 特征选择与划分标准

构建决策树的关键在于如何选择每个节点上用于划分的最优特征。常用的衡量标准有：

1. 信息增益 (Information Gain) - ID3 算法

• 信息熵：衡量数据集的不确定性或混乱程度。熵越大，不确定性越高。

• 信息增益：计算使用某个特征 A 划分数据集前后熵的减少量。信息增益越大，意味着使用特征 A 进行划分所获得的信息量越多，该特征越优。

• 缺点：信息增益倾向于选择取值较多的特征（例如“身份证号”），但这可能导致过拟合且缺乏实际意义

1. 信息增益率 (Gain Ratio) - C4.5 算法

• 为克服信息增益的缺点，C4.5 算法引入了信息增益率。它通过除以特征本身的“固有值”（Intrinsic Value，类似特征熵）来惩罚取值较多的特征。

• C4.5 还支持对连续特征进行处理（通过离散化）和缺失值的处理

1. 基尼系数 (Gini Index) - CART 算法

• 基尼值：衡量从数据集中随机抽取两个样本，其类别标签不一致的概率。基尼值越小，数据纯度越高。

• 基尼指数：特征 A 的基尼指数是各子集基尼值的加权和。

• CART 算法总是选择使得划分后基尼指数最小的特征作为划分标准

• CART 算法构建的是二叉树，每个非叶节点只有两个分支（即使特征有多个取值），同时适用于分类和回归任务（回归任务中使用均方误差 MSE 作为划分标准）

1. 构建流程与停止条件

决策树的构建是一个递归的、自上而下的过程：

1. 从根节点开始：计算当前数据集中所有特征的信息增益（或增益率，或基尼指数）。

2. 选择最优特征：选择能最大程度降低不纯度的特征作为当前节点的划分标准。

3. 划分数据集：根据该特征的不同取值，将当前数据集划分成若干子集，并为每个子集创建一个新的子节点。

4. 递归重复：对每个子节点递归地执行步骤 1-3，直到满足以下停止条件之一：

   1. 节点中的样本全部属于同一类别。

   2. 没有剩余特征可用于进一步划分。

   3. 节点中的样本数少于预设的最小值（如 min_samples_split）。

   4. 树的深度达到预设的最大值（如 max_depth）

1. 剪枝：防止过拟合

决策树非常容易过拟合（Overfitting），即在训练集上表现很好，但在未见过的测试集上表现不佳。为了解决这个问题，需要进行剪枝（Pruning）。

1. 预剪枝 (Pre-Pruning)

• 在树构建的过程中，提前停止树的生长。

• 通过设置一些核心参数来实现，例如：

  参数	作用	典型值/选择
  criterion	分裂准则（基尼指数或信息熵）	"gini"（CART）或 "entropy"（ID3）
  max_depth	树的最大深度，控制模型复杂度	3-10（过深易过拟合）
  min_samples_split	节点分裂所需最小样本数	2-20（防止过拟合）
  min_samples_leaf	叶节点最少样本数	1-10（平滑预测）
  max_features	分裂时考虑的最大特征数（None=全部）	"sqrt"（分类）或 "log2"（回归）

• 优点：计算开销小，效率高。

• 缺点：可能带来欠拟合风险，因为可能过早停止了划分，忽略了后续可能存在的有价值的分裂

1. 后剪枝 (Post-Pruning)

• 先让决策树充分生长（可能产生过拟合），然后自底向上，考察非叶节点。

• 若将其替换为叶节点（以该节点下样本最多的类别作为标签）能提升模型在验证集上的泛化性能，则进行剪枝。

• 优点：通常能保留更多的分支，泛化性能可能更好。

• 缺点：计算开销较大

1. 优缺点

算法	优势	劣势
决策树	✅ 高度可解释：规则可视化，适合业务解释	❌ 高方差：易过拟合，需剪枝
	✅数据预处理简单：不需要对数据进行标准化或归一化，可以处理数值型和类别型特征	❌ 不稳定：数据微小变化导致树结构巨变
	✅ 高效训练：时间复杂度O(n log n)	❌ 忽略信息：对于复杂的非线性关系，单棵决策树的拟合能力可能有限

决策树主要的挑战在于如何防止过拟合，通常需要通过剪枝技术或使用集成学习方法来优化模型性能。

为了克服单棵决策树的缺点（如过拟合、稳定性差），实践中更常用的是基于决策树的集成学习方法：

• 随机森林 (Random Forest)：通过构建多棵决策树，并进行投票或平均来提高预测准确性和稳定性。同时引入了随机性（对样本和特征进行随机抽样），进一步降低过拟合风险

• 梯度提升树 (Gradient Boosting Machines, GBM)：如 XGBoost, LightGBM, CatBoost。通过迭代地训练一系列决策树，每一棵树都试图纠正前一棵树的错误，通常能获得很高的精度