【机器学习】CART决策树原理及python实现

本文为博主学习机器学习决策树部分的一些笔记和思考，以及python编程实现算法的具体步骤

决策树(decision tree) 是一类常见的机器学习方法. 在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法. 在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系.

对于决策树的原理和概念以及信息增益的计算部分不再赘述，对此部分感兴趣或者希望了解的朋友可以翻阅周志华《机器学习》P73～P78

本文重点介绍CART决策树

一、基本概念

CART决策树[Breiman et al., 1984] 使用“基尼指数”来选择划分属性. 这是西瓜书上给出的定义. 通过大量文章的阅读将CART决策树关键点整理如下：

1. CART决策树既能是分类树，也能是回归树
2. 当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据
3. CART是一颗二叉树 (关于这一点其实我存在疑惑，准备去问问老师或者同学。因为在我编程实现的过程中忽略了这一点，因为西瓜树上并没有指明CART算法必须生成二叉树. 而其中西瓜数据集中的离散属性取值$N\ge 3$，因此我在编程过程中生成的是多叉树. 所以是否考虑在属性取值较少的情况下，CART算法不用一定生成二叉树)

二、选择划分属性

目标取值为一个有限集合的树模型称为分类树，而目标值是连续值(典型的真实数值)的树模型称为回归树。分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么CART是如何评价节点的纯度呢？如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度. 节点越不纯，节点分类或者预测的效果就越差.

1、CART决策树作为分类树

CART决策树作为分类树时，特征属性可以是连续类型也可以是离散类型，但观察属性(即标签属性或者分类属性)必须是离散类型。

划分的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。

如果是分类树，CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可以用基尼值来度量：
$$Gini(D)=\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}$$

$$=1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2$$

直观来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小，则数据集$D$的纯度越高.

属性$a$的基尼指数定义为
$$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v).$$
所以我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即$a_{\ast }={arg}_{a\in A}minGini\_index(D,a)$.

2、CART作为回归树

而如果是回归树，其建立算法同CART分类树大部分是类似的。除了上述中提到的两者样本输出的不同，CART回归树和CART分类树的建立和预测主要有以下两点不同：

• 连续值的处理方法不同
• 决策树建立后做预测的方式不同

回归树对于连续值的处理使用了常见的和方差的度量方式，即：
$$\sigma =\sqrt{\sum _{i\in I}(x_i-\mu {)}^2}=\sqrt{\sum _{i\in I}{x_i}^2-n{\mu }^2}.$$
方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。

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

即最小化分类树:
$$Gain=\sum _{i\in I}{p}_i\cdot Gin{i}_i$$
或者回归树：
$$Gain=\sum _{i\in I}{\sigma }_i.$$

三、剪枝处理

剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段. 决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(post-pruning). 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点; 后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

预剪枝使得决策树很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销. 但另一方面，预剪枝由于基于“贪心”本质将某些禁止展开的分支的后续划分也一并禁止，而其中某些后续划分有可能会导致泛化性能显著提高，给预剪枝决策树带来了欠拟合的风险.

后剪枝决策树通常比预剪枝决策树保留了更多的分支，且在一般情况下欠拟合风险很小，泛化性能往往也能优于预剪枝决策树。但由于其是在生成完全决策树之后进行的，并且要自底向上考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大很多.

四、连续值处理

由于现实学习任务中常会遇到连续属性，由于连续属性的可取值树木不再有限，此时连续属性离散化技术可派上用场. 最简单的策略是采用**二分法(bi-partion)**对连续属性进行处理，这正是C4.5决策树算法中采用的机制.

给定样本集合$D$和连续属性$a$，假定$a$在$D$上出现了n个不同的取值，将这些值从小到大进行排序，记为{$a^1,a^2,...,a^n$}. 基于划分点$t$可将子集$D_t^{-}$和$D_t^{+}$，其中$D_t^{-}$包含那些在属性$a$上取值不大于$t$的样本，而$D_t^{+}$则包含那些在属性$a$上取值大于$t$的样本. 所以对连续属性$a$，我们可考察包含$n-1$个元素的候选划分点集合
$$T_a=\left\{\frac{a^i=a^{i+1}}{2}|1\le i\le n-1\right\}$$
即把区间$\left[a^i,a^{i+1}\right)$的中位点 a i + a i + 1 2 \frac{a^i+a^{i+1}}{2}