决策树CART与ID3,C4.5联系与区别

CART与ID3和C4.5相同都由特征选择，树的生成，剪枝组成。但ID3和C4.5用于分类，CART可用于分类与回归。web

CART是在给定输入随机变量X条件下输出随机变量Y的条件几率分布，与ID3和C4.5的决策树所不一样的是，ID3和C4.5生成的决策树能够是多叉的，每一个节点下的叉树由该节点特征的取值种类而定，好比特征年龄分为（青年，中年，老年），那么改节点下可分为3叉。而CART为假设决策树为二叉树，内部结点特征取值为”是”和”否”。左分支取值为”是”，有分支取值为”否”。这样的决策树等价于递归地二分每个特征，将输入空间划分为有限个单元，并在这些单元上预测几率分布，也就是在输入给定的条件下输出条件几率分布。算法

CART分类树

特征选择

CART分类树经过基尼指数选择最优特征，同时决定该特征的最优二值切分点，而ID3和C4.5直接选择最优特征，不用划分。svg

基尼指数

分类问题，假设有K个类，样本点属于第k个类几率为pk，则几率分布的基尼指数定义为

对于二类分离，样本点属于第一个类的几率p，基尼指数

对于给定样本集合D,基尼指数

Ck是D中属于第k类的样本子集，K是类的个数。
若是样本集合D根据特征A是否取某一可能值a被分割为D1和D2两部分。
（即在某一特征多个取值中,取其一个将其分为”是”其余为”不是”）

在特征A下，集合D的基尼指数定义为

基尼指数越大，样本集合不肯定性越大。函数

CART树生成

(1) 设结点的训练数据集为D,计算现有特征对该数据集的基尼指数.此时，对于每一个特征，每次取其中一个每一个可能取得值，根据样本点对该值的测试结果为”是”或”否”将D分红2部分，并计算基尼指数.
(2) 在全部可能的特征，以及他们全部可能的切分点中，选择基尼指数最小的特征，该选择的特征为最优特征，该特征中的切分点为最优切分点，依照最优特征和最优切分点生成二叉树，并把训练数据集分配到子节点中。
(3)对两个子节点递归调用 (1) (2) ,直至知足中止条件
(4)生成CART决策树。
中止条件是样本个数小于预约阈值，或样本基尼指数小于预约阈值，或没有更多特征。学习

而ID3，C4.5在(1) (2)处与CART不一样，ID3计算信息增益，C4.5计算信息增益比，首先求全部特征的信息增益或信息增益比，其中计算的数值是针对每个特征，不将特征划分，然后以该特征将树延伸，在父节点肯定的条件下，继续对子节点求全部特征的信息增益，后在划分。
CART则为求全部特征下的全部切分点后进行比较来划分。测试

CART树剪枝

CART剪枝算法分两部，首先从生成算法产生的决策数T0底端开始不断剪枝，知道T0的根节点，造成子树序列{T0,T1,T2…Tn};而后经过交叉验证法在独立的验证数据集上对与子树测试，从中选择最优子树。优化

接下来咱们从ID3,C4.5一步步推出CART树的剪枝.net

在ID3,C4.5中

决策树的剪枝经过极小化决策树的总体损失函数或者代价函数来求解。
决策树经过经验熵来生成。
设树T的叶结点个数为|T|, t 是树 T 的叶结点， 该叶结点上有 N(t) 个样本点，其中 k 类的样本点的个数为 N(tk) 个， k 为结果的类别， Ht(T) 为叶结点上经验熵，则损失函数可定义为

其中经验熵为

在损失函数中将第一项记做

则
3d

C(T)表示模型对训练数据的预测偏差，即模型对训练数据的拟合程度，|T| 表示模型的复杂度，参数 a>=0 控制二者直接的影响，较大的 a 促使选择模型较简单的树，而小的则相反，a=0 意味指不考虑模型复杂度，只与拟合程度有关。
剪枝，当a肯定时，选择损失函数最小的模型，即损失函数最小的树，为最好的树。xml

从中咱们能够看出一些关系，首先ID3,C4.5，中a的取值是固定的，即树要剪枝首先咱们要给出生成算法给出的生成树和一个固定的a值。
那么当a不是固定的时候，则整个损失函数由预测偏差，a和模型复杂度共同决策。
然后从

该式子中咱们能够的得出C(T)做为模型的预测偏差的值，经过累加每个叶结点（即T个叶结点）的预测偏差而得出C(T)。
这个结论对于CART一样适用，由于CART预测偏差用的为基尼指数，但求和都是结点偏差和。

在CART剪枝中

CART剪枝分为剪枝成子树序列，并经过交叉验证选取最优子树。

1.剪枝，成子树序列

在剪枝过程当中，计算子树的损失函数：

其中，T为任意子树，C(T)为对训练数据的预测偏差（如基尼指数），|T|为子树的节点个数，a>=0为参数，Ca(T)为参数是a时子树T的总体损失，参数a权衡训练数据的拟合程度和模型的复杂度。
从上方a不是固定的时候，则整个损失函数由预测偏差，a和模型复杂度共同决策，得出a大的时候，最优子树Ta偏小；当a小的时候，最优子树Ta的树较大，a=0时总体树最优，a->∞时，根结点组成的单节点树最优。
且认为不一样的a值，能够肯定一棵不一样的最优化的树，或者说一个区间内的a值能够肯定一颗最优化的树
即将a不断增大，利用a生成Ta这棵最优子树

为了获得全部的可能生成的最优化树{T0,T1,T2,…Tn},咱们须从底向上，每次进行一次剪枝，经过获得的树认为是最优化树反推a
具体的，从总体树T0开始剪枝，对于T0的任意内部结点t，结点下有若干子节点，把t下的子树的若干叶节点称为Tt。
剪枝后(即t下的子树减去后，t变为叶节点)的损失函数

剪枝前的损失函数

注意这里的损失函数都是某个叶结点的损失函数，但为何能够只求叶节点的损失函数，由于在上面的分析ID3,C4.5中得出了C(T)做为模型的预测偏差的值，经过累加每个叶结点（即T个叶结点）的预测偏差而得出C(T)。所以单独求某个叶结点并无什么问题。

如今就是求解a，a如何求解？
当a=0或充分小时，不等式

由于叶结点越多预测偏差应该越小。
当a不断增大时，在某个a点有

当a再增大时，不等式反向。所以只要

Tt与t有相同的损失函数，而t结点少，所以t比Tt更可取，对Tt进行剪枝。
接下来对T0这棵总体树中的每个结点t，计算

这个g(t)表示剪枝后的总体损失函数减小程度，实际上能够看为是否剪枝的阈值，对于某个结点当他的参数a=g(t)时，剪和不剪整体损失函数时同样的。若是a增大则不剪的总体损失函数就大于剪去的。即a大于g(t)该剪，剪后会使总体损失函数减少，而a小于g(t)则不剪，剪后会使总体损失函数增大。
这样a缓慢增大，随着a的增大，在一个区间内可肯定一棵最优的剪枝树

而咱们求每棵树，并认为他是最优剪枝树。

g(t)则表明每一棵树的a的最优区间内的最小值

即在T0中剪去g(t)最小的Tt,获得的子树为T1,同时将最小的g(t)设为a1,那

么T1为区间[a1,a2)的最优子树。

如此这样下去，将全部可能的树的状况剪枝直到根节点，在这个过程当中则

会不断增长a，产生新的区间，最后a的全部可能的g(t)取值所有肯定。

2.经过交叉验证选取最优子树

具体的利用独立的验证数据集，测试子树序列T0,T1,…Tn中各棵子树的平

方偏差或基尼指数。平方偏差或基尼指数最小的决策数被认为是最优决策

数，由于咱们每肯定一棵子树就会肯定其参数a值，因此最优子树Tk肯定，对应ak也肯定，即获得最优决策数Ta。

参考文献：

1.决策树之剪枝原理与CART算法
2.知乎：Cart树怎么进行剪枝 3.李航. 统计学习方法[M]. 北京：清华大学出版社，2012