机器学习实战_集成学习（一）
集成学习
集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务，比单一学习器获得显著优越的泛化性能。想要获得好的集成，个体学习器应"好而不同"，要保证准确性和多样性。要产生好而不同的个体学习器，恰是集成学习研究的核心
目前集成学习可分为两大类，即个体学习器之间有依赖关系，必须串行生成的序列化方法；以及个体学习器不存在强依赖关系，可同时生成的并行化方法。前者的代表是Boosting，最著名的是代表有Adaboost, GBDT和XGBOOST;后者的代表是Bagging和随机森林。对于学习器的结合策略有三大类：投票法（分类），平均法（连续数值），学习法（Stacking）
Adaboost
line 1初始化样本权重，并在在line 7样本的分类正确与否更新样本权重（考虑line6学习器的权重），正确则降低权重，会偏重考虑分类错误的样本；line 4计算个体学习器错误率ε=分类正确样本数/总样本数；line 6利用错误率ε计算个体学习器的权重（和line1的样本权重不一样），通过指数损失函数调整权重，分类正确的降低权重，分类错误的增加权重。
line9输出举例:0.4236和0.6496为个体学习器G1(x)和G2(x)的权重，2.5与8.5为这两个学习器的分类阈值
注意，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（例如上面 AdaBoost算法的第 5 步，检查当前基分类器是否比随机猜测好），一旦条件不满足，则当前基学习器即被抛弃，学习过程停止。在此情形下，初始设置的学习轮数 T也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。
另外，权值很低的数据从侧面说明，它们在前面的学习器经常被分类正确，也就是说它们被分类正确的票数就比较多。
总之，AdaBoost的主要思想就是在不改变训练数据的情况下，通过在迭代训练弱学习器中，不断提升被错分类样本的权重（也就是使被错分的样本在下一轮训练时得到更多的重视），不断减少正确分类样本的权重。最后通过加权线性组合M个弱分类器得到最终的分类器，正确率越高的弱分类器的投票权数越高，正确率低的弱分类器自然投票权数就低。
从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此 Boosting能基于泛化性能相当弱的学习器构建出很强的集成。
GBDT
CART:
GBDT里面的树都是回归树（CART），不是分类树。回归树衡量最好的标准不再是最大熵，而是最小化均方差。而且在每个节点（不一定是叶子节点）都会得一个预测值，这个预测值可为所有样本的平均值。
分类与回归树CART:CART回归树
回归树算法流程：j为选定的某个特征属性，s为在这个特征上的切分数值（需要遍历所有特征和切分点来选到最小化均方差），R1R2为切分的样本，C1C2为切分区域样本中的特征均值。
Boosting Decision Tree:提升树
BDT提升树的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，我们训练的时候，第一棵树的拟合过后预测年龄是12岁，我们与真实数据比对差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去拟合学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。即当M=6棵树时，f_6(x)=f_5(x)+第五棵树学的残差树T6=T1+T2+T3+T4+T5+T6
加法模型与前项分布算法：加法模型与前项分布算法
提升方法采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（Boosting tree）。对分类问题构建的决策树是二叉分类树，对回归问题构建决策树是二叉回归树。提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，残差的意义如公式：残差 = 真实值 - 预测值 。提升树即是整个迭代过程生成的回归树的累加。提升树模型可以表示为决策树的加法模型：
$$f_M(x) = \sum_{m=1}^M T(x;\Theta_m)$$
其中$T(X;\Theta_m)$ 表示决策树；$\Theta_m$ 为决策树的参数； M为树的个数
提升树算法流程：对回归问题的提升树算法来说，给定当前模型 $f_{m−1}(x)$ 只需要简单地拟合当前模型的残差。现将回归问题的提升树算法叙述如下：
解析：m=1第一颗树时，计算最佳切分特征j和最佳切分点s得到回归树T1(x)，其形式类似adaboost的最简二叉树，其叶子节点的数值为c1,c2. 然后，根据c1c2和划分区域计算残差r_mi,利用残差值和之前计算方法一样得到T2(x)，重复这个过程，直到最后结果得到一个很小的平方误差值。
Gradient Boosting Decision Tree：梯度提升决策树
提升树利用加法模型与向前分布算法实现学习的优化过程，即是通过迭代得到一系列的弱分类器，进而通过不同的组合策略得到相应的强学习器。在GBDT的迭代中，假设前一轮得到的抢学习器为$f_{t−1}(x)$ ，对应的损失函数则为$L(y,f_{t−1}(x))$ 。因此新一轮迭代的目的就是找到一个弱分类器$h_t(x)$ ，使得损失函$L(y,f_{t−1}(x)+h_t(x))$ 达到最小。因此问题的关键就在于对损失函数的度量，这也正是难点所在。当损失函数是平方损失和指数损失时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化没那么容易，如绝对值损失函数和Huber损失函数。常见的损失函数及其梯度如下表所示：
那我们怎么样才能找到一种通用的拟合方法呢？针对这一问题，Freidman提出了梯度提升算法：利用最速下降的近似方法，即利用损失函数的负梯度在当前模型的值
$$r_{mi}=-\left[\frac{\partial L\left(y,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]_{f\left(x\right)=f_{m-1}\;\,\left(x\right)}$$
作为回归问题中提升树算法的残差的近似值（与其说负梯度作为残差的近似值，不如说残差是负梯度的一种特例，拟合一个回归树），这就是梯度提升决策树.
算法过程如下：
解析：
1）初始化弱分类器，估计使损失函数极小化的一个常数值，此时树仅有一个根结点,即ganma是一个常数值c
$$f_0\left(x\right)=arg\min_c\sum_{i=1}^N{L\left(y_i,c\right)}$$
2）对迭代轮数1,2,⋅⋅⋅,M
- a）对i=1,2,⋅⋅⋅,N，计算损失函数的负梯度值在当前模型的值，将它作为残差的估计,对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。即
$$r_{mi}=-\left[\frac{\partial L\left(y,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]_{f\left(x\right)=f_{m-1}\;\,\left(x\right)}$$
- b）对$r_{mi}$ 拟合一个回归树，得到第m棵树的叶结点区域$R_{mj}，j=1,2,⋅⋅⋅,J$
- c）对j=1,2,⋅⋅⋅,J计算, 即利用线性搜索估计叶结点区域的值，使损失函数极小化（计算最优梯度下降步长）
$$c_{mj}=arg\min_c\sum_{x_i\in R_{mj}}{L\left(y_i,f_{m-1}\left(x_i\right)+c\right)}$$
- d）更新回归树
$$f_m\left(x\right)=f_{m-1}\left(x\right)+\sum_{j=1}^J{c_{mj}I\left(x\in R_{mj}\right)}$$
3）得到输出的最终模型
$$\hat{f}\left(x\right)=f_M\left(x\right)=\sum_{m=1}^M{\sum_{j=1}^J{c_{mj}I\left(x\in R_{mj}\right)}}$$
XGBoost
数据建模中，经常采用Boosting方法通过将成百上千个分类准确率较低的树模型组合起来，成为一个准确率很高的预测模型。这个模型会不断地迭代，每次迭代就生成一颗新的树。但在数据集较复杂的时候，可能需要几千次迭代运算，这将造成巨大的计算瓶颈。
针对这个问题。华盛顿大学的陈天奇博士开发的XGBoost（eXtreme Gradient Boosting）基于C++通过多线程实现了回归树的并行构建，并在原有Gradient Boosting算法基础上加以改进，从而极大地提升了模型训练速度和预测精度.
寻优算法之梯度下降与牛顿法
在机器学习任务中，需要最小化损失函数L(θ)，其中θ是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值$θ^0$ ,不断迭代，更新θ的值，进行损失函数的极小化。
- 迭代公式：$θ^t = θ_{t-1}+△θ$
梯度下降：将$L(θ^t)$ 在$θ^{t-1}$ 处进行一阶泰勒展开:
$$L(θ^t)=L(θ^{t-1}+△θ)\approx L(θ^{t-1})+L'(θ^{t-1})△θ$$
要使得$L(θ^t)<L(θ^{t-1})$ ,可取$△θ=-\alpha L'(θ^{t-1})$ ，则$θ^t = θ^{t-1}-\alpha L'(θ^{t-1})$
这里$\alpha$ 是步长，可通过line search确定，但一般直接赋一个小的数
牛顿法：将$L(θ^t)$ 在$θ^{t-1}$ 处进行二阶泰勒展开:
$$L(θ^t)\approx L(θ^{t-1})+L'(θ^{t-1})△θ+L''(θ^{t-1})\frac{(△θ)^2}{2}$$
可将一阶和二阶导数分别记为g 和 h,则:
$$L(θ^t)\approx L(θ^{t-1})+g△θ+h\frac{(△θ)^2}{2}$$
要使得$L(θ^t)$极小，即让$g△θ+h\frac{(△θ)^2}{2}$ 极小，可令其对△θ求偏导值为0，求得$△θ=-\frac{g}{h}$ ,故$θ^t = θ^{t-1}+△θ=θ^{t-1}-\frac{g}{h}$ ,将其推广到向量形式，有$θ^t = θ^{t-1}-H^{-1}g$
GBDT 在函数空间中利用梯度下降法进行优化
XGBoost 在函数空间中用牛顿法进行优化
相比原始的GBDT，XGBoost的目标函数多了正则项，使得学习出来的模型更加不容易过拟合。有哪些指标可以衡量树的复杂度？树的深度，内部节点个数，叶子节点个数(T)，叶节点分数(w)...
XGBoost采用的是：T代表叶子数量，w代表叶子预测权值
而XGBoost第t次迭代后，模型的预测等于前t-1次的模型预测加上第t棵树的预测
此时目标损失函数可写作：
公式中$y_i,\widehat y_i$ 都是已知的，模型要学习的只有第t棵树$f_t$ .另外对于损失函数不是平方误差的情况，我们可以采用如下的泰勒展开近似来定义一个近似的目标函数，方便我们进行下一步的计算。
这时候，所有东西都准备好了，最后我们怎么定义$f_t$呢？它可以代表一颗具有预测结果的树，即叶子节点有预测权重。我们定义w为树叶的权重序列，q为树的结构，那么q(x)代表样本x落在树叶的位置。
这样，我们就可以对上面的目标优化函数进行泰勒二次展开进行一大堆推导（不展开了，xgboost官网有完整的推导），最后的推导结果（前提是确定了树的结构，即q(x)已知。）：
当回归树的结构确定时，我们前面已经推导出其最优的叶节点分数以及对应的最小损失值，问题是怎么确定树的结构？
- 暴力枚举所有可能的树结构，选择损失值最小的 - NP难问题
- 贪心法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的
分裂前后的增益怎么计算？
- ID3算法采用信息增益
- C4.5算法采用信息增益比
- CART采用Gini系数
- XGBoost采用上诉优化函数的打分
树节点分裂方法（Split Finding）
- 精确算法：遍历所有特征的所有可能的分割点，计算gain值，选取值最大的（feature，value）去分割
- 近似算法：对于每个特征，只考察分位点，减少计算复杂度
Global：学习每棵树前，提出候选切分点
Local：每次分裂前，重新提出候选切分点
性能比较：
如何使用：
参数：
Q&A
基分类器的选择：传统GBDT以CART作为基分类器，XGBoost还支持线性分类器，这个时候XGBoost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
二阶泰勒展开：传统GBDT在优化时只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，XGBoost工具支持自定义损失函数，只要函数可一阶和二阶求导。
方差-方差权衡：XGBoost在目标函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数T、每个叶子节点上输出分数的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性。
Shrinkage（缩减）：相当于学习速率（xgboost中的ϵ）。XGBoost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
列抽样（column subsampling）：XGBoost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是XGBoost异于传统GBDT的一个特性。
缺失值处理：XGBoost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。即对于特征的值有缺失的样本，XGBoost可以自动学习出它的分裂方向。
XGBoost工具支持并行：Boosting不是一种串行的结构吗?怎么并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的损失函数里包含了前面t−1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block(块)结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
线程缓冲区存储：按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer（缓冲区），主要是结合多线程、数据压缩、分片的方法，然后再计算，提高算法的效率。
可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
另外一种高效的扩展：更高效的工具包Light GBM
Bagging与随机森林
如果采样出的每个子集都完全不同，则每个基学习器只用到一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为了解决这个问题，我们可考虑使用相互有交叠的采样子集。
Bagging
随机取出一个样本放入采样集中，再把该样本放回初始数据集。这样的自助采样过程还给 Bagging带来了另一个优点：由于每个基学习器只使用了初始训练集中约 63.2%的样本，剩下约 36.8%的样本可用作验证集来对泛化性能进行包外估计(out-of-bag estimate)。Bagging通常对分类任务使用简单的投票法，对回归任务使用简单平均法。
Bagging的算法描述如下所诉($D_{bs}$是自助采样产生的样本分布,输出采用投票法)：
随机森林
随机森林(Random Forest)是Bagging的一个扩展变体。随机森林在以决策树为基学习器构建 Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性；而在随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度：若令 k=d，则基决策树的构建与传统决策树相同；若令k=1,则是随机选择一个属性用于划分；一般情况下，推荐值 k=log2d.随机森林简单、容易实现、计算开销小.
随机森林的训练效率常优于 Bagging，因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”决策树则只需考察一个属性子集。
结合策略
假定集成包含 T 个基学习器h1,h2,...ht,其中hi在示例x上的输出为hi(x)下面介绍几种对hi进行结合的常见策略。
- 投票法 1）硬投票 2）相对多数投票 3）加权投票
- 平均法 1）简单平均法 2）加权平均法（较好）
- 学习法 1）Stacking
Stacking
当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。Stacking是学习法的典型代表。这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习(metalearner)。
Stacking先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当作样例标记。Stacking的算法描述如下，这里假定初级学习器使用不同的学习算法产生，即初级集成是异质的（初级学习器也可是同质的）。
多样性度量：
集合学习的个体学习器要求“好而不同”，典型做法是考虑个体学习器的两两相似/不相似性
- 不合度量(disagreement measure)
- 相关系数(correlation coefficient)
- Q-统计量(Q-statistic)
- k-统计量(k-statistic)
多样性增强：
- 样本数据扰动
- 属性扰动（随机子空间算法）
数据样本扰动通常基于采样法，此类做法简单高效，使用最广。数据样本扰动对决策树，神经网络等这样的“不稳定基学习器”很有效，然而，有一些基学习器对样本数据扰动不敏感，例如线性学习器，支持向量机，朴素贝叶斯，k近邻学习。