分类与回归树 Classification and Regression Tree/cart
CART 是在给定输入随机变量 X 条件下输出随机变量 Y 的条件概率分布的学习方法。
定义
CART 假设决策树是二叉树，内部结点特征的取值为「是」和「否」，左分支是取值为「是」的分支，右分支是取值为「否」的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART 算法由以下两步组成：
- 树的生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 树的剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。
决策树的生成就是通过递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
回归树的生成
假设 X 与 Y 分别是输入和输出向量，并且 Y 是连续变量，给定训练数据集 考虑如何生成回归树。
一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的但单元上的输出值。假设已将输入空间划分为 M 个单元 $latex R_{1}, R_{2}, \ldots, R_{M}$ 并且在每个单元 $latex R_{m} $ 上有一个固定的输出值 $latex c_{m} $ 于是回归树模型可表示为 $latex f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right) $
当输入空间的划分确定时，可以用平方误差 $latex \sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$
来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元 $latex R_{m} $ 上的 $latex c_{m} $ 的最优值 $latex c_{m} $ 是 $latex R_{m} $ 上所有输入实例 $latex x_{i} $ 对于的输出 $latex y_{i} $ 的均值，即
问题是怎样对输入空间进行划分，这里采用启发式的方法，选择第 j 个变量 $latex x^{(j)}$和它取的值 s ，作为切分变量和切分点，并定义两个区域：
然后寻找最优切分变量 j 和最优切分点 s 。具体的，求解
对固定输入变量 j 可以找到最优切分点 s
遍历所有输入变量，找到最优切分变量 j ，构成一个对 $latex (j, s) $，依次将输入空间划分为两个区域。接着，每个对每个区域重复上述划分过程，直到满足停止条件为止。
分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点
基尼指数
在分类过程中，假设有 K 个类，样本点属于第 k 个类的概率为 $latex p_{k} $ ，则概率分布的基尼指数定义为：
对于二类分类问题，若样本点属于第 1 个类的概率是 p，则概率分布的基尼指数为：
对于给定的样本集合 D ，其基尼指数为：
其中， $latex C_{k} $ 是 D 中属于第 k 类的样本子集，K 是类的个数。
如果样本集合 D 根据特征 A 是否取某一可能值 a 被分割成 $latex D_{1}$ 和 $latex D_{2}$ 两部分，即：
则在特征 A 的条件下，集合 D 的基尼指数定义为：
基尼指数 $latex {Gini}(D) $ 表示集合 D 的不确定性，基尼指数 $latex {Gini}(D, A) $ 表示经 A=a 分割后集合 D 的不确定性。基尼指数越大，样本集合的不确定性越大，这一点与熵相似。
生成算法
输入：训练数据集 D, 停止计算的条件
输出：CART 决策树
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
- 设结点的训练数据集为 D，计算现有特征对该数据集的基尼系数。此时，对每个特征 A，对其可能取得每一个值 a，根据样本点 A=a 的测试为「是」或「否」将 D 分成 $latex D_{1} $和 $latex D_{2} $ 两部分，计算 A=a 时的基尼指数
- 在所有可能的特征 A 以及它们所有可能的切分点 a 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，依据最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去
- 对两个子结点递归地调用 ( 1 ) 、 ( 2 ) 直至满足停止条件
- 生成 CART 决策树