决策树是一种基于树状结构的监督学习模型，广泛应用于分类和回归任务。其核心思想是通过一系列规则对数据进行递归划分，使每个子集内的样本尽可能属于同一类别或具有相似的目标值

基本结构

• 节点：包括根节点、内部节点和叶节点。
  • 根节点：包含全部样本,通过第一个特征划分。
  • 内部节点：表示对某个特征的测试,根据测试结果将数据引向不同分支。
  • 叶节点：代表最终的预测结果（类别或数值）。
• 分支：对应特征测试的不同结果,连接节点。

构建过程

决策树的构建是自上而下的递归过程,主要步骤包括：

1. 特征选择：在每个节点上，从所有特征中选择一个最优特征进行划分，选择标准是使子集的“纯度”最大化，常用准则有：
   • 信息增益（ID3算法）：基于信息熵，选择使信息增益最大的特征，信息增益 = 父节点的熵 - 子节点的加权平均熵。
   • 增益率（C4.5算法）：修正信息增益对多值特征的偏好,通过分裂信息归一化。
   • 基尼不纯度（CART分类树）：选择使基尼不纯度减少最多的特征,基尼不纯度表示从数据集中随机抽取两个样本类别不一致的概率。
   • 方差减少（CART回归树）：选择使子节点目标值方差减少最多的特征。
2. 分裂点选择：对于连续特征，需要确定最佳分割点（如按阈值二分）；对于离散特征,可按类别划分或多分。
3. 递归划分：对生成的子节点重复上述过程,直到满足停止条件。
4. 生成叶节点：当节点满足停止条件时，将其标记为叶节点，并确定其预测值（分类中常采用多数类，回归中采用样本均值）。

停止条件

为防止过拟合，需限制树的生长,常见条件包括：

• 节点中所有样本属于同一类别；
• 节点中样本数少于预设阈值；
• 树的深度达到预设最大值；
• 特征已用完,或进一步划分带来的纯度提升小于阈值。

剪枝

为了提升模型的泛化能力，常对生成的树进行剪枝,分为：

• 预剪枝：在构建过程中提前停止分裂（如上述停止条件）。
• 后剪枝：先生成完整的树，再自底向上修剪一些节点，用叶节点替代，常用方法包括错误率降低剪枝（REP）、悲观错误剪枝（PEP）和代价复杂度剪枝（CCP）。

特点

• 优点：模型直观易解释；对数据预处理要求低（如无需标准化）；能处理数值和类别特征。
• 缺点：容易过拟合，需通过剪枝控制；对数据微小变化敏感，不稳定；贪婪算法可能导致局部最优。

决策树是许多集成方法（如随机森林、梯度提升树）的基础,理解其原理对掌握更复杂的机器学习模型至关重要。

标签： 决策树 监督学习