决策树（下）
在决策树（上）中我们了解了ID3和C4.5算法，这两种算法都使用了较为复杂的熵来度量，使用了复杂的多叉树，并且只能处理分类问题，针对这些缺点，CART(Classification And Regression Tree)做了改进，可以处理分类，也可以处理回归。
分类：预测目标是离散值。
回归：预测目标是连续值。
基尼指数（Gini）
从之前的内容我们了解到ID3使用信息增益来选择特征，C4.5使用信息增益率来选择特征，同样对于我们的CART需要使用基尼系数来进行特征选择。
基尼系数代表了了模型的不纯度，基尼系数越小，不纯度越低，特征越好，这和信息增益比是相反的。先来看一下基尼系数的定义：
（Ck是D中属于第K类的样本子集，K是类的个数）
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类，与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切分成两份，分别进入左右子树，特征A的基尼指数为：
CART分类树对连续特征和离散特征的处理
CART分类树算法对连续值的处理，思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。
具体思路：m个样本的连续特征A有m个，从小到大排列a1，a2，…，am，则CART取相邻两样本值的平均数做划分点，一共取m-1个，其中第i个划分点Ti表示为：Ti = (ai + ai+1)/2。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at，则小于at的值为类别1，大于at的值为类别2，这样就做到了连续特征的离散化。
CART分类树算法对离散值的处理，采用的思路：不停的二分离散特征。
在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别A1,A2,A3，我们会在决策树上建立一个三叉点，这样决策树是多叉树。
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的一颗子树中，离散特征只会参与一次节点的建立。
CART分类树
输入：训练集D，基尼系数的阈值，样本个数阈值。
输出：决策树T。
算法从根节点开始，用训练集递归建立CART分类树。
Step1：对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，则返回决策子树，当前节点停止递归；
Step2：计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归；
Step3：计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数；
Step4：在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。
Step5：对左右的子节点递归的调用1-4步，生成决策树。
注：对生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。
CART回归树
输入：训练集D
输出：回归树
Step1：针对数据集D（此时树的深度为0），遍历每一个特征Feature的每一个值Value，对于每一个Value将原数据集S分裂成2个集合：左集合S_left(<=Value的样本)、右集合S_right(>Value的样本)，每一个集合也叫做一个结点。分别计算这2个集合的均方误差（mse），找到使得（left_mse+right_mse）最小的那个Value，记录下此时的Feature名称和Value，这个就是最佳分割特征以及最佳分割值。
使用MSE的好处在于其一阶导数和二阶导数可求并好求。
Step2：找到最佳分割Feature以及最佳分割Value之后，用该Value将集合S分裂成2个集合：左集合S_left、右集合S_right，每一个集合也叫做一个结点。此时树的深度depth += 1。
Step3：针对集合S_left、S_right分别重复步骤1,2，直到达到终止条件。
Step4：最后生成的并且不再进行分裂的集合就叫做叶子结点。落在该叶子节点内的样本的预测值，就是该叶子结点的值。同一个叶子结点中的样本具有同一个预测值。
决策树的优化（剪枝）
当我们把所有的特征都放入决策树中的时候，树的模型会显得很大，同时也大概率的会造成过拟合现象的产生，为了避免该现象的发生，我们需要对决策树进行剪枝。
决策树的剪枝通常有两种方法：预剪枝和后剪枝。
预剪枝
预剪枝的核心思想是在树中节点进行扩展之前，先计算当前的划分是否能够带来模型泛化能力的提升，如果不能则不再继续生长子树。
预剪枝对于何时停止决策树的生长有如下的几种方法：
（1）当树达到一定深度的时候，停止树的生长。
（2）当达到前节点的样本数量小于某个阈值的时候，停止树的生长。
（3）计算每次分裂对测试集的准确度的提升，当小于某个阈值的守，不在继续扩展。
后剪枝
后剪枝的思想是让算法生成一颗完全生长的决策树，然后从最上层计算是否剪枝，剪枝过程将子树删除，用一个叶子节点代替，该节点的类别同样按照多数投票的原则进行判断。
举一个西瓜书中的例子：
有如下的一个完全生长的决策树：
剪枝的考虑以及剪枝后的结果如下：
常见的后剪枝的方法包括：错误率降低剪枝，悲观剪枝，代价复杂度剪枝，最小误差剪枝，CVP，OPP等，这些方法各有利弊，这里不再一一介绍。
决策树算法的对比
决策树算法优缺点
优点：
- 简单直观，生成的决策树很直观。
- 基本不需要预处理，不需要提前归一化和处理缺失值。
- 使用决策树预测的代价是O(log2m)。m为样本数。
- 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
- 可以处理多维度输出的分类问题。
- 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以很好解释。
- 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
- 对于异常点的容错能力好，健壮性高。
缺点：
- 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
- 决策树会因为样本发生一点的改动，导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
- 寻找最优的决策树是一个NP难题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习的方法来改善。
- 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
- 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
