决策树 Decision Tree

从混乱到有序的智慧分割 · From Chaos to Order

01. 概述与定义 Overview & Definition

什么是决策树？

决策树 (Decision Tree) 是一种受人类决策逻辑启发的非参数监督学习算法，广泛应用于分类 (Classification) 和 回归 (Regression) 任务。

它的本质是将复杂的决策过程分解为一系列简单的选择题。就像医生诊断病情或银行审批贷款一样，通过层层提问（特征判断），最终得出一个确定的结论。在机器学习领域，它以其高可解释性、可视化强以及无需大量数据预处理的特性，成为了数据科学中的核心基石。

核心应用场景：医疗诊断、风险评估、客户细分、故障检测等。

02. 核心结构与术语 Core Structure

决策树由节点和有向边组成，形成一个倒置的树状结构。理解以下四个关键术语是掌握算法的前提：

  • ROOT NODE (根节点) 树的起始点，包含完整的训练数据集。它没有父节点，但有两个或多个子节点。
  • INTERNAL NODE (内部节点 / 决策节点) 代表一个特征或属性的测试条件（例如：“温度 > 25°C？”）。根据测试结果，样本被分流到不同的分支。
  • LEAF NODE (叶节点 / 终结点) 树的末端，不再进行分割。它代表最终的决策结果（类别标签或回归数值）。
  • BRANCH (分支) 连接节点的线段，代表判定结果的输出路径（如“是”或“否”）。
ROOT Start: All Data Yes No Decision LEAF LEAF A LEAF B

图1：决策树的标准拓扑结构，展示了从根节点到叶节点的层级关系。

03. 构建过程与原理 Construction Logic

A. 特征选择：追求“纯度” (Purity)

构建决策树的核心在于：在每一步选择哪个特征进行分割？ 我们的目标是让分割后的子节点尽可能“纯净”（即包含同一类别的样本）。

Low Purity (Impure) Mixed Classes High Purity Single Class

图2：高不纯度（混合）与高纯度（单一）节点的直观对比。

这就引入了量化指标。常用的指标包括：

信息增益 (Information Gain)

基于熵 (Entropy) 的概念。熵越低，纯度越高。我们选择通过分割能使系统整体熵降低幅度最大的特征。

Gain(D, A) = Entropy(D) - Σ Entropy(D_v)

基尼不纯度 (Gini Impurity)

衡量从集合中随机选取一个样本被错误分类的概率。CART算法使用基尼系数最小化准则。

Gini(p) = 1 - Σ (p_i)^2

Parent Entropy High Uncertainty Split by Feature Weighted Avg Entropy = Information Gain Target: Maximize This

B. 分割点选择 & 递归生长

怎么切？ 对于离散特征（如“天气”），直接按取值分支；对于连续特征（如“温度”），算法会排序所有值，尝试相邻值的中点作为阈值，计算信息增益，找到最佳分割点。

Feature X1 Feature X2 Split Condition: X1 > 5

图3：通过特征分割线将二维空间划分为更纯净的子区域。

C. 停止条件

树不会无限生长，通常遇到以下情况停止：

  • 纯度达标：节点内样本已属同一类别。
  • 无特征可分：所有特征都已用完。
  • 预设限制：达到最大深度 (Max Depth) 或 节点样本数过少 (Min Samples)。

04. 经典算法演进 Classic Algorithms

ID3

Iterative Dichotomiser 3

  • 核心指标: 信息增益 (Information Gain)。
  • 特点: 仅支持离散特征；容易偏向取值多的特征（如“ID号”）。
  • 缺点: 无法处理缺失值和连续值；容易过拟合（无剪枝）。

C4.5

Successor to ID3

  • 核心指标: 增益率 (Gain Ratio)，修正了ID3的偏差。
  • 特点: 支持连续值（离散化）和缺失值处理；引入悲观剪枝。
  • 地位: 传统的分类树标杆算法。

CART

Classification And Regression Tree

  • 核心指标: 基尼不纯度 (Classification) / 均方误差 (Regression)。
  • 特点: 严格的二叉树结构；可分类也可回归；使用代价复杂度剪枝。
  • 现状: scikit-learn等现代库的默认实现基础。

05. 优缺点分析 Pros & Cons

优势 (Pros)

  • 白盒模型: 逻辑清晰，易于向非技术人员解释（If-Then规则）。
  • 数据友好: 对异常值不敏感，无需标准化/归一化，能处理混合数据类型。
  • 特征筛选: 自动进行特征选择，通过树结构呈现特征重要性。

劣势 (Cons)

  • 容易过拟合: 如果不加限制，树会生长得非常复杂，记住噪音数据。
  • 不稳定性: 数据微小的变化可能导致树结构发生剧烈改变（高方差）。
  • 局部最优: 贪心算法在每一步只看眼前最优，不保证全局最优树。

06. 过拟合与剪枝 Optimization

过拟合 (Overfitting) 是决策树面临的最大挑战。一棵“完美”的树往往在训练集上表现100%，但在新数据上表现糟糕，因为它学到了太多“特例”和“噪音”。

Overfitting (High Variance) Captures Noise Good Generalization Ignores Noise

图4：左侧为过拟合的复杂树，右侧为剪枝后的简约树。

剪枝策略 (Pruning)

为了对抗过拟合，我们需要给树“瘦身”。

预剪枝 (Pre-pruning)

在生长过程中提前停止。

  • 限制最大深度 (Max Depth)
  • 限制叶节点最小样本数 (Min Samples Leaf)
  • 限制最小信息增益 (Min Info Gain)

风险：可能导致“欠拟合”。

后剪枝 (Post-pruning)

先让树充分生长，再由底向上修剪。

  • 评估验证集性能
  • 代价复杂度剪枝 (Cost Complexity Pruning)
  • 减少误差剪枝 (Reduced Error Pruning)

优点：通常保留更多有用信息，泛化能力更强。

✂️ PRUNED

07. 回归树 Regression Tree

决策树不仅能分类（预测离散标签），也能回归（预测连续数值）。两者的主要区别在于：

Classification Leaf Prediction: Class: "Yes" Prob: 0.92 VS Regression Leaf Prediction: Value: 24.5 Mean of Samples

图5：分类树输出的是类别概率或标签，回归树输出的是叶节点样本均值。

  • 分割目标: 分类树试图降低“不纯度”（熵/基尼）；回归树试图降低“误差”（通常是均方误差 MSE）。
  • 预测输出: 回归树的叶节点输出值通常是落入该节点的所有训练样本的目标值的平均值。

08. 实战推演：贷款批准 Walkthrough

假设我们要建立一个简单的模型来决定是否批准用户的贷款申请。特征包括：收入 (High/Low)，信用记录 (Good/Bad)。

1. 根节点包含所有申请者。
2. 计算特征的信息增益。发现“信用记录”区分度最高。
3. Split 1: 按“信用记录”分割。
   - 左支 (Credit=Bad): 大部分违约 -> 叶节点：拒绝 (Deny)。
   - 右支 (Credit=Good): 仍有违约风险，需进一步判断。
4. Split 2: 在右支中按“收入”分割。
   - 左支 (Income=Low): 风险较高 -> 叶节点：拒绝 (Deny)。
   - 右支 (Income=High): 信用好且收入高 -> 叶节点：批准 (Approve)。

通过这个简单的过程，我们构建了一棵深度为2的树，它清晰地表达了业务规则。