【机器学习基础】CART--分类回归树完全解读

CART树全名是分类与回归树，可用于分类或回归，是二叉树，根据是否满足某个条件将集合不断二分。无论分类还是回归，其中心思想是找到最优切分变量和最优切分点，只不过在分类问题中用基尼指数最小化作为依据，在回归问题中用平方误差最小化作为准则。接下来分别举例说明两种树。

一、分类树

先验知识：基尼系数

基尼系数，又叫基尼不纯度，表示样本集合中被随机选中的一个样本被错误分类的概率，值越小表示被分错的概率越小，基尼指数=被选中的概率*被分错的概率，如下公式中， pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)。

CART分类树生成算法

输入：训练数据集D，停止计算的条件；

输出：CART决策树；

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

1.设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分，之后计算基尼指数。

2.在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最有特征与最优切分点。依照最优特征与最优切分点，从现有结点生成两个子节点，将训练数据集按照特征分配到两个子节点中去

3.对两个子结点递归地调用两个子结点，将训练数据集按特征分配到两个子节点中去。

4.生成CART决策树。 算法停止计算的条件是节点中的样本个数小于阈值或者基尼指数小于阈值，或者没有更多特征可用于分类了。

举个例子帮助理解

原始数据：

解答过程：

CART回归树生成算法

对各个特征找最优切分点，找最优切分点的依据就是按照这个切分原则，将集合分为两部分，分别对两部分的标签取均值，作为预测值，计算两部分的预测值与真实值之间的误差平方总和，能使得这个误差最小的，即为最优切分变量与最优切分点。

举个例子帮助理解

原始数据：

用sklearn中的库函数，限定最深深度为3，生成的CART回归树如下图：

1.选择第一个最优切分变量时，根据平方误差最小原则，选择6.5为切分点，和调用sklearn库得到的决策树根结点一致，并且此时的平方误差值为19.11，与上图中mse1.911相同。

2.以根结点的左分支对<6.5的集合再切分，再详细写一个，以便理解，

其他节点同理，当平方误差值达到一定阈值，可以停止节点再切分。

参考资料：

非常感谢有这么多愿意分享的大佬，争取做一个喜欢分享的小菜鸟

1.统计学习方法 李航

2.师兄的博文哈哈哈 juejin.im/post/5a16b2…