决策树是最强大的监督学习算法之一，用于分类和回归。它由一个类似树结构的流程图组成，其中每个内部节点表示对属性的测试，每个分支表示测试的结果，每个叶节点（终端节点）都包含一个类标签。它是通过根据属性值递归地将训练数据拆分为子集来构建的，直到满足停止条件，例如树的最大深度或拆分节点所需的最小样本数。

在训练期间，决策树算法根据熵或基尼杂质等指标选择最佳属性来拆分数据，该指标测量子集中的随机性或杂质水平。目标是找到在分裂后最大限度地提高信息增益或减少杂质的属性。

什么是决策树？

决策树是用于决策支持的分层模型，它描述了决策及其潜在结果，包括偶然事件、资源支出和效用。该算法模型利用条件控制语句，是非参数监督学习，对分类和回归任务都很有用。

决策树术语

讨论决策树时使用的一些常用技术术语如下：

• 根节点：树中最顶层的节点，表示完整的数据集。它是决策过程的起点。
• 决策/内部节点：表示有关输入要素的选择的节点。内部节点的分支会导致叶节点或其他内部节点。
• 叶/终端节点：没有任何指示类标签或数值的子节点的节点。
• 拆分：使用拆分条件和所选特征将节点拆分为两个或多个子节点的过程。
• 分支/子树：决策树的子部分，从内部节点开始，到叶节点结束。
• 父节点：划分为一个或多个子节点的节点。
• 子节点：拆分父节点时出现的节点。
• 杂质：测量目标变量在数据子集中的同质性。它指的是一组示例中的随机性或不确定性程度。
• 方差：方差衡量预测变量和目标变量在数据集的不同样本中的变化程度。它用于决策树中的回归问题。均方误差、均值绝对误差、Freidman-mse 或半泊松偏差用于度量决策树中回归任务的方差。
• 信息增益：信息增益是通过在决策树中拆分特定特征的数据集来实现的杂质减少的度量。拆分标准由提供最大信息增益的特征决定。它用于确定要在树的每个节点上拆分的信息量最大的特征，目的是创建纯子集。
• 修剪：从树上移除不提供任何附加信息或导致过度拟合的树枝的过程。

选择度量：

可以通过根据属性选择度量将源集拆分为子集来学习树。属性选择度量 （ASM） 是决策树算法中使用的一种标准，用于评估不同属性对拆分数据集的有用性。ASM 的目标是确定在拆分后将创建最同构的数据子集的属性，从而最大限度地提高信息增益。然后，以递归方式在每个派生子集上重复该过程，称为递归分区。当节点上的整个子集与目标变量具有相同的值时，或者当拆分不再为预测增加值时，递归完成。决策树分类器的构造不需要任何领域知识或参数设置，因此适用于探索性知识发现。决策树可以处理高维数据。

熵：

熵是数据集中随机性或不确定性程度的度量。在分类的情况下，它根据数据集中类标签的分布来测量随机性。对于第 i 个节点具有 K 个类的原始数据集的子集，其熵可以定义为：

这里

• k 是 K 类中的特定类
• p（i，k） 不应等于 0。

与熵相关的要点：

1. 当数据集完全同质时，熵为 0，这意味着每个实例属于同一类。零表示数据集样本中没有不确定性。
2. 当数据集在多个类之间平均分配时，熵达到最大值。因此，当类标签分布均匀时，熵最高，表明数据集样本的不确定性最大。
3. 熵用于评估分裂的质量。熵的目标是通过将数据集拆分为相对于类标签的更均匀的子集来选择使结果子集的熵最小化的属性。
4. 选择最高的信息增益属性作为拆分标准（即该属性拆分后熵的减少），并递归重复该过程以构建决策树。

基尼杂质：

基尼杂质是评估分类组之间分裂准确性的分数。基尼杂质评估 0 到 1 之间的分数，其中 0 表示所有观测值都属于一个类别，1 是类别内元素的随机分布。在这种情况下，希望基尼指数得分尽可能低。基尼指数是将用来我们的决策树模型的评估指标。

这里

• pi 是集合中属于第 i 个类别的元素的比例。

信息增益：

信息增益衡量基于特定属性拆分数据集所导致的熵或方差的减少。它在决策树算法中使用，通过将数据集划分为相对于类标签或目标变量的更同质的子集来确定特征的有用性。信息增益越高，该特征在预测目标变量方面的价值就越大。

属性 A 相对于数据集 S 的信息增益计算如下：

这里

• A 是特定的属性或类标签。
• |H|是数据集样本 S 的熵。
• |Hv|是子集中属性 A 的值为 V 的实例数。

信 息增益衡量通过对属性 A 的数据集进行分区而实现的熵或方差的减少。选择最大化信息增益的属性作为构建决策树的拆分标准。

信息增益用于分类和回归决策树。在分类中，熵用作杂质的度量，而在回归中，方差用作杂质的度量。在这两种情况下，信息增益计算保持不变，只是在公式中使用熵或方差而不是熵。

决策树算法：

决策树算法，也称为CART（分类和回归树算法），用于构建决策树。以下是 CART 算法的基本步骤：

1. 树的根节点应该是完整的训练数据集。
2. 根据数据集中存在的每个特征确定数据的杂质。杂质可以使用基尼指数或熵等指标进行分类，并使用均方误差、平均绝对误差、freidman-mse 或半泊松偏差进行回归。
3. 然后选择在拆分数据时导致最高信息增益或杂质减少的特征。
4. 对于所选要素的每个可能值，将数据集拆分为两个子集（左侧和右侧），一个子集的特征具有该值，另一个子集不具有该值。拆分应设计为创建相对于目标变量尽可能纯的子集。
5. 根据目标变量，确定每个结果子集的杂质。
6. 对于每个子集，重复步骤 2-5 迭代，直到满足停止条件。例如，停止条件可以是最大树深度、进行分裂所需的最小样品数或最小杂质阈值。
7. 为树中的每个终端节点分配分类任务的多数类标签或回归任务的平均值。

决策树的优点：

1. 它很容易理解，因为它遵循人类在现实生活中做出任何决定时所遵循的相同过程。
2. 它对于解决与决策相关的问题非常有用。
3. 它有助于思考问题的可能结果。
4. 与其他算法相比，对数据清理的需求较少。

决策树的缺点：

1. 决策树包含许多层，这使得它变得复杂。
2. 它可能存在过拟合问题，可以使用随机森林算法解决。
3. 对于更多的类标签，决策树的计算复杂性可能会增加。