分类与回归树(CART)

1.分类与回归树简介

分类与回归树的英文是Classfication And Regression Tree，缩写为CART。CART算法采用二分递归分割的技术将当前样本集分为两个子样本集，使得生成的每个非叶子节点都有两个分支。非叶子节点的特征取值为True和False，左分支取值为True，右分支取值为False，因此CART算法生成的决策树是结构简洁的二叉树。CART可以处理连续型变量和离散型变量，利用训练数据递归的划分特征空间进行建树，用验证数据进行剪枝。

• 如果待预测分类是离散型数据，则CART生成分类决策树。
• 如果待预测分类是连续性数据，则CART生成回归决策树。

  2.CART分类树

  2.1算法详解

  CART分类树预测分类离散型数据，采用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类过程中，假设有K个类，样本点属于第k个类的概率为Pk，则概率分布的基尼指数定义为根据基尼指数定义，可以得到样本集合D的基尼指数，其中Ck表示数据集D中属于第k类的样本子集。如果数据集D根据特征A在某一取值a上进行分割，得到D1,D2两部分后，那么在特征A下集合D的基尼系数如下所示。其中基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。对于属性A，分别计算任意属性值将数据集划分为两部分之后的Gain_Gini，选取其中的最小值，作为属性A得到的最优二分方案。然后对于训练集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本及S的最优二分方案。

  2.1实例详解

  
  针对上述离散型数据，按照体温为恒温和非恒温进行划分。其中恒温时包括哺乳类5个、鸟类2个，非恒温时包括爬行类3个、鱼类3个、两栖类2个，如下所示我们计算D1,D2的基尼指数。然后计算得到特征体温下数据集的Gini指数，最后我们选择Gain_Gini最小的特征和相应的划分。

  3.CART回归树

  3.1算法详解

  CART回归树预测回归连续型数据，假设X与Y分别是输入和输出变量，并且Y是连续变量。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。选择最优切分变量j与切分点s：遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小值时的(j,s)对。其中Rm是被划分的输入空间，cm是空间Rm对应的固定输出值。用选定的(j,s)对，划分区域并决定相应的输出值继续对两个子区域调用上述步骤，将输入空间划分为M个区域R1,R2,…,Rm，生成决策树。当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测方法，用平方误差最小的准则求解每个单元上的最优输出值。

  3.2实例详解

  
  因为只有一个变量x，所以j只有一个变量，j=1。取s=1。此时R1={1},R2={2,3,4,5,6,7,8,9,10}，这两个区域的输出值c分别为(c可以认为是预测输出值，m=2表示每个节点分为两个子节点)：
  
  
  当j=1,s=1,把c1和c2的值代入到均方差中，如下：
  
  
  同理，可以获得下表：
  
  显然取s=5时，m(s)最小。因此，第一个最优切分变量为j=1、最优切分点为s=5。R1={1，2，3，4，5}，R2={6，7，8，9，10}，对R1继续划分：
  
  
  s=3时，m(3)最小。R1={1，2，3}，R2={4，5}