前言

假设你正在运营一个猫领养中心，你需要训练一个分类器以便快速判断一个动物是否是猫

这里有10个训练样本，每个样本都关联了一些关于动物耳朵形状、脸型、是否有胡须的特征以及这个动物是否是猫
第一个样本有尖耳朵、圆脸、有胡须、并且它是一只猫
第二个样本有垂耳朵，脸型不是圆的，有胡须，这也是一只猫，以此类推，其余样本也是如此

这个数据集中有五只猫和五只狗，输入特征x是这三列，想要预测的目标输出y是最后一列，即这个动物是否是猫
在这个例子中，特征值x只取几个离散的值。耳朵形状要么是尖的，要么是垂的，脸型要么是圆的，要么不是圆的，胡须要么存在，要么不存在，这是一个二分类任务，因为标签也是1或0。
目前，每个特征 x 1、x2和 x3 只取两个可能的值

所以什么是决策树

这里是一个决策树学习算法后得到的模型示例
这些椭圆形或矩形中的每一个都称为树中的节点。
这个模型的工作方式是如果你有一个新的测试样本。这里有一只猫，耳朵形状是尖的，脸型是圆的，胡须存在。这个模型将通过以下方式查看这个样本并做出分类决策:
从树的最顶端节点开始,这被称为树的根节点，我们将查看写在内的特征，即耳朵形状，根据这个样本的耳朵形状的值，我们将向左或向右移动。这个样本的耳朵形状的值是尖的，因此，左分支向下移动，并最终到达这里的椭圆形节点。我们将沿着树的然后我们查看这个样本的脸型，结果是圆的，因此我们将沿着这里的箭头向下移动，算法将推断出它认为这是一只猫，你到达这个节点，算法将预测这是一只猫。
这些节点，即所有这些椭圆形，但不包括底部的矩形，都称为决策节点。它们是决策节点，因为它们查看特定的特征，然后根据特征的值，决定你是向左还是向右沿着树走。最后，这些底部的节点，这些矩形框，称为叶节点，它们做出预测。
其他例子：根节点开始，根据一个例子的耳形，你向左或向右走。如果耳形是尖的，那么你查看胡须特征，根据胡须是否存在，你再次向左或向石走，并分类猫与非猫
在这些不同的决策树中，有些在训练集或交又验证和测试集上表现更好，有些则表现更差。
因此，决策树学习算法的任务是，从所有可能的决策树中尝试挑选一个在训练集上表现良好，并且理想情况下也能很好地泛化到新数据的树。
我们先看看决策树是如何构建的

构建决策树的过程，给定一个训练集，有几个步骤。

给定一个包含10个猫和狗的训练集，决策树学习的第一步是我们必须决定在根节点使用什么特征。
假设我们决定选择耳形特征作为根节点的特征。这意味着我们将决定查看所有的训练样本，所有10个训练样本，并根据耳形特征的值将它们分割。
特别是，让我们挑出5个有尖耳朵的例子并将它们移到左边，挑出5个有垂耳的例子并将它们移到右边，第二步是专注于左部分，或者有时称为决策树的左分支决定在那里放置什么节点，特别是我们想要分割什么特征或者我们想要使用什么特征。假设你决定在那里使用脸形特征。我们现在要做的是将这5个例子根据它们的脸形值分成两个子集，我们将这5个例子中的4个圆脸形的例子移到左边，将1个非圆脸形的例子移到右边。最后，我们注意到这4个例子都是猫。
我们创建一个叶节点，预测到达该节点的都是猫。在这里，0个例子是猫。因此，我们可以在这里创建一个叶节点，预测不是猫。在完成了决策树左部分或左分支的工作后，我们现在在右部分或右分支重复类似的过程，并专注于这5个例子，其中包含1只猫和4只狗。
我们在这里选择一些特征来进一步分割这5个例子。如果我们最终选择了胡须特征，我们将根据胡须的存在与否来分割这5个例子，像这样。你注意到左边的一个例子是猫，而右边的4个例子都不是猫。
因此，每个节点都是全是猫或全不是猫，不再有猫和狗的混合。因此，我们可以创建这些叶节点，在左边做出猫的预测，在右边做出不是猫的预测。
这就是构建决策树的过程。
在刚才的决策树建立过程中，做出几个关键决策。

第一个关键决策是，你如何选择在每个节点上使用的特征来进行分割?

在根节点，以及决策树的左分支和右分支，我们必须决定如果该节点有少数例子包含猫和狗的混合，你是想根据耳形特征、脸形特征还是胡须特征进行分割?

我们希望的是在决策树节点选择哪个特征进行分裂，可以获得最大化纯度。

所谓纯度，是希望得到尽可能接近全是猫或全是狗的子集。
例如，如果我们有一个特征，它问:这个动物有猫的 DNA 吗，我们实际上没有这个特征，但如果我们有，我们可以在根节点上基于这个特征进行分裂，这将导致左分支中有五分之五的猫，右分支中有零分之五的猫，这两个左分支和右分支的数据子集是完全纯的，这意味着这两个左分支和右分支的数据子集是完全纯的，这意味着这就是为什么如果我们有猫 DNA 特征，它将是一个非常好的特征来使用。
但对于我们实际拥有的特征，我们必须决定是基于耳形分裂，这导致左分支中有五分之四的例子是猫，右分支中有五分之一是猫，还是基于脸形，这导致左分支中有七分之四，右分支中有三分之二，或者基于胡须，这导致左分支中有四分之三的例子是猫，右分支中有六分之二不是猫。

因此，决策树学习算法必须在耳形、脸形和胡须之间选择哪个特征能导致左分支和右分支的标签纯度最高。因为如果你能得到一个高度纯的例子子集，那么你就可以预测是猫或不是猫，并且大部分情况下都是正确的。

因此，在学习决策树时，我们首先要做的决定是如何在每个节点上选择要分裂的特征。

构建决策树时需要做的第二个关键决定是决定何时停止分裂

1、我们刚才使用的标准是直到一个节点要么100%全是猫，要么100%全是狗和不是猫。 因为在这一点上，构建一个只进行分类预测的叶节点似乎是自然的。
2、你也可以决定在进一步分裂节点会导致树超过最大深度时停止分裂，你允许树生长的最大深度是你可以决定的参数。
在决策树中，节点的深度定义为从根节点(即最顶部的节点)到达该节点所需的跳数。因此，根节点到达自身需要零跳，深度为零，它下面的节点深度为一，再下面的节点深度为二。所以如果你决定决策树的最大深度是二，那么你就不会分裂任何低于这个深度的节点，这样树就不会达到深度三。
我们限制决策树深度的原因之一是确保首先树不会变得太大和难以管理，其次通过保持树小，它不太容易过拟合。
过拟合就是模型在训练集上表现良好，在测试集上表现不好。
3、另一个你可能用来决定停止分裂的标准是，纯度分数的改进低于某个阈值。所以如果分裂一个节点导致纯度的最小改进，或者它实际上降低了不纯度，但如果收益太小，你可能就不会费心了。同样，为了保持树更小并减少过拟合的风险。
4，如果一个节点中的例子数量低于某个阈值，那么你也可能决定停止分裂。

例如，如果在根节点我们根据面部形状特征进行分裂，那么右分支将只有三个训练样本，其中一个是猫，两个是狗。与其将这些样本进一步分成更小的子集，如果你决定不再对只有三个或更少样本的集合进行分裂，那么你将创建一个决策节点。由于这里主要是狗，三个中有两个是狗，这个节点将做出非猫的预测。
再次强调，你可能决定不值得进一步分裂的一个原因是保持树的规模较小，以避免过拟合。

下面我们将探讨一种测量样本集纯度的方法。

如果样本全是猫或单一类别，那么它的纯度非常高。如果全是非猫，那也是非常纯的。但如果介于两者之间，如何量化这个样本集的纯度呢?
让我们来看看熵的定义，它是衡量样本集不纯度的一指标。
假设有一个包含六个样本的集合，其中有三个猫和三个狗。
我们定义 p1 为猫在样本的比例，即标签为1的样本比例，这就是下标1所表示的。因此，在这个例子中，p1等于3除以6。
我们将使用一个称为熵的函数来测量样本集的不纯度，这个函数看起来是这样的。熵函数通常用大写 H 表示，参数为 p1。
熵函数通常用大写 H 表示，参数为 p1。这个函数看起来像这里的曲线，横轴是样本中猫的比例 p1,纵轴是熵的值。
所以在这个例子中，当 p1 为3除以6或0.5时，熵的值等于1,你会注意到，当样本集为50-50时，这条曲线达到最高点。因此，当样本集为50-50时，不纯度最大，熵值为1.相比之下，如果样本集全是猫或全不是猫，那么熵为零,
让我们再看几个例子，以进一步理解熵及其工作原理，
这里有一个不同的样本集，包含五只猫和一只狗。所以 p1，即正样本的比例，标签为1的样本比例是5除以6.因此，p1 大约是0.83.如果你在0.83处读取该值，你会发现 p1的熵大约是0.65
再看一个例子。
这个包含六个图像的样本全是猫。所以 p1 是6除以6，因为所有六个都是猫,p1 的熵是这里的这个点，值为零。因此我们看到，当你从3除以6到6除以6的猫样本变化时，不纯度从1降到0。

换句话说，纯度随着你从猫和狗的50-50混合到全是猫而增加。

现在让我们来看看熵函数的实际方程，H(p1)。
回想一下，p1 是等于猫的样本比例。所以如果你有一个样本集，其中三分之二是猫，那么这个样本集必须有三分之一的非猫。因此，我定义 p0 为非猫样本的比例，等于1减去 p1,熵函数定义为负 p1 乘以 p1 的对数。按照惯例，在计算熵时，我们使用以2为底的对数，而不是以e 为底。然后减去 p0 乘以 p0 以2为底的对数,或者，这也等于负p1 log p1 减去1-p1 log 1-p1.
如果你要在计算机上绘制这个函数，你会发现它就是这个左边的函数。
我们取以2为底的对数，只是为了让这个曲线的峰值等于1。如果你取以e为底的对数，或者自然对数的底，那么这只是垂直缩放了这个函数。
它仍然有效，但数值变得有点难以解释，因为函数的峰值不再是像1这样的整数了。
关于计算这个函数的一个注意事项是，如果 p1 或 p0等于0，那么这样的表达式看起来像是0 log0.而 log 0在技术上是未定义的，实际上是负无穷大.
为了计算熵的目的，我们将0 log 0视为等于0 ，这将正确计算在0或1处的熵等于0。 但应用这个熵公式在构建决策树时应该工作得很好。
总结一下，熵函数是衡量数据集不纯度的一个指标。它从0开始，上升到1，然后又回到0，作为样本中正样本比例的函数，基尼函数也是从0到1再到0的函数

信息增益

在构建决策树时，我们决定选择哪种特征选择最能减少熵，或减少不纯度，或最大化纯度。在决策树学习中，熵的减少称为信息增益。
从而选择在决策树的每个节点上使用哪个特征进行分割。让我们以决定在根节点上使用哪个特征为例，来识别猫与非猫。
如果我们使用耳形特征在根节点上进行分割， p1 等于五分之四或0.8，右边有五分之一是猫，所以p1等于五分之一或0.2。
如果你应用上面的熵公式到这个左边的数据子集和右边的数据子集，我们发现左边的熵是0.8，大约是0.72，右边的熵是0.2，结果也是0.72。
如果我们选择耳形特征进行分割左边，p1是七分之四，右边的 p1 是三分之一，它们的熵分别是0.99和0.92。所以左节点和右节点的不纯度似乎更高，0.99和0.92对比0.72和0.72。最后，第三个可能的选择是在根节点上使用胡须特征进行分割。

与这些分割相关的每个都有两个数字，左子分支的熵和右子分支的熵都计算出来了。所以我们需要回答的关键问题是，给定这三个在根节点上使用的特征选项，我们认为哪一个效果最好?
为了从这些中选择，我们喜欢将这两个数字合并成一个单一的数字，这样我们就可以从这三个选择中挑选出看起来最好的一个。
我们将通过加权平均来合并这两个数字，
因为在一个子分支中拥有低熵的重要性也取决于有多少例子进入了左或右子分支，因为如果在一个子分支中有大量的例子，那么确保该子分支的熵值低似乎更重要。
所以在本例中，我们有五个样本进入了左子分支，因此我们可以计算加权平均值为十分之五乘以熵0.8，然后加上十分之五的样本也进入了右子分支，加上十分之五乘以熵。依次类推
因此，我们将通过计算这三个数值并选择其中最小的那个来选择分割，因为这为我们提供了左右子分支中加权平均熵最低的分割。
在构建决策树的过程中，我们实际上会对这些公式进行一次修改，以符合决策树构建的惯例，但这并不会改变结果：即我们不是计算这个加权平均熵，而是计算与未分割时的熵相比的减少量。
因此，如果我们回到根节点，记住在根节点我们一开始有十个样本，五只猫和五只狗，所以在根节点我们有p1等于十分之五或0.5，因此根节点的熵，熵0.5，实际上等于1。这是最大不纯度，因为它是五只猫和五只狗。因此，我们实际上用于选择分割的公式不是左右子分支的加权熵。
相反，它将是根节点的熵，即熵0.5，然后减去这个公式,在这个例子中，如果你计算数学，耳朵特征结果是0.28.依次类推。
我们刚刚计算的这些数值，0.28、0.03和0.12，这些被称为信息增益，它衡量的是你在树中通过分割获得的熵减少量，因为熵最初在根节点为1，通过分割，你最终得到一个较低的熵值，这两个值之间的差异就是熵的减少量，在耳型分割的情况下是0.28。

那么为什么我们要计算熵的减少量而不是左右子分支的熵呢？

事实证明，决定何时不再进一步分割的停止准则之一是如果熵的减少量太小，在这种情况下，你可以决定只是不必要地增加树的大小并冒着过拟合的风险进行分割，如果熵的减少量太小低于某个阈值，就决定不再分割。 在这个特定的例子中，耳型分割导致了最大的熵减少量，0. 28大于0.03或0.12，因此我们将在根节点选择耳型特征进行分割。
我们将在下一页介绍的另一个符号是这些数值，十分之五和十分之五，我将称之为 w左（左权重），因为这是进入左分支的样本比例， w右：是进入右分支的样本比例。而对于中间的例子，w左 将是十分之七，w右 将是十分之三 。
那么现在让我们写下计算信息增益的一般公式，以耳形特征的分割为例，让我定义p1左等于左子树中具有正标签的样本的比例，即猫的比例。 所以在本例中，p1左将等于五分之四，并且让我定义w左为根节点中所有样本中进入左子分支的样本比例。所以在本例中，w左 将是十分之五。类似地，让我们定义 p1 右为右分支中所有样本中正样本的比例，所以如果这些样本中有五分之一是猫，那将是五分之一，同样地，w右 是十分之五，即进入右子分支的样本比例。让我们也定义p1根为根节点中正样本的比例，所以在这种情况下，这将是十分之五或0.5.
信息增益随后被定义为 p1 根的熵，即根节点的熵，减去我们在上一张幻灯片中提到的加权熵计算，减去 w左，在本例中为十分之五，乘以应用于 p1 左的熵，即左子分支的熵，加上 w右，即进入右分支的样本比例，乘以 p1 右的熵.

通过这种熵的定义，你可以计算出与选择任何特定特征进行分割相关的信息增益。

然后，在所有可能的特征中，你可以选择提供最高信息增益的那个。这将有望增加你在决策树的左子分支和右子分支上获得的数据子集的纯度。
这将导致选择一个特征进行分割，该特征增加了决策树的左子分支和右子分支上数据子集的纯度
让我们把所有讨论的内容结合起来，形成一个给定训练集构建决策树的总体算法。

综合示例

信息增益标准让你决定如何在某个节点选择一个特征进行分裂。让我们把这个标准应用到决策树的多个地方，以便弄清楚如何构建一个具有多个节点的大型决策树。
从根节点开始，包含所有训练样本，计算所有可能特征的信息增益，并选择信息增益最高的特征进行分裂。选择该特征后，根据所选特征将数据集分成两个子集，创建树的左右分支，并根据该样本的特征值将训练样本发送到左分支或右分支。这使得你可以在根节点进行一次分裂。之后，你将继续在树的左分支和右分支上重复分裂过程，直到满足停止标准。
停止标准可以是当一个节点100%属于单一类别时，即熵为零，或者进一步分裂节点会导致树超过你设定的最大深度，或者如果进一步分裂的信息增益小于某个值，或者如果节点中的样本数量低于某个阈值。因此，你将继续重复分裂过程，直到你选择的停止标准(可能是一个或多个这些标准)被满足。
我们从根节点开始，包含所有样本，并基于计算所有三个 特征的信息增益，决定耳形是最佳的分裂特征基于此，我们创建左右子分支，并将具有尖耳或软耳的子数据集发送到左右子分支。所以让我覆盖根节点和右子分支，只关注左子分支，这里有五个样本。

假设我们的分裂标准是继续分裂，直到节点中的所有内容都属于单一类别，即全是猫或全是狗。我们会查看这个节点，看看它是否满足分裂标准，但它不满足，因为这里有猫和狗的混合。所以下一步是选择一个特征进行分裂。因此，我们依次查看每个特征，并计算这些特征的信息增益,就好像这个节点是使用这里显示的五个训练样本训练的决策树的新根节点。因此，我们将计算分裂胡须特征的信息增益，分裂脸型特征的信息增益，结果分裂耳形的信息增益将为零，因为所有这些都有相同的尖耳形状。在胡须和脸型之间，脸型最终具有最高的信息增益，因此我们将基于脸型进行分裂，这使我们能够构建如下所示的左右子分支。因此，对于左子分支，我们将检查是否满足停止分裂的标准,这里全是猫。因此，停止标准被满足，我们创建一个叶节点，预测为猫,对于右子分支，我们发现全是狗，因此我们也将停止分裂,因为我们已经满足了分裂标准，并在那里放置一个叶节点,预测为非猫。

因此，构建了这个左子树后，我们现在可以关注构建右子树,为了构建正确的子树，我们有这五个样本，首先检查是否满足停止分裂的条件，条件是所有样本是否属于同一类别。我们尚未满足停止分裂的条件，因此我们决定在这个右子分支上继续分裂。事实上，构建右子分支的过程与从头开始训练决策树学习算法非常相似，其中数据集仅包含这五个训练样本,因此，再次计算所有可能特征的信息增益，你会发现胡须特征提供了最高的信息增益。根据胡须是否存在来分裂这五个样本，检查左子分支和右子分支是否满足停止分裂的条件，并确定它们满足，因此你最终得到预测猫和不猫的叶节点。这就是构建决策树的总体过程。

注意，我们做的一个有趣的事情是，在根节点决定分裂后，我们通过在五个样本的子集上构建决策树来构建左子树，而右子树也是通过在五个样本的子集上构建决策树来构建的。在计算机科学中，这是递归算法的一个例子，这意味着你在根节点构建决策树的方式是通过在左子分支和右子分支上构建其他较小的决策树。
因此，计算机科学中的递归指的是编写调用自身的代码，在构建决策树时，你通过构建较小的子决策树然后将它们组合在一起来构建整个决策树。这就是为什么如果你查看决策树的软件实现，有时会看到对递归算法的引用，但如果你不完全理解递归算法的概念，不用担心，一样可以用库来让决策树为你工作。但如果你从头开始实现决策树算法，那么递归算法就是你必须要实现的一个步骤。
你可能想知道如何选择最大深度参数。有许多不同的可能选择，但一些开源库会有很好的默认选择供你使用。
一个直觉是，最大深度越大，你愿意构建的决策树就越大，这有点像拟合更高次的多项式或训练更大的神经网络。它让决策树学习更复杂的模型，但如果它拟合了一个非常复杂的函数到你的数据上，也会增加过拟合的风险。
理论上，你可以使用交又验证来选择像最大深度这样的参数，你尝试不同的最大深度值，并选择在交又验证集上效果最好的那个。虽然在实践中，开源库甚至有更好的方法来为你选择这个参数。或者，你可以使用的另一个停止分裂的标准是，如果从额外分裂中获得的信息增益小于某个阈值，因此，如果你分裂的任何特征只实现了很小的熵减少或非常小的信息增益，那么你可能也会决定不继续分裂。最后，你也可以在节点中的样本数量低于某个阈值时决定停止分裂。

连续值特征

那就是可以任意数量的特性
让我们从一个例子开始
我已经修改了猫领养中心数据集，添加了一个额外的特征：动物的体重(以磅为单位)，平均而言
在猫和狗之间，猫比狗稍微轻一点，尽管有些猫比一些狗重，但是，动物的重量是一个有用特征，用于决定它是不是猫
那么如何让决策树使用这种特征
决策树学习算法将像以前一样进行
只是不再仅仅考虑根据耳朵形状、面部形状和胡须进行分裂，还要考虑胡须或体重进行分割
如果根据重量特征分裂可以获得比其他选项更好的信息增益
那么你将根据重量特征进行分裂
但你如何决定如何根据重量特征进行分裂
让我们看看
这里是根节点的数据图。

我在横轴上绘制了动物的体重，纵轴上方是猫，下方不是猫，因此，纵轴表示标签 y为1或0.
我们根据重量特征进行划分的方式是
如果我们根据重量是否小于或等于某个值对数据进行划分
例如小于或等于8(或其他某个值)来分割数据
假设我们选择8或其他某个值，这是学习算法需要决定的
在考虑根据重量特征进行划分时我们需要考虑许多不同的阈值然后选择最好的一个
我是指能带来最大信息增益的那个
具体来说
如果你考虑根据重量是否小于等于8来划分示例
那么你会将这个数据集分为两个子集
左边的子集有两个猫
右边的子集有三个猫和五个狗

如果你计算我们通常的信息增益计算你将会计算
节点的熵，熵为0.5，减去2/10乘以左边分割的熵(有2只猫）加上右边分割的熵(有8个示例)。
右边的8个示例中，3只是猫，所以熵为3/8，结果是0.24.
因此，如果你基于体重是否小于或等于8进行分割，这将是你获得的信息增益。但我们也应该尝试其他值。那么，如果你基于体重是否小于或等于9进行分割呢?这对应于这里的这条新线。信息增益计算变为 h( 0.5)减去，现在左边分割有4个示例
因此，这里的信息增益看起来好得多，0.61的信息增益，远高于0.24。或者我们可以尝试另一个值，比如13，计算结果看起来像这样，是0.40.

在更一般的情况下，我们实际上不会只尝试3个值，而是会尝试x轴 上的多个值。
一种惯例是根据权重或这个特征的值对所有示例进行排序，并取排序列表中训练示例之间的所有中点值作为这里阈值的考虑值。这样，如果你有10个训练样本，你将测试9个不同的可能阈值，然后尝试选择那个能给你最高信息增益的值。最后，如果基于某个阈值进行分割的信息增益优于基于任何其他特征进行分割的信息增益，那么你将决定在该特征上分割该节点。
在这个例子中，0.61的信息增益最终高于任何其他特征的信息增益。 事实证明，实际上有两个阈值。因此，假设算法选择这个特征进行分割，你将根据动物的重量是否小于或等于9磅来分割数据集。
这样你就会得到两个这样的数据子集，然后你可以使用这两个数据子集递归地构建额外的决策树，以构建树的其余部分
总结一下，为了让决策树在每个节点上处理连续值特征，在考虑分割时，你只需考虑不同的分割值，进行通常的信息增益计算，并决定如果该连续值特征能提供最高可能的信息增益，则在该特征上进行分割。