《机器学习》笔记四

4.1 基本流程

决策树是一种直观、类似“问答式”的分类方法，其基本思想就是通过一系列简单的判断（例如“这个瓜的颜色是不是青绿？”、“这个瓜的根蒂形状如何？”）一步步把样本分类。

4.1.1 决策树的基本概念

树结构：决策树由“结点”和“分支”组成。
- 根结点：放着所有的样本，表示开始决策的起点。
- 内部结点：每个内部结点对应一个“属性测试”，例如“色泽是否青绿？”。
- 叶结点：当经过一系列属性测试后到达的结点，叶结点直接给出最终的分类结果，比如“好瓜”或“坏瓜”。
决策过程：从根结点开始，根据样本在各个属性上的取值，沿着相应的分支不断向下走，直到到达叶结点，这一路上问的问题就构成了一个“测试序列”。

4.1.2 决策树如何“学习”

决策树学习的目标是从训练数据中自动生成这样一棵树，使得它能对未见过的新样本也做出正确分类。整个过程采用了“分而治之”的策略，简单说就是“把问题不断地拆分”。

学习过程的基本步骤：

开始于所有数据的根结点：把所有训练样本放在一个结点里。
判断是否停止划分：
- 如果当前结点里的所有样本都属于同一类别，就不用再分了，直接把这个结点标记为该类别的叶结点。
- 如果当前结点中样本在所有属性上都取相同的值，或者没有属性可用来进一步划分，也就无法区分，那么就把这个结点作为叶结点，其类别由当前样本中数量最多的类别决定。
选择最佳的划分属性：
- 从当前可用的属性集合中，选择一个最能将样本“分开”的属性，这个过程类似于“找出最有区分度的问题”。
递归地构造子树：
- 根据所选属性的不同取值，把当前结点的样本分到不同的子结点。
- 对于每个子结点，再重复上述过程，即继续判断是否停止划分、选择最佳属性，然后递归构建决策树。
处理特殊情况：
- 如果某个分支没有样本（即当前测试结果下没有数据），通常会把该分支的叶结点类别设为父结点中样本最多的类别。

4.1.3 递归与“分而治之”

整个决策树的生成过程其实是一个递归过程，每次都把一个问题（即一个结点的样本分类问题）拆分成更小的问题（子结点上的分类问题），直到无法再拆分为止。

停止条件：
1. 当前结点的所有样本都属于同一类别（决策已完成）。
2. 没有更多的属性可以用来划分，或者样本在所有属性上的取值都一样（无法进一步区分）。
3. 当前结点没有样本（这时通常参考父结点的分布来决定类别）。

4.1.4 一个简单的例子

假设我们要判断“这是个好瓜吗？”，决策树可能会这样工作：

根结点：开始时考虑所有瓜。
第一个测试：判断瓜的“色泽”。如果是“青绿”，沿着一条分支；如果不是，则走另一条分支。
第二个测试：在“青绿”这一分支上，进一步判断“根蒂形态”。例如，如果根蒂是“蜷缩”的，就继续往下判断；否则，可能直接做出决策。
叶结点：最终在一条测试路径的尽头，给出判断结果，比如“好瓜”或“坏瓜”。

通过这种方式，决策树将复杂的分类问题拆分成一系列简单的判断，既符合人类直观的决策思路，又便于计算机通过递归自动生成模型。

一句话总结：

决策树就是通过不断提问（每个问题对应一个属性测试），把数据一步步拆分，直到每条路径（从根到叶）都能给出明确的分类结果，从而实现对新样本的判断。

4.2 划分选择

4.2.1 为什么需要选择划分属性？

在构建决策树时，我们希望通过不断地“提问”将数据拆分成纯度更高的子集。

纯度高：意味着一个子集中大部分样本都属于同一个类别。
目标：每次选择一个属性来划分数据，使得划分后每个分支中的数据“混乱度”降低，即更容易判断最终的类别。

4.2.2 什么是信息熵（Entropy）？

信息熵是用来衡量一个数据集“混乱”程度的指标。
计算公式为 $\text{Ent}(D) = -\sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k$ 其中， $p_k$ 是数据集中属于第 $k$ 类的比例。
直观理解：
- 如果一个数据集中各类别分布均匀，熵值高，说明数据很“混乱”；
- 如果大部分数据都来自同一类别，熵值低，说明数据很“纯”。

4.2.3 如何利用信息熵选择属性？

假设我们有一个数据集 $D$ 和一个候选属性 $a$ （这个属性可能有多个取值），我们用 $a$ 将 $D$ 分成 $V$ 个子集 $D^1, D^2, \ldots, D^V$ 。

对每个子集 $D^v$ 也能计算出其信息熵 $\text{Ent}(D^v)$ 。
然后，我们计算用属性 $a$ $a$ 划分前后的“信息变化”，称为信息增益：
$\text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \text{Ent}(D^v)$
- 意思：原始数据集的熵减去划分后各子集熵的加权平均值。
- 信息增益越大，说明用这个属性划分后数据的混乱度降低得越多，也就是子集更纯。

4.2.4 例子说明

以西瓜数据集为例：

整个数据集 $D$ 的熵约为 0.998（表示还挺混乱的）。
如果我们用“色泽”这个属性进行划分，会产生三个子集，每个子集的熵分别计算出来，再加权平均后减去原始熵，得到的信息增益约为 0.109。
类似地，可以计算其他属性的信息增益。
通常我们选择信息增益最大的属性作为当前节点的划分属性，从而得到最大的纯度提升。

4.2.5 信息增益的缺点与增益率的引入

问题：

某些属性如果取值太多（比如“编号”这种，每个样本都是唯一的），划分后每个子集可能只有一个样本，熵自然为 0，导致信息增益非常高。
但这样的划分没有意义，因为它不能推广到新的数据上，容易导致过拟合。

解决方法：增益率

增益率（Gain Ratio）就是用来修正这一问题的。
定义：
$\text{Gain\_ratio}(D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)}$
其中， $\text{IV}(a)$ 称为固有值，计算公式为
$\text{IV}(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$
直观理解：
- 固有值反映了属性 $a$ 本身的取值“分散”程度，取值越多，固有值通常越大。
- 增益率就是把信息增益除以固有值，这样能减少对那些取值很多但泛化能力差的属性的偏好。
C4.5 算法（一种著名的决策树算法）就是先用信息增益筛选出较好的候选属性，再用增益率来最终确定最佳属性。

4.2.6 基尼指数（Gini Index）

背景：
除了信息熵，CART决策树则常用另一种指标——基尼指数。
公式： $\text{Gini}(D)=1 - \sum_{k=1}^{|\mathcal{Y}|}p_k^2$
解释：
基尼指数反映了从数据集中随机抽取两个样本，类别不同的概率。数值越小，说明数据越纯。
划分选择：
当使用属性 (a) 划分数据时，对应的基尼指数为： $\text{Gini\_index}(D, a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}\text{Gini}(D^v)$ 在候选属性中，我们通常选择使得基尼指数最小的属性来作为最佳划分属性。

4.2.7 小结

决策树划分选择的关键在于找到那个能让子集变得“最纯”的属性。
信息熵用来衡量数据集的混乱程度；
信息增益衡量划分前后纯度提升的效果；
增益率进一步修正了信息增益在属性取值过多时可能带来的偏好问题。
通过这样的指标，我们能一步步构建出一棵具有良好泛化能力的决策树模型。

4.3 剪枝处理

剪枝是决策树防止“过拟合”的一种方法。简单来说，决策树在学习过程中可能会“学得太细”，把训练数据中的噪音和偶然性当成了规律，这样生成的树在面对新数据时往往表现不好。剪枝的目的就是在决策树生成后，有选择地删去一些不必要的分支，让树变得更简单、更泛化，从而提高新数据上的预测准确率。

下面用通俗易懂的语言讲讲两种主要的剪枝策略：预剪枝和后剪枝。

4.3.1 为什么要剪枝？

过拟合问题：如果决策树不断分裂直到每个叶结点只有极少量甚至单个样本，那么这棵树可能完全记住了训练数据的细节。但这些细节往往只适用于训练集，而不适用于新的数据。
目标：我们希望树的每个分支尽量概括一类数据，而不是仅仅记住训练集的特殊情况。剪枝就是通过减少不必要的分支，达到“去噪”和简化模型的效果。

4.3.2 预剪枝（Pre-pruning）

预剪枝的做法是在构建决策树的过程中，就提前阻止一些不必要的分支生长。步骤大致如下：

决策过程：在决策树生成时，每次在决定是否对当前结点进行进一步分裂前，先用一部分预留的“验证集”数据来估计，如果再分裂能否提高在新数据上的表现。
具体判断：
- 如果不分裂（即把当前结点直接作为叶结点）在验证集上的表现已经很好，
- 或者如果进一步分裂后反而使验证集的准确率降低，
那么就停止分裂，将当前结点直接标记为叶结点，并确定一个最终的类别（通常是该结点中样本最多的类别）。
优缺点：
- 优点：可以防止树分裂得过深，减少训练和测试时的计算开销；
- 缺点：有时一个看似没提升的分支，如果继续往下分裂可能会最终提高准确率，预剪枝的“贪心”决策可能会导致模型欠拟合。

4.3.3 后剪枝（Post-pruning）

后剪枝的做法是先让决策树完全生成，也就是把所有训练数据都划分完，然后再从树的底部开始，逐步检查是否可以简化部分树结构。步骤大致如下：

构建完整树：首先根据所有训练数据生成一棵完整的决策树，这棵树可能非常复杂，甚至过拟合。
自底向上剪枝：从最底层的非叶结点开始，逐个考察：
- 尝试把某个结点以及它下面的子树全部替换成一个叶结点。
- 用验证集数据评估，看看这样的替换是否能提高整体的泛化性能（也就是在新数据上的预测准确率）。
- 如果替换后性能更好，就保留这种剪枝；否则，就保留原来的子树。
优缺点：
- 优点：后剪枝能保留更多有用的分支，通常泛化性能更好，降低过拟合的风险；
- 缺点：需要先生成完整树，再进行反复验证和剪枝，计算量和时间开销会比较大。

4.3.4 一个直观的例子

假设我们用西瓜数据集来训练决策树：

初始情况：最初，我们生成了一个完整的决策树，树的每个叶结点可能都过于细化，导致在训练集上表现很好，但在预留的验证集上准确率很低（比如只有42.9%）。
预剪枝案例：
- 在生成树时，先用一个属性（例如“脐部”）进行分裂后，验证集的准确率提高到了71.4%，这说明这个分裂是有用的，于是保留这个分裂。
- 但是，当对某个结点继续分裂（比如用“色泽”进一步分裂）后，验证集的准确率反而下降了，这时预剪枝会阻止这个分裂，直接将这个结点作为叶结点。
后剪枝案例：
- 我们先生成一棵完整的树（可能在验证集上的准确率仍然很低，比如42.9%）。
- 然后，我们自底向上检查，比如对某个结点的子树进行剪枝后，验证集准确率从42.9%提升到了57.1%，那么就将该子树剪掉。
- 最终，经过多次剪枝后，整体验证集准确率提升到71.4%。

4.3.5 总结

剪枝的目的：通过删除那些在新数据上没有帮助甚至有害的分支，简化决策树，防止过拟合。
预剪枝：在构造树时就提前判断，若分裂后没有提升性能则停止分裂，优点是节省计算时间，但可能错过一些后续有用的信息，存在欠拟合风险。
后剪枝：先构建完整树，然后再逐步删减分支，通常能保留更多有用信息，泛化性能更好，但计算开销更大。

4.4 连续与缺失值

4.4.1 连续值的处理

为什么要处理连续值？

问题：前面讨论的决策树主要针对离散属性（例如“色泽”只有“青绿”、“乌黑”、“浅白”几种取值），但现实中很多属性是连续的（例如“密度”、“含糖率”可以是任意小数）。
挑战：连续属性可能有无穷多个不同取值，不能直接按照每个取值来分支，这样会导致树枝过多且没有实际意义。

如何处理连续属性？

二分法（二元划分）：一种简单而常用的方法是把连续属性进行离散化，方法是选择一个“阈值”（或称“划分点”）将数据分为两部分。
1. 排序：先把属性的所有取值从小到大排序。例如，属性 a 在数据集 D 中有 n 个不同的取值： $a^1, a^2, \ldots, a^n$ 。
2. 候选划分点：在相邻两个值之间取中点作为候选划分点。也就是说，候选集合为
  $T_a = \left\{\frac{a^i + a^{i+1}}{2}\ \bigg|\ 1\leq i\leq n-1\right\}.$
3. 评估每个划分点：对于每个候选阈值 t，将数据集分成两部分：
  - $D_t^-$ ：属性 a 的值小于或等于 t 的样本，
  - $D_t^+$ ：属性 a 的值大于 t 的样本。
  接下来就可以计算使用该划分所获得的信息增益（类似于离散属性的划分，只不过这里是针对二分后的两个子集）。
4. 选择最佳划分点：遍历所有候选点，选取使信息增益最大的 t。这个 t 就是当前连续属性最优的分割点。
举个例子：在西瓜数据集中，我们给每个样本增加了“密度”和“含糖率”两个连续属性。通过上述方法，我们得到例如“密度”的候选划分点集合，然后计算出在某个划分点（比如0.381）处的信息增益最大；同理，“含糖率”也找到最优划分点（比如0.126）。最终，决策树会根据这些最优划分点来进行节点划分。
注意：一个连续属性可以在决策树的不同节点上多次使用，每次划分的阈值可以不同。

4.4.2 缺失值的处理

为什么要处理缺失值？

问题：现实数据中常常存在缺失值，比如某些样本在某些属性上的值未知。如果直接丢弃这些样本，会浪费大量信息。
目标：在生成决策树时，尽量利用所有样本，同时合理处理那些缺失了部分属性值的样本。

如何处理缺失值？

我们需要解决两个问题：

属性选择时：当某个属性有部分样本缺失时，如何评估这个属性的优劣？
样本分支时：当某个样本在划分属性上缺失值，如何决定将它归入哪一个分支？

(1) 属性选择

只用非缺失样本：首先，针对某个属性 a，我们只使用那些在 a 上没有缺失值的样本，记为 $\tilde{D}$ 。
计算比例：
- 用 $\rho$ 表示 $\tilde{D}$ 占整个数据集 D 的比例，即：
  $\rho = \frac{\text{非缺失样本的权重和}}{\text{总样本的权重和}}$ 。
- 对于 $\tilde{D}$ 内不同类别和不同属性取值，也计算相应的比例。
调整信息增益：最后，针对属性 a 的信息增益就按非缺失样本的结果计算，再乘以 $\rho$ 进行缩放。这样可以反映出由于缺失值带来的不确定性。公式变为： $\text{Gain}(D, a) = \rho \times \left(\text{Ent}(\tilde{D}) - \sum_{v=1}^{V} \tilde{r}_v \text{Ent}(\tilde{D}^v)\right),$ 其中 $\tilde{r}_v$ 是在属性 a 上取某个值 $a^v$ 的样本比例。

(2) 样本划分

样本属性已知：如果一个样本在属性 a 上有值，就按该值划入对应的子结点，权重不变。
样本属性缺失：如果样本 x 在属性 a 上缺失，则不舍弃该样本，而是将 x 同时“分配”到所有分支中，并为每个分支分配一个比例权重。例如，假如属性 a 的各个取值在非缺失样本中出现的比例分别为 $\tilde{r}_1, \tilde{r}_2, \ldots, \tilde{r}_V$ ，那么将样本 x 按照这些比例分别加入到每个对应的子结点中。这样，相当于“模糊”地把 x 分配到多个分支，保证不因缺失而丢失信息。
实际应用：C4.5算法就采用了上述策略处理缺失值。这样既保证了属性选择时的合理性，又能在划分过程中充分利用那些部分缺失数据的样本。

4.4.3 小结

连续属性：采用二分法离散化连续值，先排序、选取候选阈值，再通过信息增益选择最佳的划分点。
缺失值：在属性选择时只考虑有值的样本，并用一个比例因子调整；在划分时，将缺失值样本按照各个分支的比例“分摊”到各子结点中。

4.5 多变量决策树

4.5.1 传统（单变量）决策树的特点

单变量决策树在每个内部结点只使用一个属性来做判断。例如，如果你只有“密度”或者“含糖率”这两个属性，那么决策树每次只能根据“密度是否大于某个值”或者“含糖率是否大于某个值”来分数据。
这种分法产生的决策边界都是轴平行的，也就是说，分割线总是垂直或水平的（在二维情况下），就像在坐标图上划直线一样。
优点：这种方法简单直观，每个判断都直接对应某个属性的取值。
缺点：如果真实的分类边界并不是严格的水平或垂直线，单变量决策树可能需要用很多次分割才能近似真实边界，从而生成很复杂的树，预测时也会比较耗时。

4.5.2 多变量决策树的思想

多变量决策树允许在一个结点上同时使用多个属性进行判断，也就是说，不再只判断某个属性是否大于某个值，而是根据属性的线性组合来进行判断。
每个内部结点会建立一个形如 $w_1a_1 + w_2a_2 + \cdots + w_da_d = t$ 的线性模型，其中 $a_1, a_2, \ldots, a_d$ 是各个属性， $w_1, w_2, \ldots, w_d$ 是对应的权重， $t$ 是阈值。
这样的决策规则可以产生斜的分割边界，也称为斜划分，不再局限于水平或垂直的分割线。

4.5.3 多变量决策树的优势

简化决策树结构：由于斜划分能更直接地贴近真实分类边界，多变量决策树往往可以用较少的分割就达到较好的分类效果。
减少分支：在某些情况下，一条斜线就能把不同类别的数据很好地分开，而单变量方法可能需要连续的多个水平和垂直分割来逼近这条斜线。
更好的近似复杂边界：当真实数据的分类边界比较复杂时，多变量决策树更容易找到一个简单而有效的分割平面。

4.5.4 举个例子

以西瓜数据集为例，假设只有两个属性——“密度”和“含糖率”，数据点在二维平面上散布。
如果使用单变量决策树，每个分割只看一个属性，分割线只能是垂直或水平的，这可能需要多个分割才能形成一条近似真实边界的曲线。
而多变量决策树可以直接利用“密度”和“含糖率”的线性组合来形成一条任意角度的直线分割（斜划分），这样就更容易将“好瓜”和“坏瓜”分开，而且树的结构也更简单。

4.5.5 总结

传统决策树：只使用单个属性分裂，生成的分类边界都是轴平行的，简单但可能需要很多分割来逼近复杂边界。
多变量决策树：允许在结点上使用多个属性的线性组合进行判断，能产生斜划分，通常可以更简洁地逼近复杂的分类边界，降低树的复杂度，但同时可能牺牲部分直观性和可解释性。

Ryo's blog