CART决策树

参考：

1. http://www.cnblogs.com/yonghao/p/5135386.html
2. http://blog.sina.com.cn/s/blog_5d6632e70101gh79.html

概述：

1. CART 既能是分类树，又能是回归树.

2. 当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据；

3. CART是一棵二叉树。

优点：既能是分类树，又能是回归树，且二叉树的结构更为简洁.

缺点：是一种大样本统计方法，样本量较小时模型不稳定.

详述：

接下来将以一个实际的例子对CART进行介绍：

从以下的思路理解CART：

分类树？回归树？

分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。
CART既能是分类树，又能是决策树，如上表所示，如果我们想预测一个人是否已婚，那么构建的CART将是分类树；如果想预测一个人的年龄，那么构建的将是回归树。

分类树和回归树是怎么做决策的？
假设我们构建了两棵决策树分别预测用户是否已婚和实际的年龄，如图1和图2所示：

图1表示一棵分类树，其叶子节点的输出结果为一个实际的类别，在这个例子里是婚姻的情况（已婚或者未婚），选择叶子节点中数量占比最大的类别作为输出的类别；
图2是一棵回归树，预测用户的实际年龄，是一个具体的输出值。怎样得到这个输出值？一般情况下选择使用中值、平均值或者众数进行表示，图2使用节点年龄数据的平均值作为输出值。

CART如何选择分裂的属性？

分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么CART是如何评价节点的纯度呢？如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。

GINI值的计算公式：

其中，pi表示节点中属于类i的概率。
节点越不纯，GINI值越大，反之，则GINI值越小。
以预测二分类为例，如果节点的所有数据只有一个类别，则GINI=1−∑i∈Ip2i=0；
如果两类数量相同，则GINI=1−∑i∈Ip2i=12。
(个人感觉GINI与信息熵的意义类似)

回归方差计算公式：

方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。

因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者回归方差最小的属性作为分裂的方案。
即最小化（分类树）：

这里的pi是指分配到各个子节点的概率

或者（回归树）

CART如何分裂成一棵二叉树？

节点的分裂分为两种情况，连续型的数据和离散型的数据。
CART对连续型属性的处理与C4.5差不多，通过最小化分裂后的GINI值或者样本方差寻找最优分割点，将节点一分为二，在这里不再叙述，详细请看C4.5。
对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值X，Y，Z，则该属性的分裂方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。
以属性“职业”为例，一共有三个离散值，“学生”、“老师”、“上班族”。该属性有三种划分的方案，分别为{“学生”}、{“老师”、“上班族”}，{“老师”}、{“学生”、“上班族”}，{“上班族”}、{“学生”、“老师”}，分别计算三种划分方案的子节点GINI值或者样本方差，选择最优的划分方法，如下图所示：

第一种划分方法：{“学生”}、{“老师”、“上班族”}

预测是否已婚（分类）：

预测年龄（回归）：

第二种划分方法：{“老师”}、{“学生”、“上班族”}

预测是否已婚（分类）：
Gain=0.49

预测年龄（回归）：
Gain=16.36

第三种划分方法：{“上班族”}、{“学生”、“老师”}

预测是否已婚（分类）：
Gain=0.34

预测年龄（回归）：
Gain=21.14

综上，如果想预测是否已婚，则选择{“上班族”}、{“学生”、“老师”}的划分方法，如果想预测年龄，则选择{“老师”}、{“学生”、“上班族”}的划分方法。

CART算法生成决策树的流程总结如下：

CART如何剪枝？

CART采用基于代价复杂度（cost-complexity pruning,CCP）的剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。

CCP剪枝主要分为两部分：

1. 循环剪掉具有最小误差率增益值的子树，直到剩下根节点

2. 利用独立的剪枝集进行评价，获取最佳剪枝树

第一部分-修剪：
令决策树的非叶子节点为{T1,T2,T3…,Tn} 。

1. 计算所有非叶子节点的表面误差率增益值α={α1,α2,α3,…,αn}

2. 选择表面误差率增益值,αi最小的非叶子节点 （若多个非叶子节点具有相同小的表面误差率增益值，选择子节点数最多的非叶子节点）。

3. 对Ti进行剪枝

表面误差增益值α的计算公式如下：

其中，
R(t)表示非叶子节点的代价误差（用节点代替子树），R(t)=r(t)⋅p(t)，r(t)为节点的错误率，p(t)为叶子节点数据量占总数据量的比率（注意是训练集的总量而不是父节点的数据量）；
R(T)表示子树的误差代价，R(T)=∑mi=1ri(t)⋅pi(t)，ri(t)为叶子节点i的错误率，pi(t)表示叶子节点i的数据量占总数据量的比率；
N(T)表示子树叶子节点的个数。

表面误差率增益值公式的由来：

CCP剪枝中，代价(cost) ：主要指样本错分率；复杂度(complexity) ：主要指树t的叶子节点数，定义树t的代价复杂度(cost-complexity)：

其中，
N是训练集样本总数
E是决策树错分样本数
leaft是t子树的叶子数
参数α：用于衡量代价与复杂度之间关系，表示剪枝后树的复杂度降低程度与代价间的关系，如何定义α?

对非叶子节点t来说，剪掉它的子树s，得到新树new_t。 new_t可能会比t对于训练数据分错M个，但是new_t包含的叶节点数，却比t少: (leaft−1)个。令替换后代价复杂度相等：
cc(t)=cc(new_t)
⇒EN+α∗leaft=E+MN+α∗1]
⇒α=MN(leaft−1)

将上文中的α上下同乘N整理后与本式相同

算例：
下图是一颗子树，设决策树的总数据量为40。

该子树的表面误差率增益值可以计算如下：
R(t)=818⋅1840=15
R(T)=13⋅340+49⋅940+16⋅640=640

α=R(t−R(T))N(T)−1=15−6403−1=140
只要求出其他子树的表面误差率增益值就可以对决策树进行剪枝。

第二部分-评估：
随着剪枝的不断进行，决策树将会只剩下根节点，并得到一系列剪枝（嵌套）树 {T0,T1,T2,⋯,Tm}。其中，T0就是完全决策树，Ti+1是对Ti进行剪枝后得到的结果。
之后需要使用独立的剪枝集（非训练集）对之前的剪枝树Ti进行评估，获取最佳剪枝树
最佳剪枝树Tbest是满足以下条件并且包含的节点数最少的那棵剪枝树：

其中，
Ei是树Ti对剪枝集的错分数
E′=min{Ei}
SE(E′)=E′∗(N−E′)N−−−−−−−−√ 其中，N是剪枝集的大小（由方差可以看出来此处应该也是进行了二项分布的拟合）

其实CCP剪枝的第一部分就是一个后向序列（SBS）的子集搜索过程，其使用的评价指标为表面误差率增益值α。最终用于评定子树效果的则是Ei≤E′+SE(E′)的条件和节点个数。