CART决策树

喜欢ヅ旅行 2022-06-08 13:46 578阅读 0赞

#### 参考： ####

1.  [http://www.cnblogs.com/yonghao/p/5135386.html][http_www.cnblogs.com_yonghao_p_5135386.html]
2.  [http://blog.sina.com.cn/s/blog\_5d6632e70101gh79.html][http_blog.sina.com.cn_s_blog_5d6632e70101gh79.html]

#### 概述： ####

1.  CART **既能是分类树，又能是回归树**.
2.  当CART是分类树时，采用**GINI值**作为节点分裂的依据；当CART是回归树时，采用样本的**最小方差**作为节点分裂的依据；
3.  CART是一棵**二叉树**。

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

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

#### 详述： ####

接下来将以一个实际的例子对CART进行介绍：  
![这里写图片描述][SouthEast]

从以下的思路理解CART：

##### 分类树？回归树？ #####

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

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

![这里写图片描述][SouthEast 1]

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

##### CART如何选择分裂的属性？ #####

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

**GINI值的计算公式：**

GINI=1−∑i∈Ip2i

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

**回归方差计算公式：**

σ=∑i∈I(xi−μ)2−−−−−−−−−−√=∑i∈Ix2i−nμ2−−−−−−−−−−√

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

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

Gain=∑i∈Ipi⋅Ginii

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

或者（回归树）

Gain=∑i∈Iδi

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

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

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

![这里写图片描述][SouthEast 2]

预测是否已婚（分类）：

Gain=∑i∈IpiGinii=37\[1−(23)2−(13)2\]\+47\[1−(34)2−(14)2\]=0.4

预测年龄（回归）：

Gain=∑i∈Iδi=122\+182\+212−3⋅172−−−−−−−−−−−−−−−−−−−√\+262\+472\+362\+292−4⋅32.52−−−−−−−−−−−−−−−−−−−−−−−−−√=34.71

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

![这里写图片描述][SouthEast 3]

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

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

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

![这里写图片描述][SouthEast 4]

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

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

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

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

![这里写图片描述][SouthEast 5]

##### 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))N(T)−1

其中，  
 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)**：

cc(t)=EN\+α∗leaft

其中，  
 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。

![这里写图片描述][SouthEast 6]

该子树的表面误差率增益值可以计算如下：  
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≤E′\+SE(E′)

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

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

[http_www.cnblogs.com_yonghao_p_5135386.html]: http://www.cnblogs.com/yonghao/p/5135386.html
[http_blog.sina.com.cn_s_blog_5d6632e70101gh79.html]: http://blog.sina.com.cn/s/blog_5d6632e70101gh79.html
[SouthEast]: /images/20220608/bade6780203a4fac87e2e86d3fa478c7.png
[SouthEast 1]: /images/20220608/ea182f80b5894c03a8e4e48987db21d5.png
[C4.5]: http://blog.csdn.net/xiaohukun/article/details/78093720
[SouthEast 2]: /images/20220608/a43619519a2045b1b04cd00e42188e26.png
[SouthEast 3]: /images/20220608/8b6c398b66684eef86e587a0795e37c2.png
[SouthEast 4]: /images/20220608/093df7ce51ff4d4fbfd76202c5896401.png
[SouthEast 5]: /images/20220608/68197dfdaee242bb84284b1975efacd8.png
[SouthEast 6]: /images/20220608/c64927dfa13a439d8b8b34816814fd68.png