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

决策树简介

决策树算法在很多应用中被使用，呆板学习角逐中会经常见到，但在盛行病学范畴未受到太多关注。
决策树示例 —— 猫的分类

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

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

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

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

构建决策树的步骤

第一步：选择根节点特性

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

第二步：处理左分支

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

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

特性选择

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

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

决策树算法的发展与特点

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

纯度的概念

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

• 界说：熵（ENTRPY）是对样本数据杂质的度量。对于一组包含6个样本（3只猫和3只狗）的集合，界说
  
  为带有标签1（可理解为猫）的样本比例，在这个例子中
  
   。熵函数通常表现为
  
  ，此中横轴是
  
  （样本中猫的比例），纵轴是熵的值。当
  
  时，熵
  
  ，此时样本集最不纯（杂质值为1）。相反，当样本集要么满是猫要么全不是猫时，熵为0，即纯度最高。
  
• 示例：
  
  
  
  • 对于一组有5只猫和1只狗的样本，
    
    ，此时熵
    
     。
    
  • 当6个样本满是猫时，
    
    ，熵为0，阐明从3只猫3只狗（
    
    ）到6只满是猫（
    
    ），杂质从1减少到0，纯度增长。
    
  • 对于一组有2只猫和4只狗的样本，
    
    ，熵约为0.92\，该样本集比5只猫1只狗的样本集更不纯，因为它更接近
    
    的混合。
    
  • 当6个样本满是狗时，
    
    ，熵也为0。
    
  
  

熵函数的方程

是样本中猫的比例，若样本中

是猫，则

不是猫。界说

为不是猫的样本比例，

。熵函数

。
盘算熵时通常取以2为底的对数，这样能使曲线峰值等于1；若取以e为底的对数，函数只是垂直缩放但仍有用，不过数字表明起来较困难。当

或

等于0时，按照惯例

，能正确盘算出熵为0。
熵与逻辑损失的关系

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

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

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

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

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

信息增益的盘算及意义

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

信息增益的正式界说及公式

• 符号界说：
  
  表现到达左分支的样本比例，
  
  表现到达右分支的样本比例；
  
  表现左子树中标签为正（猫）的样本比例，
  
  表现右子树中标签为正的样本比例，
  
  表现根节点中标签为正的样本比例。
  
• 公式：信息增益界说为根节点的熵
  
   - 
  
   x 
  
  + 
  
  x
  
  。通过这个公式可以盘算与选择任何特定特性举行节点分割相关的信息增益，然后从全部可能的特性中选择能提供最高信息增益的特性，这样有望增长决策树左右子分支中数据子集的纯度。
  

笔者注

本篇整理了决策树和节点熵的有关概念，在盘算信息增益和选择分割特性后，接下来需要把这些内容整合到构建给定训练集决策树的整体算法中，这些在下一篇博客中整理。





免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。