03-决策树（cart）

1. CART分类树算法的最优特征选择方法

我们知道，在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

具体的，在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为：

image.png

如果是二类分类问题，计算就更加简单了，如果属于第一个样本输出的概率是p，那属于第二个类别的概率为（1-p）则基尼系数的表达式为：

image.png
对于给定的样本D，假设有k个类别，第k个类别的数量为Ck,则样本D的基尼系数表达式为： image.png
特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为： image.png
gini指数Gini(D,A)表示特征A不同分组的数据集D的不确定性。gini指数值越大，样本集合的不确定性也就越大，这一点与熵的概念比较类似

所以在此，基于以上的理论，我们可以通过gini指数来确定某个特征的最优切分点(也即只需要确保切分后某点的gini指数值最小)，这就是决策树CART算法中类别变量切分的关键所在。是不是对于决策树的CART算法有点小理解啦！其实，这里可以进一步拓展到我们对于类别变量的粗分类应用上来。比如我某个特征变量下有20多个分组，现在我只想要5个大类，如何将这个20多个类合并为5个大类，如何分类最优，以及如何找到最优的分类。这些建模初期的数据预处理问题其实我们都可以用gini指数来解决。
例子：

image.png
当根据是否有房来进行划分时，Gini系数增益计算过程为 image.png
Gini(左子节点)=1−(0/3)^2−(3/3)2=0
Gini(右子节点)=1−(3/7)^2−(4/7)2=0.4898
Gini(D,A1) = 7/10 * 0.4898 + 3/10 * 0 = 0.343
若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的
1、{married} | {single,divorced}
2、{single} | {married,divorced}
3、{divorced} | {single,married}
的Gini系数增益。
当分组为{married} | {single,divorced}时，Sl表示婚姻状况取值为married的分组，Sr表示婚姻状况取值为single或者divorced的分组
Δ{婚姻状况} = 4/10×0+6/10×[1−(3/6)^2−(3/6)2]=0.3
当分组为{single} | {married,divorced}时，
Δ{婚姻状况}=0.4/10×0.5+6/10×[1−(1/6^)2−(5/6)2]=0.367
当分组为{divorced} | {single,married}时，
Δ{婚姻状况}=2/10×0.5+8/10×[1−(2/8)^2−(6/8)2]=0.4
对比计算结果，根据婚姻状况属性来划分根节点时取Gini系数最小的分组作为划分结果，也就是{married} | {single,divorced}。
最后考虑年收入属性，我们发现它是一个连续的数值类型。我们在前面的文章里已经专门介绍过如何应对这种类型的数据划分了。对此还不是很清楚的朋友可以参考之前的文章，这里不再赘述。

对于年收入属性为数值型属性，首先需要对数据按升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。倘若以中间值65作为分割点。Sl作为年收入小于65的样本，Sr表示年收入大于等于65的样本，于是则得Gini系数增益为

Δ(年收入)=1/10×0−9/10×[1−(6/9)^2−(3/9)2]=0.4
选择基尼系数最小的最为根节点，以此类推
最后我们构建的CART如下图所示：

image.png
总结上面的例子：
1）、对特征属性值进行划分，如下所示，假设某个特征的有三个属性分别是（结婚、单身、离婚），然后对这三个特征进行组合，组合如下：
{结婚，（单身，离婚）}
{单身，（结婚，离婚）}
{离婚，（结婚，单身）}
2）、计算每个特征值组合的基尼系数，取最小的基尼系数，作为该特征的基尼系数
3）、比较每个特征的基尼系数，取最小的基尼系数的特征作为根节点
4）、根据该特征组合进行左右子节点进行划分
5）、根节点的下一个子节点取第二小的基尼系数的特征作为节点，以此类推，直到所有特征遍历完

2. CART分类树算法对于连续特征和离散特征处理的

对于CART分类树连续值的处理问题，其思想和C4.5是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益比，则CART分类树使用的是基尼系数。

具体的思路如下，比如m个样本的连续特征A有m个，从小到大排列为a1,a2,...,am,则CART算法取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为： image.png

。对于这m-1个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与ID3或者C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。

回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。

3. CART分类树建立算法的具体流程

算法输入是训练集D，基尼系数的阈值，样本个数阈值。

输出是决策树T。

我们的算法从根节点开始，用训练集递归的建立CART树。

1. 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
2. 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
3. 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和上篇的C4.5算法里描述的相同。
4. 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
5. 对左右的子节点递归的调用1-4步，生成决策树。

4. CART回归树建立算法

CART回归树和CART分类树的建立算法大部分是类似的，所以这里我们只讨论CART回归树和CART分类树的建立算法不同的地方。

首先，我们要明白，什么是回归树，什么是分类树。两者的区别在于样本输出，如果样本输出是离散值，那么这是一颗分类树。如果果样本输出是连续值，那么那么这是一颗回归树。

除了概念的不同，CART回归树和CART分类树的建立和预测的区别主要有下面两点：

1)连续值的处理方法不同

2)决策树建立后做预测的方式不同。

对于连续值的处理，我们知道CART分类树采用的是用基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型，但是对于回归模型，我们使用了常见的和方差的度量方式，CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。表达式为：

image.png

其中，c1为D1数据集的样本输出均值，c2为D2数据集的样本输出均值。

对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

除了上面提到了以外，CART回归树和CART分类树的建立算法和预测没有什么区别。

5. CART算法小结

上面我们对CART算法做了一个详细的介绍，CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。当然CART树最大的好处是还可以做回归模型，这个C4.5没有。下表给出了ID3，C4.5和CART的一个比较总结。希望可以帮助大家理解。

image.png

看起来CART算法高大上，那么CART算法还有没有什么缺点呢？有！主要的缺点我认为如下：

1）应该大家有注意到，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，暂时不了解

2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。