机器学习笔记7-CART决策树+剪枝
CART算法
CART又名分类回归树，该算法既可以用于分类还可以用于回归。
CART树有以下几个关键点：
- CART是一棵二叉树；
- 当CART是分类树时，采用GINI值作为节点分裂的依据；
- 当CART是回归树时，采用样本的最小方差作为节点分裂的依据；
CART树节点的分裂分为两种情况，连续型的数据和离散型的数据。分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么CART是如何评价节点的纯度呢？如果是分类树，CART采用GINI值(基尼指数)衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。
分类模型：
ID3中使用了信息增益选择特征，增益大优先选择。C4.5中，采用信息增益比选择特征，减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（比）相反。
回归模型：
采用和方差度量，度量目标是对于划分特征A，对应划分点s两边的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小。表达式为：
下面举例说明：
| 看电视时间 | 婚姻情况 | 职业 | 年龄 |
| 3 | 未婚 | 学生 | 12 |
| 4 | 未婚 | 学生 | 18 |
| 2 | 已婚 | 老师 | 26 |
| 5 | 已婚 | 上班族 | 47 |
| 2.5 | 已婚 | 上班族 | 36 |
| 3.5 | 未婚 | 老师 | 29 |
| 4 | 已婚 | 学生 | 21 |
以职业这个属性来划分，总共有三种划分方法
第一种划分方法：{“学生”}、{“老师”、“上班族”}
预测是否已婚（分类）：
预测年龄（回归）：
第二种划分方法：{“老师”}、{“学生”、“上班族”}
预测是否已婚（分类）：
预测年龄（回归）：
第三种划分方法：{“上班族”}、{“学生”、“老师”}
预测是否已婚（分类）：
预测年龄（回归）：
综上，如果想预测是否已婚，则选择{“上班族”}、{“学生”、“老师”}的划分方法，如果想预测年龄，也选择{“上班族”}、{“学生”、“老师”}的划分方法。
回归树和模型树：
CART算法将数据集切分成多份易建模的模型。
回归树：叶子节点使用分段常数
模型树：叶子节点使用线性回归方程
CART树算法的剪枝
预剪枝：在创建树的时候添加一些限制条件，例如方差的差值大于某个阈值，划分数据集后每个数据集的数量也需要大于某个阈值等。
后剪枝：将数据集划分成测试集和训练集。接下来从上而下找到叶子节点，用测试集来判断将这些叶节点合并是否能降低测试误差。如果是的话就合并。