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