大数据分类与回归树（ClassificationandRegressionTree）

　　决策树不仅可以进行分类，也可以进行回归。与线性回归不同，回归树是将＂空间＂进行划分，每个空间对应一个统一的预测值。回归树的建立
　　当面对一个回归问题时，如特征向量为:  , 对应数据的多个维度，回归问题就是求出来这个特征向量的预测结果。
　　回归树所做的事情是：将空间X划分为多个不重叠的领域 ，其中，每一个划分出来的空间对应一个预测结果，即标签值y，标签值是根据该区域内的总样本数平均化得出的，即：
　　与线性回归类似，需要一个损失函数对回归的效果进行评估，采用平方残差和RSS进行评估：
　　内层 就是将该区域内所有样本的预测值和真实值之差值的平方进行求和；
　　外层 就是遍历所有划分出来的区域。
　　但是如果真的按照上述计算公式来进行空间划分的话，计算量将会非常惊人。为了对空间划分进行简化，通常使用递归二分法来对空间进行划分。递归二分法
　　什么是递归二分法？顾名思义，树的每次分裂都以二叉树的形式分裂。当我们初步根据特征及其最佳划分点分裂出了2个空间后，不断从当前位置，继续将该空间的样本再次划分成2份。
　　不同划分空间，生成回归树
　　划分方案自顶向下：从所有样本开始，不断从当前位置，把样本切分到2个分支里；贪婪：每一次的划分，只考虑当下划分的最优，不会回头考虑先前的划分。
　　假如回归树的特征向量是2个维度 ，若第一次分裂时，通过计算得知，当选取属性X1 最佳切分点为 t1 时，得到的损失函数RSS最小，那么本次分裂则可划分出两片区域R1和R2。
　　划分出R1和R2两个区域后，继续进行树的第二次分裂，若本次分裂根据特征 X2 找到最佳切分点 t2，则可将上图中原R1中的区域再次进行二分。类似的，原样本空间则可根据每一次属性及切分点的选择，以二分裂的形式每次更新两片空间，直到符合某个停止准则，如我们在前文《大数据：如何用决策树解决分类问题》中提到过的预剪枝中的停止准则。
　　前文《大数据：如何用决策树解决分类问题》介绍了几种可以用于分类问题的决策树，比如ID3和C4.5等。本文要介绍的CART（Classification and Regression Tree）树，既可以用于分类，也可以用于回归。CART分类树
　　首先我们先说一下CART分类树，ID3和C4.5都是多叉树，而CART是二叉树，内部节点的取值为＂是＂或＂否＂。除此之外，CART分类树和C4.5的最大区别在于选择分裂点时的计算逻辑，C4.5选择分裂点基于信息增益率，而CART分类树基于基尼指数的增益率。
　　基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。 基尼指数越小，则数据集纯度越高。
　　基尼系数
　　其中Ck代表在数据集D中属于标签值为K的数据样本个数。
　　总体来说，CART分类树是以基尼系数作为选择的标准，但CART每次分类都以2叉树的形式进行分类，需要进行多次的基尼系数差值的运算才能找到最好的分类结果。
　　对比C4.5，CART的提升主要包括以下方面：C4.5 只能分类，CART 既可以分类也可以回归；CART 使用 Gini 系数作为度量，减少了大量的对数运算，运算速度较快；C4.5使用信息增益率作为度量，信息增益率的计算需要使用大量对数运算，计算复杂度较高。CART回归树
　　CART回归树与分类树的建立很相似，不同的地方在于连续值的处理方法及最终预测的方式不同。CART回归树使用平方误差最小化准则构建二叉回归树。一棵回归树对应输入空间X的一个划分以及在划分的单元上的输出值。
　　对于训练集，和CART分类树唯一不同的在于CART回归树面向的是回归问题，即样本的输出为连续型变量。
　　单一决策树的学习能力是有限的，所以后来人们开始通过集成学习的方法，将多个弱学习器联合在一起，提升为强学习器。
　　著名的梯度提升机（GBM：Gradient Boosting Machine ）中最常见的算法叫做GBDT（Gradient Boosting Decision Tree ）。GBDT中的弱学习器就是CART回归树，GBDT就是CART回归树的加性模型，因此也被称为GBRT（Gradient Boosting Regression Tree）。在之后的文章中，我们再来介绍集成学习的方法。