引言
在之前的两节博文《混合和装袋》和《自适应提升》中，我们已经有现成的一堆假设g在手中，我们还如何将这些g混合起来，得到更好的分类器。
混合方式可以分为三种情况：
- 把g看做是同等地位，通过投票或者平均的方式将它们合起来，称为Bagging
- g是不平等的，有好有坏，一个可行的做法是把g当成是特征的转换，然后丢进线性模型训练就可以了，这称为AdaBoost
- 如果是不同的条件下，使用不同的g，那么我们仍然可以将g当做是特征转换，接下来使用一个非线性模型来得到最终的模型参数，这就是该文要介绍的决策树算法
1. 决策树的表达式
决策树的表示方式可以有两种形式。
第一种是从路径的角度（Path View），将每个从根到叶子的路径作为一个假设g，通过不同的条件组合得到最后的G(X)。
第二种是从递归的角度（Recursive View），父树是由子树递归定义的
tree=(root,sub-trees)。
2. CART决策树算法
这里我们讨论的决策树算法以CART算法为例。
2.1 基本流程
- 从数据中看看如何做分支（branching criteria）
- 根据分支将数据分成几块
- 根据不同的数据学习子树
- 得到最终的决策树
所以，上面进行决策树学习的过程中需要考虑4个方面，分别是：分支的数量(number of branches)、分支的判断条件(branching criteria)、终止的条件(termination criteria)、基本的假设(base hypothesis)。
2.2 CART算法
分类回归树(CART,Classification And Regression Tree)算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。
CART根据不同的条件，对数据进行切分，到达叶子节点时，根据剩下的数据进行预测，输出一个常数。
2.3 纯度
CART算法中每个节点（看做是一个决策桩decision stump）对数据进行切分，如果分出来的数据的y都很接近（回归问题）或者都一样（分类问题），那么我们说这样的数据是“纯的”，这样用标量对数据进行预测可以得到比较小的误差。
我们通过上面的公式，来计算对于每一个节点的决策桩来说，分出来的两份数据的纯度是怎样的。该公式通过计算数据集Di（i=1 or 2）的纯度并根据数据集的数量对其进行加权，其加权的意义是如果数据集的数量比较大的话，那个纯度对其比较重要，反之，就不那么重要。
CART通过分出的两部分数据综合起来的纯度对决策桩进行选择，选择“最纯”的分割方式作为当前的分支。
2.4 计算纯度的函数
我们可以将分割出来的数据和回传的常数的误差作为评价纯度的方法，利用数据的y和回传的y_ba的均方误差来评价回归问题的纯度；利用0/1误差函数来评价分类问题的纯度。
如果是分类问题，我们还可以使用一个别的方法。通过基尼不纯度来度量分类问题的纯度问题。
2.5 终止条件
CART中有两种被迫终止的情况，分别是：当yn都一样，这时不纯度为0，于是可以得到gt(x)=yn；另一种情况是xn都一样，就没有继续分割的可能了。
CART树长到被迫停下来的情况，称为完全长成的树（fully-grown tree）。
下面是CART算法完整流程：
CART剪枝算法
一棵完全长成的树的训练误差为0Ein(G)=0，这会有过拟合的危险，在每一个节点上的数据越来越少，导致拟合到这些节点的数据可能是过拟合的。
所以，我们需要一个正则化的机制，来控制模型复杂度，让模型不那么容易出现过拟合现象。
CART剪枝算法从完全生长的决策树的底端剪去一些子树，使决策树变简单，从而能够对未知数据有更准确的预测。
上图告诉我们使用叶子的数目作为正则项（regularizer），最终得到一个正则化的决策树。
关于剪枝的具体做法时：
- 首先得到完全长成的树作为G(0)；
- 然后试图摘掉一片叶子，将所有摘掉一片叶子后的树计算Ein，将最小的那棵摘掉一片叶子的数作为G(1)；
- 如此这般，得到摘掉两片叶子的最优树G(2)，这样不断剪枝，直到根结点，形成一个子树序列；
- 最终对这个子树序列使用
argmin Ein(G)+λΩ(G)来得到最后的输出。
参考资料
机器学习技法课程，林轩田，台湾大学
CART: 分类与回归树
转载请注明作者Jason Ding及其出处
GitCafe博客主页(http://jasonding1354.gitcafe.io/)
Github博客主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354进入我的博客主页
