决策树、随机森林与Boosting

      树形模型是机器学习中最为常用的模型之一，其同KNN算法一样，也是弱假设型模型。
      决策树
      决策树是bagging、随机森林以及boosting的基础，所以我们从决策树开始讲起。
      
                
                
                
                
      决策树主要可以分为两种，一种为回归树（图1），另一种为分类树（图2）。回归树和分类树原理大同小异，我们先从回归树讲起。
      回归树
      回归树的原理很简单，即选择一个变量，确定一个决策点，而后将数据分成两份。如图1所示，我们先选择year为决策变量，当它小于4.5时，我们预测的y值为5.11，如若不是，我们就需要继续做决策，即在year大于等于4.5的前提下，当Hits小于117.5时，预测y值为6，否则为6.74.
      
                
                
      那么这些值是怎么预测出来的呢？如上图所示，前面的回归树可以通过平面图表示出来。当我们确定第一个决策点为year小于4.5时，我们的数据就被分成了两个部分，而当我们队year大于等于4.5的数据继续做决策时，数据就进一步被分割。最终数据被分成了三大块，而每块区域观测点的y值均值即是我们的预测值。当然，决策树的每个部分都可以被进一步分割，而数据也可以被分成更多的区域（如下图所示）。
      
                
                
      然而，重点却是，我们该如何确定决策变量和决策点呢？
      回归树选择决策变量与决策点的原理其实和OLS方法类似。我们可以计算，预测值同观测值差距的平方和（RSS）。即
                
                
      以最前面的例子来说，我们的数据被分成了R1，R2，R3三部分，我们自然可以计算每个部分的RSS然后将它们相加，当然，数据可以被分成n个部分，那么也就是n部分的RSS相加。当总体RSS最小时，也即是最优解。
      然而，这种解法实际上并不可能，因为数据有非常多种分法，我们太不可能计算出每种分发再做对比。于是我们选择了贪婪算法，即我们先计算在第一次决策时，两部分的RSS在何种情况下最小，在计算出决策变量和决策点后，立马忘掉这次决策，只考虑如何使下一次的决策产生最小的RSS。即我们每次决策我们只考虑两个区域的RSS：
                
                
      至于要种出一棵多大的树，则取决于参数的选择，我们可以规定当每个区域的观测点少于一定数额就停止运算，也可以规定当区域超过某个数值时停止运算。
      修剪枝节
      值得注意的一点是，RSS最小并不能确保模型的预测能力就最佳。我们可以回顾一下OLS方法的RSS。OLS中RSS等价于R方。R方越大表面上意味着我们的模型解释掉了更多的变异，但只要我们在OLS模型中加入更多变量，R方一边情况下会持续增大。如果R方是靠此种方法增大，那么很容易导致模型的过拟合而失去预测能力（详细见该系列的第一篇）。对于决策树来说情形也是如此。只要我们加入足够多的变量，那么就可以得到一棵庞大的决策树，只要庞大到每个观测点占据一个区域，那么RSS就是0。然而这种模型往往过拟合了，并没有什么预测能力。一旦我们也能够这个模型去预测另一套数据，就会产生问题。为了解决这个问题，我们就需要一棵中等规模的树。
      Tree pruning是最为常见的修剪方法，类似于Lasso算法对OLS的约束。
                
                
      我们给RSS施加一个约束项，那么那些重要性并不高的枝节就会被剔除出模型。其中alpha是一个位于0-1之间的约束常数（类似于lasso中的lambda），T则是terminal node的数量（即最后被分成几个区域）。terminal node和alpha则需要根据交叉验证中所产生的MSE来选择（MSE的解释见第一篇）。实践中最简单的方法就是写个for loop计算MSE。不过在实际建模中我们很少用到tree pruning，因为random forest或者boosting的效果一般要高于tree pruning。
      
      分类树
      分类树同回归树只有两点不同。第一是它产生的结果是类别，而不是具体数值，因此分类树模型所分割的每个区域就代表一种类别区域，不需要求平均值。第二是我们在选择决策变量和决策点时不再根据RSS，因为分类树中没有RSS。不过我们也不会根据error rate（即分错的概率），因为分类树模型对error rate不够敏感。我们的判断标准为Gini指数或熵：
                
                
                
                
      在公式中，pmk表示k类观测点在第m区域中的比例。对Gini和熵来说，当pmk接近0或接近1时，G和D就会接近0，即纯度越高（某个区域中某类观测点的比例越高）。换句或说，Gini系数和熵并和error rate其实成正比，因此它们能够用来衡量模型好坏的指标。
      Bagging
      Bagging的全称为Bootstrap aggregating，即通过Bootstrap方法来合并多棵决策树。Bootstrap是一种在样本中进行抽样的方法。比如我们现在有一个包含了n个观测点的样本，现在我们可以通过有放回抽样地抽取包含n个观测点的bootstrap样本。有放回抽样意味着，我们先抽取一个观测点，然后将它放回，之后再抽取一个观测点，第二个观测点有1/n的几率抽到第一个观测点。如此重复直到抽取出N个观测点组成一个新的训练集。如果我们计算下概率，可以发现训练集平均会包含原样本中三分之二的观测点。每个训练集可以训练出一棵决策树，我们把训练的m棵决策树的结果取均值就是bagging的预测结果（如果是分类树，可以看均值结果是否大于0.5，大于0.5即为1，当然，分界线也可以按情况自己定），其中决策树的数量可以自己定。bagging模型同单棵决策树模型相比，可以缩小方差因此提高准确率。
      随机森林
      Bagging是随机森林中的一个特例。随机森林和bagging唯一的区别在于，当我们把p个变量放到模型中时，bagging在训练每棵决策树时会将所有的变量都用上，而随机森林则只随机使用q个变量（q属于p）。我们常常会将q的值设置成根号p，但也可以随自己调。随机森林会每次随机选择q个变量种出一棵决策树，最后也同样是将决策树的结果合并。这么做的好处在于，有些变量看上去在训练集中非常重要，但实际预测效果并不佳。在bagging模型中，这类变量每次都会在决策树上端，起到最重要的作用，而它们实际上却不是好的预测变量，因此削弱了模型的预测能力。而在随机森林中，它们在很多决策树中不会被选到，几乎所有的变量都有平等的机会进入到模型中。因此只要我们种的树足够多，我们就可以削弱那些strong但预测效果不佳的变量，从而提升预测准确性。一般情况下，随机森林的OOB MSE和传统MSE要分别小于bagging的OOB MSE和传统MSE。
      随机森林因为绝佳的预测能力和运行效率，绝对可以称得上数据科学中被用得最多的机器学习算法之一。
      Out of Bag
      Bagging和随机森林方法还可以计算out of bag(OOB) MSE。由于在bagging和随机森林中，我们通过进入训练集的样本建模而后预测没有进入训练集的那些的样本的y值，所以当我们合并这些被预测的y值时，这些y值和那些训练集中的样本不相关。因此，我们可以通过OOB预测值和原来数据中的y值计算出OOB MSE（即OOB预测值和观测点的差距的平方和）。当样本量足够大时，OOB MSE会比传统的leave one out计算出来的MSE相似。如果样本不够，往往会略低，但总体来说呈正比，因此和传统MSE拥有相似的判定建模好坏的标准。
      Boosting
      Boosting是另外一种合并决策树的方法。不过Boosting采用的则是种出一棵棵相互关联的小树进行合并，而不是种出一堆互不关联的决策树进行合并。Boosting会通过上一次种出来的决策树所产生的残差来种出下一棵树，而后将原先已经存在的结果同根据残差种出来的小树的结果相加，如此循环往复，因此每次种的树都务必要小。同bagging和随机森林不同的一点是，bagging和随机森林所种的树由于相互独立，因此越多越好，多棵决策树合并不会产生过拟合的问题。但boosting则不同，由于根据残差种树，原理就类似于R方，如果合并的树过多，很可能出现过拟合的问题。因此我们就需要用交叉验证的MSE来决定到底种多少棵树才合适。