原文： https://machinelearningmastery.com/classification-and-regression-trees-for-machine-learning/
决策树是用于预测性建模机器学习的重要算法类型。
经典的决策树算法已经存在了几十年，现代变体如随机森林是最有效的技术之一。
在这篇文章中，您将发现一种简陋的决策树算法，它以更现代的名称 CART 代表分类和回归树。阅读这篇文章后，你会知道：
- 用于描述机器学习的 CART 算法的许多名称。
- 实际存储在磁盘上的已学习 CART 模型使用的表示形式。
- 如何从训练数据中学习 CART 模型。
- 如何使用学习的 CART 模型对看不见的数据做出预测。
- 您可以使用其他资源来了解有关 CART 和相关算法的更多信息。
如果你已经采用了算法和数据结构课程，那么可能很难阻止你实现这个简单而强大的算法。从那里开始，您距离自己实现的随机森林只有一小步之遥。
让我们开始吧。
- 2017 年 8 月更新：修正了一个拼写错误，表明 Gini 是一个类的实例数，应该是实例的比例。除了计算子节点的纯度之外，还更新了显示用于评估拆分的 Gini 权重。
用于机器学习的分类和回归树 照片由 Wonderlane 拍摄，保留一些权利。
分类和回归树或简称 CART 是 Leo Breiman 引用的术语，指的是可用于分类或回归预测性建模问题的决策树算法。
传统上，这种算法被称为“决策树”，但在某些平台上，如 R，它们被更现代的术语 CART 所引用。
CART 算法为诸如袋装决策树，随机森林和提升决策树等重要算法提供了基础。
方便的机器学习算法思维导图的样本。
我已经创建了一个由类型组织的 60 多种算法的方便思维导图。
下载，打印并使用它。
CART 模型的表示是二叉树。
这是来自算法和数据结构的二叉树，没什么太花哨的。每个根节点表示单个输入变量（x）和该变量上的分割点（假设变量是数字）。
树的叶节点包含用于做出预测的输出变量（y）。
给定一个数据集，其中两个输入（x）的高度以厘米为单位，重量以千克为单位，性别输出为男性或女性，下面是二元决策树的粗略示例（完全虚构仅用于演示目的）。
决策树示例
树可以作为图形或一组规则存储到文件中。例如，下面是上面的决策树作为一组规则。
If Height > 180 cm Then Male
If Height <= 180 cm AND Weight > 80 kg Then Male
If Height <= 180 cm AND Weight <= 80 kg Then Female
Make Predictions With CART Models利用上述 CART 模型的二叉树表示，做出预测相对简单。
给定新输入，通过评估在树的根节点处开始的特定输入来遍历树。
学习的二叉树实际上是输入空间的分区。您可以将每个输入变量视为 p 维空间上的维度。决策树将其分为矩形（当 p = 2 个输入变量时）或某种具有更多输入的超矩形。
新数据通过树过滤并落在其中一个矩形中，该矩形的输出值是模型预测的结果。这让您对 CART 模型能够做出的决策类型有所了解，例如：四四方方的决定边界。
例如，如果输入[height = 160 cm，weight = 65 kg]，我们将按如下方式遍历上面的树：
Height > 180 cm: No
Weight > 80 kg: No
Therefore: Female创建 CART 模型涉及在这些变量上选择输入变量和分割点，直到构造出合适的树。
使用贪婪算法选择要使用的输入变量和特定的分割或切割点以最小化成本函数。树构造使用预定义的停止标准结束，例如分配给树的每个叶节点的最小数量的训练实例。
创建二元决策树实际上是划分输入空间的过程。贪婪的方法用于划分称为递归二进制分裂的空间。
这是一个数值程序，其中所有值都排成一行，并使用成本函数尝试和测试不同的分裂点。选择具有最佳成本（最低成本，因为我们最小化成本）的分割。
以贪婪的方式评估和选择所有输入变量和所有可能的分裂点（例如，每次选择最佳分裂点）。
对于回归预测性建模问题，最小化以选择分割点的成本函数是落在矩形内的所有训练样本的总平方误差：
sum（y - 预测）^ 2
其中 y 是训练样本的输出，预测是矩形的预测输出。
对于分类，使用 Gini 索引函数，其指示叶节点的“纯”程度（分配给每个节点的训练数据的混合程度如何）。
G =总和（pk *（1 - pk））
其中 G 是所有类的基尼指数，pk 是在感兴趣的矩形中具有类 k 的训练实例的比例。具有相同类型（完全类纯度）的所有类的节点将具有 G = 0，其中对于二分类问题（最差纯度）具有 50-50 类别的 G 将具有 G = 0.5。
对于二分类问题，可以将其重写为：
G = 2 * p1 * p2 或 G = 1 - （p1 ^ 2 + p2 ^ 2）
每个节点的 Gini 索引计算由父节点中的实例总数加权。因此，二分类问题中所选分裂点的基尼分数计算如下：
G =（（1 - （g1_1 ^ 2 + g1_2 ^ 2））（ng1 / n））+（（1 - （g2_1 ^ 2 + g2_2 ^ 2））（ng2 / n））
其中 G 是分裂点的基尼指数，g1_1 是第 1 组中第 1 类实例的比例，第 2 类为 g1_2，第 2 组为第 2 类，第 2 组为 g2_2，第 2 组为第 2，ng1 和 ng2 为总数第 1 组和第 2 组中的实例和 n 是我们尝试从父节点分组的实例总数。
上面描述的递归二进制分裂过程需要知道何时停止分裂，因为它沿着具有训练数据的树向下工作。
最常见的停止过程是对分配给每个叶节点的训练实例的数量使用最小计数。如果计数小于某个最小值，则不接受拆分，并将该节点作为最终叶节点。
训练成员的数量被调整到数据集，例如，它定义了树将对训练数据的具体程度。太具体（例如计数为 1）并且树将过拟合训练数据并且可能在测试集上具有差的表现。
停止标准很重要，因为它会严重影响树的表现。学习树后可以使用修剪来进一步提升表现。
决策树的复杂性定义为树中的分裂数。更简单的树木是首选。它们易于理解（您可以将它们打印出来并向主题专家展示），并且它们不太可能过度填充您的数据。
最快和最简单的修剪方法是遍历树中的每个叶节点，并使用保持测试集评估删除它的效果。仅当叶节点导致整个测试集上的总成本函数下降时，才会删除叶节点。如果无法进一步改进，则停止删除节点。
可以使用更复杂的修剪方法，例如成本复杂性修剪（也称为最弱链接修剪），其中使用学习参数（α）来权衡是否可以基于子树的大小来移除节点。
决策树的递归二进制拆分 照片由 Paul L Dineen 拍摄，保留一些权利。
除了很好地表示问题之外，CART 不需要任何特殊的数据准备。
本节列出了一些资源，如果您希望深入了解 CART，可以参考这些资源。
下面是一些很好的机器学习文本，它们从机器学习的角度描述了 CART 算法。
- 统计学习简介：在 R 中的应用，第 8 章
- Applied Predictive Modeling ，第 8 章和第 14 章
- 数据挖掘：实用机器学习工具和技术，第 6 章。
在这篇文章中，您发现了用于机器学习的分类和回归树（CART）。你了解到：
- 经典名称决策树和更现代的名称 CART 算法。
- 用于 CART 的表示是二叉树。
- 通过在给定新输入记录的情况下遍历二叉树，使用 CART 做出预测。
- 使用训练数据上的贪婪算法来学习树以选择树中的分裂。
- 停止标准定义了多少树学习和修剪可用于改进学习树。
您对 CART 或这篇文章有任何疑问吗？ 在评论中提问，我会尽力回答。