吴恩达深度学习复盘(16)决策树|节点纯度与熵-EW帮帮网

决策树简介

决策树算法在很多应用中被使用，机器学习比赛中会经常见到，但在流行病学领域未受到太多关注。

决策树示例 —— 猫的分类

以经营猫收养中心为例，通过动物的耳朵形状、脸型、是否有胡须等特征，来训练一个分类器判断动物是否为猫。数据集包含 10 个训练样本，其中 5 只猫和 5 只狗，输入特征为 X、R、B 三列（分别对应耳朵形状、脸型、是否有胡须），目标输出是判断该动物是不是猫（标签为 1 或 0）。这些特征是分类值，即只取几个离散值，如耳朵形状为尖或软，脸型为圆或不圆，胡须为有或无，这是一个二元分类任务。

决策树的定义和结构

决策树是在训练数据集后学习算法输出的模型，形似一棵树。树中的每个椭圆或矩形称为一个节点，树的根在上面，叶子在下面（类似于室内悬挂植物）。树的最顶端节点是根节点，除了底部的盒子外，其他椭圆形节点称为决策节点，它们会查看特定的特征，并根据特征的值决定沿着树的左分支或右分支向下走。底部的矩形盒子节点称为叶节点，它们做出预测。

决策树的分类过程

以一个新的测试样本（猫，耳朵形状尖、脸型圆、有胡须）为例，从根节点开始，查看根节点内的特征（耳朵形状），根据样本中耳朵形状的值（尖），沿着左分支走，到达下一个节点。再查看该节点对应的特征（脸型），样本脸型为圆，继续沿着相应箭头向下，最后到达叶节点，叶节点推断这是一只猫并做出预测。

不同决策树的比较

不同的决策树在训练集、交叉验证集和测试集上的表现有所不同。决策树学习算法的任务就是从所有可能的决策树中，选择一个在训练集上表现良好，并且能很好地推广到新数据（如交叉验证集和测试集）的决策树。

建立决策树

构建决策树的步骤

第一步：选择根节点特征

给定包含猫和狗的训练样本集，决策树学习的首要步骤是确定根节点使用的特征。假设选择耳朵形状特征，那么会依据该特征的值对所有十个训练样本进行划分，将耳朵形状为 “尖” 的五个样本移到左边，耳朵形状为 “软” 的五个样本移到右边。

第二步：处理左分支

专注于左分支，决定在该分支放置的节点以及用于分割的特征。假设选择脸型特征，对左分支的五个样本根据脸型特征的值进一步划分，把四个圆脸的样本移到左边，一个非圆脸的样本移到右边。此时发现左边四个样本都是猫，不再继续分裂，将其作为叶节点并做出 “是猫” 的预测；右边样本都不是猫（都是狗），创建叶节点预测 “不是猫” 。

第三步：处理右分支

在决策树的右分支重复类似过程。假设选择胡须特征，对右分支的五个样本根据胡须是否存在进行划分。划分后发现左右两边的节点要么全是猫，要么全不是猫，即达到了 “纯度”，于是创建叶节点分别做出 “是猫” 和 “不是猫” 的预测。

构建决策树的关键决策

特征选择

在每个节点（包括根节点、左分支和右分支的节点）都需要决定使用哪个特征进行分割。选择的目标是使分割后的左右子分支上的标签纯度尽可能高，纯度意味着子集中尽可能接近全是猫或全是狗。例如，若有 “动物是否有猫的 DNA” 这样的特征（实际没有），在根节点使用它进行分割，会使左右子集完全纯（一边全是猫，一边全不是猫）。而实际只有耳朵形状、脸型和胡须等特征，决策树学习算法需要在这些特征中选择能使左右子分支标签纯度最高的特征。下一个关于熵的视频将讨论如何估计不纯度以及如何最小化不纯度。

停止分裂的时机

纯度标准：当节点中的样本要么全是猫，要么全是狗（即达到 100% 的纯度）时，自然地创建叶节点并做出分类预测。
最大深度限制：可以设定决策树的最大深度作为参数，如果继续分割节点会使树的深度超过这个最大值，则停止分裂。节点的深度是指从根节点到达该特定节点所需经过的边的数量，根节点深度为 0，其下一层节点深度为 1，再下一层为 2，以此类推。限制树的深度可以防止树过于复杂，避免过拟合。
纯度分数提升标准：如果分割节点后纯度分数（实际上是不纯度的减少）的提升低于某个值，即分割对纯度的改善不明显，为了保持树较小并降低过拟合风险，可能会停止分裂。
样本数量阈值：如果节点中的样本数量低于某个阈值，例如在根节点按脸型特征分割后，右分支只有三个训练样本（一只猫和两只狗），为避免过度分割，可能决定不再继续分割，而是创建叶节点并做出 “不是猫” 的预测。

决策树算法的发展与特点

决策树算法是经过多位研究人员逐步改进发展而来的，不同研究人员提出了不同的改进方法，如不同的分裂标准和停止分裂的条件等。这使得算法在实际应用中表现良好，但从实现细节上看，感觉有很多不同部分和复杂的决策方式。虽然算法看似复杂凌乱，但各个部分组合起来形成了一个非常有效的学习算法。

熵与节点纯度

纯度的概念

如果样本集全是猫或全不是猫（即单类），则纯度很高。但当样本集处于两者之间，即存在不同类别的混合时，需要一种方法来量化其纯度。

熵的定义及示例

定义：熵（ENTRPY）是对样本数据杂质的度量。对于一组包含6个样本（3只猫和3只狗）的集合，定义 $p_1$ 为带有标签1（可理解为猫）的样本比例，在这个例子中 $p_1 = 3/6 = 0.5$ 。熵函数通常表示为 $H(p)$ ，其中横轴是 $p_1$ （样本中猫的比例），纵轴是熵的值。当 $p_1 = 0.5$ 时，熵 $H(p_1) = 1$ ，此时样本集最不纯（杂质值为1）。相反，当样本集要么全是猫要么全不是猫时，熵为0，即纯度最高。
示例：
- 对于一组有5只猫和1只狗的样本， $p_1 = 5/6 \approx 0.83$ ，此时熵 $H(p) \approx 0.65$ 。
- 当6个样本全是猫时， $p_1 = 6/6 = 1$ ，熵为0，说明从3只猫3只狗（ $p_1 = 0.5$ ）到6只全是猫（ $p_1 = 1$ ），杂质从1减少到0，纯度增加。
- 对于一组有2只猫和4只狗的样本， $p_1 = 2/6 = 1/3$ ，熵约为0.92\，该样本集比5只猫1只狗的样本集更不纯，因为它更接近 $50 - 50$ 的混合。
- 当6个样本全是狗时， $p_1 = 0$ ，熵也为0。

熵函数的方程

$p_1$ 是样本中猫的比例，若样本中 $2/3$ 是猫，则 $1/3$ 不是猫。定义 $p_0$ 为不是猫的样本比例， $p_0 = 1 - p_1$ 。熵函数 $H(p_1) = -p_1 \log_2(p_1) - p_0 \log_2(p_0) = -p_1 \log_2(p_1) - (1 - p_1) \log_2(1 - p_1)$ 。

计算熵时通常取以2为底的对数，这样能使曲线峰值等于1；若取以e为底的对数，函数只是垂直缩放但仍有效，不过数字解释起来较困难。当 $p_1$ 或 $p_0$ 等于0时，按照惯例 $0 \log(0) = 0$ ，能正确计算出熵为0。

熵与逻辑损失的关系

熵的定义与之前学过的逻辑损失的定义相似，这有其数学原理，但在本课程中不深入讨论，在构建决策树时应用熵的公式即可。

总结

熵函数是衡量样本数据杂质程度的指标，其值从0上升到1再下降到0，是样本中正例（如猫）比例的函数。还有其他类似的函数，如 GENI 标准，也可用于构建决策树。为简单起见，文章中重点关注熵准则，其适用于大多数应用。

决策树特征选择

构建决策树时特征选择需要通过熵和信息增益的方式处理，如何确定在决策树节点上使用哪个特征进行分割是关键所在。

特征选择的依据

在构建决策树时，每个节点选择分割特征的方法是基于该特征能减少熵（即减少杂质或最大化纯度）。在决策树学习中，熵的减少被称为信息增益。

计算信息增益的示例

以识别猫为例：在构建识别猫的决策树的根节点时，考虑三个可能的分割特征：耳朵形状、脸型和胡须特征。
- 耳朵形状特征：若按耳朵形状特征分割，左右分支各有5个样本，左边4只猫， $p_1 = 4/5 = 0.8$ ；右边1只猫， $p_1 = 1/5 = 0.2$ 。应用熵公式计算，左右分支的熵均约为 $0.72$ 。
- 脸型特征：若按脸型特征分割，左边7个样本中有4只猫， $p_1 = 4/7$ ；右边3个样本中有1只猫， $p_1 = 1/3$ 。计算得左右分支的熵分别约为 $0.99$ 和 $0.92$ ，杂质度比按耳朵形状特征分割时高。
- 胡须特征：若按胡须特征分割，左边 $p_1 = 3/4$ ，右边 $p_1 = 2/6$ ，并给出相应的熵值。
加权平均的必要性：
为了比较这三种特征选择的效果，不能仅仅观察熵值，而需要取加权平均。因为一个节点中包含很多高熵的样本比只有几个高熵样本的情况更糟糕，即熵作为杂质的度量，数据集越大且越不纯，情况越差。所以要将左右分支的熵合并为一个数，通过取加权平均来实现，权重取决于进入左右分支的样本数量。
计算加权平均熵：
以耳朵形状特征为例，10个样本中有5个去了左分支，5个去了右分支，则加权平均熵为 $5/10 \times 0.72 + 5/10 \times 0.72$ 。同理可计算脸型特征和胡须特征分割时的加权平均熵。
选择分割特征的方法：选择加权平均熵最小的特征作为分割特征，即选择能使左右分支平均加权熵最低的特征。

信息增益的计算及意义

计算方式的调整：在实际构建决策树时，为遵循惯例，不直接计算加权平均熵，而是计算与不进行分割时相比熵的减少量。回到根节点，最初有5只猫和5只狗， $p_1 = 5/10 = 0.5$ ，根节点的熵 $H(0.5) = 1$ 。
信息增益的定义：计算分割后左右分支的熵与根节点熵的差值，这个差值就是信息增益。例如，按耳朵形状特征分割时信息增益的计算结果是0.28，脸型特征是0.03，胡须特征是0.12。这些信息增益衡量了由于分割导致的熵减少量，因为根节点熵最初为1，分割后熵降低，两者的差值就是熵的减少量。
信息增益的作用：信息增益用于决定是否继续分割。如果信息增益的减少量太小，低于阈值，就可能会决定不再分割，因为这可能只是不必要地增加树的大小并冒着过拟合的风险。在上述例子中，按耳朵形状特征分割时熵的减少量最大，所以会选择在根节点按耳朵形状特征进行分割。

信息增益的正式定义及公式

符号定义： $W_{left}$ 表示到达左分支的样本比例， $W_{right}$ 表示到达右分支的样本比例； $P_{left}$ 表示左子树中标签为正（猫）的样本比例， $P_{right}$ 表示右子树中标签为正的样本比例， $P_{root}$ 表示根节点中标签为正的样本比例。
公式：信息增益定义为根节点的熵 $H(P_{root})$ - $W_{left}$ x $H(P_{left})$ + $W_{right}$ x $H(P_{right})$ 。通过这个公式可以计算与选择任何特定特征进行节点分割相关的信息增益，然后从所有可能的特征中选择能提供最高信息增益的特征，这样有望增加决策树左右子分支中数据子集的纯度。