决策树

从最简单的地方开始吧，决策树。

前面随机森林的部分有写过，最简单的决策树就是从常人的思维方式产生的，拿比较接地气的例子来说，某人判断相亲对象是否应该再约的过程，就是一个典型的决策树：

某人会首先关注性别是否相同，同性当然就拜拜了，异性的话就先看看年龄，如果在20-30之间，就继续看看长相，如果年龄超过30岁，就直接问问收入，接着看看性格，学历，大概就知道自己喜不喜欢，要继续约会还是直接拜拜。以上这颗决策树是某人通过对十几个相亲对象的考察，结合自己的喜好建立的模型（这个过程就是机器学习中的“训练”），这样建立模型的好处在于，当下一个相亲对象出现时，可以在很短的时间内做出判断，减少犹豫和纠结的时间。

是不是很好理解？，基本跟工作流程图没啥区别。我们知道所有一般化的常识之所以能够升级为高级的知识，都是在实践中为了解决困难而慢慢变得复杂和专业。相亲的问题固然简单，但是遇到诸如预测天气、预测比赛结果、预测疾病诊断、预测股市涨跌之类的情景，上面这种简单的决策机制就不好办了。说不好办，主要也是一下几个因素造成的：

1. 对于某一类现象（比如天气），影响它的因素往往成百上千（比如气压、风速、湿度、温度、日照时间等等）；

2. 这些因素往往同时包括离散变量和连续变量，甚至有时需要预测的值是连续变量（例如冷和热是离散变量，而温度是连续变量，上述相亲例子中全是离散变量）；

3. 这些因素对于分类效果的贡献往往千差万别，有些甚至几乎没有什么贡献（例如在预测天气的时候考虑是否有冤案发生）；

4. 数据采集阶段可能没有获得高质量的样本群，或者样本采集有严重偏好（例如收集了北方的天气数据去预测南方天气）；

在解决这些问题之前，决策树建立需要考虑的最重要的一件事，就是如何决定下一个节点该如何分解。比如当我们获得了温度、湿度和风速的数据之后，如何确定第一个考虑的因素，以及如何划分这个因素，这里就要引入三个概念：信息增益、信息增益比和基尼系数（Gini index）。这三个概念都是衡量一个因素对分类的贡献程度，但是算法不一样：

1. 信息增益：

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数，c为某个节点中包含的样本数，k为该因素的取值范围。从公式可以看出，如果一个因素为阳性时，有更多样本也为阳性（例如当湿度很高的时候，往往会下雨），那么这个因素的信息增益就会比较高。

2. 信息增益比：

信息增益的问题在于，拥有更大取值范围的因素会占便宜，于是可以计算信息增益比，信息增益率 = 信息增益 / 属性熵，但是这种算法依然有问题，拥有更小取值范围的因素会占便宜。

3. Gini系数：

基尼系数相对而言比较合理，

pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)；基尼系数越高的因素，就可以作为划分节点的首选。

对应上述三种计算信息增益的方法，决策树被分为ID3，C4.5和CART类型。想要真正理解这三种算法，还得去实际的案例中，仔细看看计算过程，这里为了偷懒，贴一篇比较详细的 决策树 - 小小猎魔人 - 博客园，当然，西瓜书里也有。

回归树

然后，是回归树，看名字就知道跟决策树是一回事，只不过预测对象从离散变量换成了连续变量，例如从预测是否下雨，到预测单日降雨量。以CART树为例，在处理分类问题和回归问题中的相同和差异：

相同：

        在分类问题和回归问题中，CART 都是一棵二叉树，除叶子节点外的所有节点都有且仅有两个子节点；

        所有落在同一片叶子中的输入都有同样的输出。

差异：

        在分类问题中，CART 使用基尼指数（Gini index）作为选择特征（feature）和划分（split）的依据；在回归问题中，CART 使用 mse（mean square error）或者 mae（mean absolute error）作为选择 feature 和 split 的 criteria。

        在分类问题中，CART 的每一片叶子都代表的是一个 class；在回归问题中，CART 的每一片叶子表示的是一个预测值，取值是连续的。回归树同样要首先面对节点如何划分的问题，与决策树不同的是，回归树是根据均方误差（MSE）作为标准来衡量划分的优劣，选取MSE最小的元素及其取值作为划分的依据。MSE的计算方法如下：

j表示第j个元素（例如湿度），s是j的某个取值（例如湿度=80%），yi表示观测值（例如降雨量100毫米），xi表示属于该节点的样本，c1和c2表示从父节点划分出来的两个节点中所有样本的均值（因为均值可以保证每个节点的mse最小）。下面通过一个习题来解释上面公式的计算过程，习题来自李航的《统计学习方法》第5章决策树习题中的5.2题：

用平方误差损失准则生成一个二叉回归树：

首先，我们取s=1（即s取xi变量的第一个值作为划分的界限），也就是大于4.5的和小于等于4.5的分开，于是，原本的10个样本被分成两组：R1 = {1}，R2={2,3,4,5,6,7,8,9,10}，然后计算c1和c2，即两组的均值，R1只有一个值，均值就是4.5，R2有9个值：

这样，得到c1=4.5，c2=6.85。

接着，我们取s = 2（即s取xi变量的第2个值作为划分的界限），也就是大于4.75的和小于等于4.75的分开，于是，原本的10个样本被分成两组：R1={1,2}，R2={3,4,5,6,7,8,9,10}，然后计算c1和c2，即两组的均值，R1有两个值，R2有8个值：

c1 = 1/2*（4.5+4.75）=4.63

c2 = 1/8*（4.91+5.34+5.8+7.05+7.9+8.23+8.7+9）=7.12

接着，我们取s=3，....，以此类推，计算出10个c1和c2值：

然后，来计算每个s取值对应的MSE:

计算出10个MSE值：

于是，我们发现对于xi这个变量而言，选择s=5的时候对应MSE（5）=3.36是最小的MSE，因此，选择s=5来划分这个节点，也就是把10个样本划分为两组：R1={1,2,3,4,5}，R2={6,7,8,9,10}，此时c1=5.06，c2=8.18，我们得到了回归树的第一层：

接下来对分好的两组重复上述步骤，最终得到完整的回归树：

这颗回归树的10个叶子节点的均值就表示对原始10个值的拟合，值得注意的是，回归树的深度决定了拟合的程度，太深就会产生过拟合风险，相比线性回归，回归树的优点在于对原始值的尺度不敏感，无需做太多转化，且对于非线性分布的样本理论上可以得到优于多元线性回归的结果，且可以通过树深度来控制拟合：

说到过拟合风险，就不得不提决策树和回归树都要面临的剪枝问题，顾名思义，剪枝就是把树上的一些多余的枝叶减掉，目的是防止树的生长误入歧途。剪枝策略分为预剪枝和后剪枝，预剪枝是在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。

后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有可能的结果。后剪枝是目前最普遍的做法。

后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类称为majority class ，（majority class 在很多英文文献中也多次出现）。

关于剪枝的问题另外再整理一篇单独研究。

树的提升

现在回到前面罗列的影响决策树的几个问题（变量多，取值范围不一，权重不好衡量等），不难发现在面对实际问题时，一棵树即便长得再好，也只是一棵树，只能给出一个结果，那如果同时培育很多棵树，对同一个样本给出不同的预测结果，是不是可以获得更准确的判断呢？，这就是集成学习的初衷，也就是把一些弱学习器（例如一棵决策树）进行组合，获得强学习器的思路。按照广度和深度，集成学习分成了bagging和boosting两种学习策略，前者通过随机采样生成很多相互独立的基学习器，对预测结果进行投票；后者通过对预测效果的不断提升生成很多相互影响的基学习器，对预测结果进行优化。

bagging的代表就是随机森林，boosting在决策树上的实现就是梯度提升树（GBDT）以及adaboost。

随机森林就不赘述了，只想提一句随机森林最突出的缺点，就是其随机性很容易导致正确结果被错误结果淹没。

直接来看梯度提升树。梯度提升树的原理是在决策树的基础上，利用误差生成另一棵决策树，不断迭代，直到损失函数收敛，最后将所有对应子节点的值相加得到最终的预测值。提升采用前向分步算法，第t步的模型由第t-1步的模型形成，算法简述如下：

举个例子，参考自一篇博客GBDT实例，该博客举出的例子较直观地展现出多棵决策树线性求和过程以及残差的意义。

  训练一个提升树模型来预测年龄：

  训练集是4个人，A，B，C，D年龄分别是14，16，24，26。样本中有购物金额、上网时长、经常到百度知道提问等特征。提升树的过程如下：

Adaboost是英文”Adaptive Boosting“（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。Adaboost相对来说我了解比较少，它主要是按照贡献程度给每个变量赋予了权重的概念，然后按照权重进行树的迭代，不断更新权重。adaboost比较特别的地方在于，它所有的树都是单层树，也就是每棵树只对应一个变量，称为stump（树桩）：

上图，adaboost有三个特点：

1. 弱学习器都是单层决策树stump

2. 各个stump的权重不一样

3.各个stump之间是迭代的关系

《统计学习方法》中adaboost算法的描述如下：

Adaboost的计算实例再次偷懒贴一篇Adaboost实例。

后面我会针对树学习器在具体项目中的应用继续补充内容。