决策树¶

概览¶

决策树是一种非参数的监督学习方法，常用于分类和回归任务。

在分类问题中，决策树可以认为是 if - then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。但模型存在容易过拟合、容易局部最优等问题

决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。

特征选择¶

特征选择的目的是找到能够最有效地将数据集划分为更纯净子集的特征。

信息熵¶

在信息论中，熵(Entropy)是表示随机变量不确定性的度量。在决策树中，用熵来衡量数据集 $D$ 的纯度。熵越小，数据集的纯度越高（即不确定性越小）。假设数据集中有 $K$ 个类别，第 $k$ 类样本所占的比例为 $p_k$。 $$ H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k $$ 约定若 $p_k = 0$，则 $p_k \log_2 p_k = 0$。

条件熵¶

条件熵(Conditional Entropy) $H(D|A)$ 表示在已知特征 $A$ 的条件下，数据集 $D$ 的不确定性。假设特征 $A$ 有 $V$ 个可能的离散取值 $\{a^1, a^2, \dots, a^V\}$，$D^v$ 是数据集 $D$ 中特征 $A$ 取值为 $a^v$ 的样本子集。 $$ H(D|A) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} H(D^v) $$ 其中 $\frac{|D^v|}{|D|}$ 是特征 $A$ 取值为 $a^v$ 的样本所占比例，$H(D^v)$ 是子集 $D^v$ 的信息熵。

信息增益¶

信息增益(Information Gain)表示由于特征 $A$ 的引入，使得数据集 $D$ 的不确定性减少的程度（即纯度的提升）。信息增益越大的特征，分类能力越强。 $$ \text{Gain}(D, A) = H(D) - H(D|A) $$ ID3 算法即使用信息增益作为特征选择的标准。

信息增益的不足: 信息增益准则对可取值数目较多的特征有所偏好。例如，如果一个特征是“样本编号”，每个样本在此特征上的取值都唯一，则该特征会使得条件熵 $H(D|A)$ 变得很小 (甚至为0)，从而获得极高的信息增益。但这样的特征对于预测新样本通常没有泛化能力。

信息增益率¶

为了克服信息增益偏向于选择取值较多特征的缺点，C4.5 算法引入了信息增益率(Information Gain Ratio)。它是在信息增益的基础上除以一个“分裂信息”(Split Information) 或称为特征 $A$ 的“固有值”(Intrinsic Value) $H_A(D)$。 $$ \text{GainRatio}(D, A) = \frac{\text{Gain}(D, A)}{H_A(D)} $$ 其中，分裂信息 $H_A(D)$ 定义为： $$ H_A(D) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} $$ 特征 $A$ 的取值越多，通常 $H_A(D)$ 的值会越大，从而对信息增益进行校正。

基尼指数¶

基尼指数 (Gini Index)也是衡量数据集不纯度的指标，常用于 CART (Classification and Regression Trees) 算法。它表示从数据集中随机抽取两个样本，其类别标记不一致的概率。基尼指数越小，数据集纯度越高。 $$ \text{Gini}(D) = \sum_{k=1}^{K} p_k (1-p_k) = 1 - \sum_{k=1}^{K} p_k^2 $$ 对于给定的特征 $A$，选择该特征进行划分后的基尼指数为各个子集基尼指数的加权平均。CART 算法选择使得划分后基尼指数最小的特征（即基尼增益 $\Delta \text{Gini}$ 最大）。

决策树生成¶

ID3 算法由 Ross Quinlan 提出，其核心是在决策树的每个节点上应用信息增益最大的准则进行特征选择，然后递归地构建决策树。

算法步骤¶

输入：训练数据集 $D$，特征集 $\mathcal{A}$，阈值 $\epsilon$ (或无阈值，直到无法再分)。输出：一棵决策树。

若 $D$ 中所有样本属于同一类别 $C_k$，则创建叶节点，标记为类别 $C_k$，返回。
若 $\mathcal{A}$ 为空集，或者 $D$ 中样本在 $\mathcal{A}$ 中所有特征上取值相同（无法进一步划分），则创建叶节点，标记为 $D$ 中样本数最多的类别，返回。
计算 $\mathcal{A}$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A^*$。

（(可选)如果 $A^*$ 的信息增益小于阈值 $\epsilon$，则创建叶节点，标记为 $D$ 中样本数最多的类别，返回）
对 $A^*$ 的每一个可能取值 $a_v^*$，将 $D$ 中 $A^*=a_v^*$ 的样本构成子集 $D_v$。
以 $D_v$ 为训练集，以 $\mathcal{A} \setminus \{A^*\}$ 为特征集，递归调用步骤 1-5，得到子树，并将子树连接到以 $A^*$ 为分裂特征的当前节点下对应 $a_v^*$ 的分支上。
返回生成的树。

ID3一些缺点，例如，信息增益准则倾向于选择取值数目较多的特征。同时，由于没有剪枝策略，生成的树可能过于复杂。并且算法没有内置机制处理数据中的缺失特征值。

为了克服信息增益偏向于选择取值较多特征的缺点，C4.5 算法引入了信息增益率。它是在信息增益的基础上除以一个“分裂信息”(Split Information) 或称为特征 $A$ 的“固有值”(Intrinsic Value) $H_A(D)$。

使用C4.5 算法，会在在步骤3处采用信息增益率。

决策树剪枝¶

决策树算法能递归地生成决策树，当特征较多的时候，确实可以获得非常精确的分类结果——但这会导致过拟合，无法很好地适应未知的数据。为了解决过拟合问题，提高决策树的泛化能力，剪枝 (Pruning) 技术应运而生。剪枝的本质是主动去掉决策树的一些分支，以降低模型的复杂度。

损失函数¶

决策树的剪枝往往采用极小化决策树整体的损失函数或代价函数来实现。

决策树的剪枝过程可以看作是优化一个包含两项的损失函数（或称为代价函数）。这个损失函数不仅考虑模型对训练数据的拟合程度（经验风险），还考虑模型的复杂度（结构风险）。

决策树学习的损失函数可以定义为： $$ C_\alpha(T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha|T| $$ 其中，信息熵为： $$ H_t(T) = -\sum_{k=1}^{K} \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t} \quad (5.12) $$ 用$C(T)$：表示模型对训练数据的拟合误差，它是所有叶节点上的不纯度（或错误）的加权和，则损失函数可以简化为 $$ C_\alpha(T) = C(T) + \alpha|T| \quad (5.14) $$

其中：$|T|$：表示树 $T$ 的叶节点数量，$\alpha$：是一个正则化参数 ($\alpha \ge 0$)，用于权衡模型的拟合优度与模型复杂度。

剪枝的目标就是找到一棵子树 $T_\alpha$，使得损失函数 $C_\alpha(T)$ 最小。

预剪枝¶

预剪枝(Pre-pruning)是在决策树的生长过程中，对每个节点在划分前先进行评估。如果当前节点的划分不能带来决策树泛化性能的提升，则决定停止划分，并将当前节点标记为叶节点。

判断方法： * 信息增益（率）阈值: 当划分后得到的信息增益（或信息增益率）小于某个预设阈值时，停止分裂。 * 节点样本数限制: 当节点内样本数量少于某个阈值时，停止分裂 * 树的深度限制: 当树的深度达到预设的最大深度时，停止生长。

预先剪枝停止了不必要的分裂，降低了过拟合的风险，同时开销较小

但预剪枝基于“贪心”策略，可能带有“短视”问题，可能会过早地终止这些有潜力的分支，导致欠拟合 (Underfitting)。

后剪枝¶

后剪枝(Post-pruning)是先从训练集生成一棵相对完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点（或该子树中最常用的某个分支）能带来决策树泛化性能的提升，则进行替换。

后剪枝有以下常用方法

降低错误剪枝 (Reduced Error Pruning - REP):
- 思想：使用一个独立的验证集。对于树中的每个非叶节点，尝试将其替换为一个叶节点（类别标记为该节点子树中最常见的类别）。
- 如果剪枝后的树在验证集上的准确率不低于原树（或更高），则执行剪枝。
悲观错误剪枝 (Pessimistic Error Pruning - PEP): (C4.5算法采用)
- 思想：不需要独立的验证集，而是基于训练数据本身来估计剪枝后的错误率。它对节点的错误进行“悲观”估计，即假设其错误率比在训练集上观察到的要高一些（通过引入连续性校正或统计置信区间）。
- 过程：对于一个子树，如果将其剪枝为一个叶节点后，该叶节点的错误率不比原子树的错误率高，则进行剪枝。
代价复杂度剪枝 (Cost-Complexity Pruning - CCP): (CART算法采用)
- 思想：该方法正是基于前面提到的损失函数 $C_\alpha(T) = C(T) + \alpha|T|$。
- 过程：
  1. 从完整生长的树 $T_0$ 开始，当 $\alpha=0$ 时，$T_0$ 是最优子树。
  2. 逐渐增大 $\alpha$，会得到一系列嵌套的最优子树序列 $\{T_0, T_1, \dots, T_m\}$，其中 $T_m$ 是根节点本身。对于每个内部节点 $t$，可以计算一个参数 $g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1}$，其中 $C(t)$ 是将节点 $t$ 作为叶节点时的误差，$C(T_t)$ 是以 $t$ 为根的子树 $T_t$ 的误差，$|T_t|$ 是子树 $T_t$ 的叶节点数。这个 $g(t)$ 实际上代表了剪掉子树 $T_t$ 后，每个叶节点平均带来的误差增加量。
  3. 在每一步，选择具有最小 $g(t)$ 值的节点进行剪枝，得到下一个子树。这个最小的 $g(t)$ 就是下一个 $\alpha$ 的临界值。
  4. 最终通过交叉验证 (Cross-Validation) 在独立的验证集上评估这一系列子树的性能，选择表现最好的子树作为最终的剪枝结果。

剪枝是控制决策树模型复杂度、防止过拟合、提高泛化能力的关键技术。