1. 什么是决策树？

决策树是一种监督学习算法，通过树状结构对数据进行分类或回归。其核心思想是通过对数据特征的逐步划分，模拟人类决策过程。每个内部节点代表一个特征判断，分支代表判断结果，叶子节点代表最终结论。

2. 关键概念

• 根节点：包含全部数据的起点。
• 内部节点：对某一特征进行判断的分支点。
• 叶子节点：最终的分类/回归结果。
• 分裂标准：选择最佳特征划分数据的指标（如信息增益、基尼系数）。

---

3. 核心算法类型

算法	分裂标准	任务类型	特点
ID3	信息增益	分类	倾向选择多值特征，可能过拟合
C4.5	信息增益率	分类	改进ID3，处理连续值和缺失值
CART	基尼不纯度	分类	二叉树结构，支持剪枝
CART	均方误差(MSE)	回归	预测连续值

3.1 ID3算法

ID3（Iterative Dichotomiser 3） 是最早的决策树算法之一，由Ross Quinlan于1986年提出，专用于分类任务。其核心思想是通过信息增益（Information Gain） 选择最优特征进行节点分裂，逐步构建树结构，最终生成可解释的分类规则。

核心原理

1. 信息熵（Entropy）
   衡量数据集的不确定性，值越大表示数据越混乱。
   公式：
   $$H(S)=-\sum _{i=1}^n{p}_i{\log }_2{p}_i$$

   • $p_i$：类别$i$在数据集$S$中的比例
   • 熵值越大，说明数据集的不确定性越高
   • 当所有样本属于同一类时，此时$p_i=1$，熵为0（最纯净）。

2. 信息增益（Information Gain）
   衡量某个特征对分类目标的贡献度。
   公式：
   $$IG(S,A)=H(S)-\sum _{v\in \text{Values}(A)}\frac{|S_v|}{|S|}H(S_v)$$

• 参数说明

  • $S$是整个数据集
  • $A$是某个属性特征
  • $IG$代表信息增益，表示使用属性$A$对数据集$S$进行划分所获得的信息增益。
  • $H(S)$表示数据集$S$的熵（Entropy）。
  • ${\sum }_{v\in \text{Values}(A)}\frac{|S_v|}{|S|}H(S_v)$：
    • $\text{Values}(A)$表示属性$A$的所有可能取值。
    • 对于每个取值$v$，$S_v$是数据集$S$中属性$A$取值为$v$的子集。
    • $|S_v|$是子集$S_v$的大小（样本数量），$|S|$是数据集$S$的大小。$\frac{|S_v|}{|S|}$表示子集$S_v$在数据集$S$中所占的比例。
    • $H(S_v)$是子集$S_v$的熵。

• 整个公式含义：信息增益等于数据集$S$划分前的熵$H(S)$减去划分后各个子集的熵的加权和

• 如果信息增益越大，说明使用属性$A$对数据集$S$进行划分后，数据集的不确定性减少得越多，那么属性$A$就越适合作为当前节点的划分属性。

• 选择信息增益最大的特征作为当前节点的分裂特征。

算法步骤

1. 初始化：从根节点开始，包含所有训练数据。
2. 终止条件：
   • 当前节点所有样本属于同一类别 → 标记为叶子节点。
   • 无剩余特征可用 → 标记为多数类别的叶子节点。
3. 特征选择：
   • 计算每个特征的信息增益。
   • 选择信息增益最大的特征作为分裂依据。
4. 递归分裂：
   • 按选定特征的每个取值生成子节点。
   • 对每个子节点递归重复步骤2-4。

示例：天气预测是否打网球

数据集：

天气	温度	湿度	风力	打网球？
晴	高	高	弱	否
晴	高	高	强	否
多云	高	高	弱	是
雨	中	高	弱	是
雨	低	正常	弱	是
雨	低	正常	强	否

步骤1：计算初始熵
目标列“打网球？”的分布：3个“否”，3个“是”。
$$H(S)=-\left(\frac{3}{6}{\log }_2\frac{3}{6}+\frac{3}{6}{\log }_2\frac{3}{6}\right)=1.0$$

步骤2：计算各特征的信息增益

• 湿度：

  • 高湿度（3条）：2“否”，1“是” → 熵=0.918
  • 正常湿度（3条）：1“否”，2“是” → 熵=0.918
  • 条件熵：$\frac{3}{6}\times 0.918+\frac{3}{6}\times 0.918=0.918$
  • 信息增益：$1.0-0.918=0.082$

• 天气：

  • 晴（2条）：2“否” → 熵=0
  • 多云（1条）：1“是” → 熵=0
  • 雨（3条）：1“否”，2“是” → 熵=0.918
  • 条件熵：$\frac{2}{6}\times 0+\frac{1}{6}\times 0+\frac{3}{6}\times 0.918=0.459$
  • 信息增益：$1.0-0.459=0.541$（最大）

步骤3：选择“天气”作为根节点

• 晴：直接标记为“否”（纯度100%）。
• 多云：直接标记为“是”。
• 雨：继续递归分裂（按“湿度”或“风力”）。

ID3的局限性

缺点	说明
偏好多值特征	倾向于选择取值多的特征（如“ID”），导致过拟合。
无法处理连续值	只能处理离散特征，需预先离散化。
缺失值敏感	需预处理缺失值（删除或填充）。
无剪枝机制	容易生成复杂树，泛化能力差。

应用场景

• 简单分类问题：特征均为离散型，数据量较小。
• 规则解释需求：如医疗诊断（症状→疾病类型）。

代码示例（Python伪代码）

class ID3DecisionTree:
    def fit(self, X, y):
        # 递归终止条件
        if 所有y相同: return 叶子节点(y[0])
        if 无剩余特征: return 叶子节点(多数类(y))
        
        # 选择最佳特征
        best_feature = argmax([信息增益(X[:,i], y) for i in features])
        
        # 按特征取值递归分裂
        tree = {best_feature: {}}
        for value in X[:,best_feature].unique():
            sub_X = X[X[:,best_feature] == value]
            sub_y = y[X[:,best_feature] == value]
            tree[best_feature][value] = self.fit(sub_X, sub_y)
        return tree

总结：ID3是决策树的基础算法，通过信息增益选择特征，生成直观的规则树，但需注意其局限性和改进算法的优势。

3.2 C4.5算法

C4.5 是ID3算法的改进版本，由Ross Quinlan于1993年提出，旨在解决ID3的局限性（如无法处理连续值、缺失值、过拟合等）。它通过引入信息增益率、连续值离散化、缺失值处理和剪枝技术，显著提升了决策树的泛化能力和实用性，成为经典的分类算法之一。

核心改进与原理

1. 信息增益率（Gain Ratio）

针对ID3偏好取值多特征的缺陷（如“ID”字段），C4.5用信息增益率替代信息增益：
$$\text{GainRatio}(S,A)=\frac{\text{IG}(S,A)}{\text{SplitInfo}(A)}$$

• $\text{GainRatio}(S,A)$：
  • 表示使用属性 $A$ 对数据集 $S$ 划分的增益率。它是我们最终要计算的衡量指标，用于评估属性 $A$ 作为划分属性的优劣程度。
• $\text{IG}(S,A)$：
  • 代表信息增益（Information Gain）。
  • 其计算公式为 $IG(S,A)=H(S)-{\sum }_{v\in \text{Values}(A)}\frac{|S_v|}{|S|}H(S_v)$。
  • 如前面所解释，信息增益衡量的是使用属性 $A$ 对数据集 $S$ 进行划分后，不确定性减少的程度。
• $\text{SplitInfo}(A)$：
  • 称为分裂信息（Split Information）。
  • 对于属性 $A$，其计算公式为 $\text{SplitInfo}(A)=-{\sum }_{v\in \text{Values}(A)}\frac{|S_v|}{|S|}{\log }_2\frac{|S_v|}{|S|}$。
  • 它表示按照属性 $A$ 划分数据集的纯度。
  • 对于属性$A$的所有可能取值$v$，计算每个取值对应的子集在数据集中所占比例与该比例取对数后的乘积，然后将这些乘积求和，并在前面加上负号。
  • 例如，如果一个属性的分裂信息值很低，说明该属性划分后的子集没有被划分成太多份
• 增益率的计算公式 $\text{GainRatio}(S,A)=\frac{\text{IG}(S,A)}{\text{SplitInfo}(A)}$ 的含义是，用信息增益除以分裂信息。
  • 通过这样的计算，当一个属性不仅能够带来较高的信息增益（使得数据集的不确定性大幅降低）
  • 而且其分裂信息不会过大（即不会因为属性取值过多而导致过度划分）时，该属性会有较高的增益率。

示例：
比如有10个数据，某个特征将其划分成10类，根据ID3算法得到的信息增益很大，但是由于这样会导致分裂信息也很大，因此它的信息增益率并不会很大，因此，C4.5算法避免了过度划分。

2. 连续值处理

C4.5通过二分法将连续特征离散化：

1. 对连续特征的所有取值排序。
2. 选择相邻值的中间点作为候选分割点。
3. 计算每个候选点的信息增益率，选择最优分割点。

示例：
比如

温度	衣着
15	短袖
18	短袖
22	长袖
25	长袖

对温度特征（连续值）排序为[15, 18, 22, 25]，候选分割点为16.5、20、23.5。计算每个点的增益率，选择最优者。

3. 缺失值处理

C4.5支持缺失值（如“未知”或空值）的处理：

• 训练阶段：
  按特征值的已知比例分配权重，计算信息增益率。
• 预测阶段：
  将缺失样本同时分配到所有子节点，根据子节点权重综合结果。

---

3.3 cart

CART算法（分类与回归树）简介

CART（Classification and Regression Tree）由Leo Breiman等人于1984年提出，是一种基于树结构的机器学习算法，可用于分类和回归任务。它通过递归划分特征空间构建二叉树，最终通过剪枝优化模型，是决策树家族中最经典的算法之一。

核心特点

1. 二叉树结构：每个内部节点仅产生两个子节点（左分支和右分支），便于算法实现和复杂度控制。
2. 适用任务：
   • 分类任务：叶子节点为类别标签（通过多数表决法确定）。
   • 回归任务：叶子节点为连续值（通常取样本均值）。
3. 分裂准则：通过最小化不纯度（分类）或误差（回归）选择最优分裂特征和阈值。
4. 剪枝策略：通过后剪枝避免过拟合，提升泛化能力。

算法流程

1. 树的生成（递归划分）

• 输入：训练数据集、特征集合、停止条件（如节点样本数小于阈值、不纯度下降小于阈值等）。
• 步骤：
  1. 选择最优分裂特征和阈值：
     • 分类任务：计算节点的Gini不纯度（衡量数据混乱程度），选择分裂后Gini值最小的特征和阈值。
       $$\text{Gini}(p)=1-\sum _{k=1}^K{p}_k^2$$
       其中，$p_k$ 是节点中第 $k$ 类样本的比例。分裂后加权平均Gini为：
       $${\text{Gini}}_{\text{split}}=\frac{n_{\text{left}}}{n}{\text{Gini}}_{\text{left}}+\frac{n_{\text{right}}}{n}{\text{Gini}}_{\text{right}}$$
     • 回归任务：计算节点的平方误差，选择分裂后误差最小的特征和阈值。
       $$\text{MSE}=\sum _{i=1}^n(y_i-\bar{y}{)}^2$$
       其中，$\bar{y}$ 是节点样本的均值。
  2. 递归划分：对左右子节点重复上述过程，直到满足停止条件。

2. 剪枝（后剪枝为主）

• 目的：防止过拟合，简化树结构。
• 方法：
  • 代价复杂度剪枝（Cost-Complexity Pruning）：引入参数 $\alpha$ 平衡树的复杂度和训练误差，生成一系列子树，通过验证集选择最优子树。
  • 损失函数：$C_{\alpha }(T)=C(T)+\alpha |T|$，其中 $C(T)$ 是训练误差，$|T|$ 是叶子节点数。

关键细节

• 特征处理：
  • 支持连续特征（通过二分法寻找最优分裂阈值）和离散特征（划分为“是/否”两个子集）。
  • 缺失值处理：通过替代特征或样本权重分配近似分裂。
• 停止条件：
  • 节点样本数小于最小阈值。
  • 所有样本属于同一类别（分类）或误差足够小（回归）。
  • 无特征可分裂。

优缺点

优点	缺点
1. 结构直观，可解释性强。 2. 支持分类和回归，鲁棒性较好。 3. 能处理非线性数据和特征交互。	1. 单棵树易过拟合，需剪枝或集成（如随机森林）。 2. 对类别不平衡数据敏感（分类时需调整权重）。 3. 特征分裂依赖局部最优，可能错过全局最优解。

应用场景

• 分类问题：如垃圾邮件分类、疾病诊断。
• 回归问题：如房价预测、销量估计。
• 集成学习：作为基学习器（如随机森林、GBDT），提升模型性能。

与其他决策树算法对比

• ID3/C4.5：多叉树，分类专用，使用信息增益/增益率（C4.5），CART用Gini指数，且为二叉树。
• CART vs 回归树：回归树直接优化平方误差，分类树优化Gini不纯度，两者共享树结构和剪枝逻辑。

总结

CART算法通过简洁的二叉树结构和明确的分裂准则，成为决策树领域的基础算法。尽管单棵CART容易过拟合，但其思想为随机森林、梯度提升等集成方法奠定了基础，至今在机器学习中广泛应用。实际使用时需注意剪枝和特征工程，以平衡模型复杂度和泛化能力。

4. 构建步骤（以分类为例）

1. 计算原始数据纯度：使用熵或基尼系数。
2. 特征选择：计算每个特征的信息增益（或增益率/基尼减少量）。
3. 分裂节点：选择最佳特征将数据划分为子集。
4. 递归生成子树：对每个子集重复上述过程，直到：
   • 节点样本全部属于同一类
   • 特征用完或达到停止条件（如最大深度）

---

5. 示例：天气预测打网球

数据集（共14条记录）：

天气	温度	湿度	风力	打网球
晴	高	高	弱	否
晴	高	高	强	否
多云	高	高	弱	是
雨	中	高	弱	是
雨	低	正常	弱	是
雨	低	正常	强	否
多云	低	正常	强	是

步骤1：计算初始熵

• 目标列"打网球"：9次"是"，5次"否"
• 熵 = -(9/14)log₂(9/14) - (5/14)log₂(5/14) ≈ 0.940

步骤2：计算各特征信息增益

• 湿度特征：
  • 高湿度样本（7条）：3"是"，4"否" → 熵=0.985
  • 正常湿度样本（7条）：6"是"，1"否" → 熵=0.592
  • 条件熵 = (7/14)*0.985 + (7/14)*0.592 = 0.788
  • 信息增益 = 0.940 - 0.788 = 0.152

同理计算其他特征：

• 风力增益=0.048
• 天气增益=0.246
• 温度增益=0.029

步骤3：选择增益最大的"天气"作为根节点

步骤4：递归构建子树

• 对"天气=晴"分支（2"否"）直接标记为"否"
• 对"天气=雨"分支继续按"风力"分裂…

最终决策树：

天气
├─ 晴 → 否
├─ 多云 → 是
└─ 雨
   ├─ 风力=弱 → 是
   └─ 风力=强 → 否

---

6. 防止过拟合的方法

• 预剪枝：提前停止分裂（如设置最大深度=3）
• 后剪枝：生成完整树后剪去冗余分支
• 设置最小样本数：节点样本数<5则停止分裂

---

7. 优缺点对比

优点	缺点
可视化强，解释性好	容易过拟合复杂数据
处理数值/类别特征	对类别不平衡敏感
无需特征缩放	贪婪算法可能局部最优

---

8. 实际应用场景

• 金融：贷款风险评估（收入/职业→是否放贷）
• 医疗：基于症状和化验结果的疾病诊断
• 零售：客户分群（购买历史→促销响应预测）

通过以上示例和原理分析，决策树将复杂的决策过程转化为直观的规则树，是入门机器学习的核心模型之一。