一、CART 算法介绍

前面我们已经学习了 算法与 算法，并且也提到了算法的一些不足，比如 算法，模型它使用了较为复杂的多叉树，只能处理分类问题而不能处理回归问题等。对于这些问题，CART（Classification and Regression Tree）算法做了很多改进，它既可以做分类也可以做回归。

二、CART 分类树

（1）特征选择
我们知道， 算法使用信息增益来作为节点划分时的属性选择标准，而 算法使用信息增益率来作为节点划分时的属性选择标准，但是二者均是基于熵模型的，因此会涉及到大量的对数运算。所以，CART 分类算法使用了基尼系数作为属性选择的标准，在保留熵模型大部分优点的情况下也简化了模型。

（2）特征处理
A. 连续型变量。CART 分类树对于连续变量的处理思想基本与 算法一致，都是将连续型变量进行离散化处理，唯一的区别在于选择划分点时的度量方式不同，也就是说，对于切分后得到的个点，CART 分类算法会分别计算各个点作为二元分类点时的基尼系数，然后选择基尼系数最小的点作为该连续特征的离散化分类点。
B. 离散型变量。对于离散型变量，CART 分类树的基本思想是将其进行不停的二分。
回忆一下 算法与 算法，假设属性A被选取进行节点划分，其取值有3个类别A1、A2、A3，此时，我们就会建立一个三分叉的节点，最后生成一棵多叉树。而CART 分类树算法则不同，还是上面的例子，CART 分类树会考虑将属性A分为{A1;A2、A3}、{A2;A1、A3}、{A3;A1、A2}，然后以基尼系数最小的组合进行节点划分，比如选择了{A3;A1、A2}建立二叉树节点，那么，实际上A1、A2的取值是没有被分开的，所以在后续的节点建立过程中，还可以继续选择属性A来划分A1和A2，而在 算法与 算法中，每个离散属性只会参与一次节点划分过程。

三、CART回归树

（1）概念理解
首先，我们要明白，什么是分类树，什么是回归树，其实二者的区别主要在于样本的输出，如果样本输出是离散值，那么就是分类树；如果样本输出是连续值，那么就是回归树。
（2）差异对比
CART 回归树与CART 分类树的建立算法大多数的相同的，这里我们主要来看下二者的区别，除了概念上的不同，还包括以下两点：
A. 连续值的处理方法不同
我们知道，CART 分类树采用基尼系数来衡量连续属性各个划分点的优劣，比较适合做分类，对于CART 回归模型而言，通常采用如下式子来选取属性和划分点：

其中，为D1数据集的样本输出均值，为D2数据集的样本输出均值，和分别代表属性和切分点。只要遍历所有属性的所有切分点，就能找到最优的切分属性和切分点，最终得到一棵回归树。

B. 预测方式不同
对于预测方式，我们知道CART 分类树采用叶节点中概率最大的类别作为当前节点的预测类别，例如，在某一叶节点中有50%的样本属于类别1，30%的样本属于类别2，20%的样本属于类别3，那么，如果新样本落到该叶节点，我们就说新样本属于类别1。但是，对于回归树而言，输出的不是类别，故它采用的是最终叶节点的均值或中位数作为预测结果。

请根据本节内容回答以下问题:

决策树的三种主要生长算法有哪些？