集成学习
1.集成学习简介
1）通过构建并结合多个学习器来完成学习任务： 先产生一组“个体学习器”(individual learner),再用某种策略将它们结合起来。其中每个IL由一个现有的学习算法从训练数据中产生，如：C4.5决策树算法、BP神经网络等。
2）性能：集成学习器的能力和个体学习器有很大关系，个体学习器本身在具有一定“准确性”的同时，还要有“多样性”，学习器间要具有差异。 产生并结合“好而不同”的个体学习器恰恰是集成学习的核心
3）基学习器
第一种就是所有的个体学习器都是一个种类的，或者说是同质的。比如都是决策树个体学习器，或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的，或者说是异质的。
本文所讲得Boosting和Bagging方法的基学习器都是同质的。
其中：
Boosting方法的个体学习器间存在强依赖关系、必须串行生成的序列化方法。集成方式一般为加权和，分类器权重并不相等，使用所有样本。
Bagging方法的个体学习器间不存在强依赖关系、可同时生成的并行化方法，集成方式为投票，分类器权值是一样的，随机抽取部份样本。如Bagging、“随机森林(Random Forest)”。
2.Boosting和Bagging学习策略
    a.Boosting
这是一族可将弱学习器提升为强学习器的算法
工作机制：先从初始训练集中训练出来一个基学习器，然后根据表现，对训练样本进行调整，是基学习器之前做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器，如此反复，直到基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。
目前有很多种类，如AdaBoost、Generalized Boosted Models、XGBoost、lightgbm等。
b.Bagging
1)从样本集D中用Bootstrap采样选出n个样本(有放回)，执行m次，选出m个样本子集{D1,D2,...,Dm}
2)在所有属性上，分别对应这m个样本子集建立m个学习器{h1(x),h2(x),...,hm(x)}
3)将这m个学习器放在各自的训练数据上进行学习
4)通过投票法或平均法对这m个学习器进行结合20.
3.GBDT(梯度提升决策树)
a特征
该算法由多棵决策树组成，所有树的结论累加起来做最终答案。GBDT中的树是回归树（不是分类树），GBDT用来做回归预测，调整后也可以用于分类。
b优势
GBDT的思想使其具有天然优势可以发现多种有区分性的特征以及特征组合。业界中，Facebook使用其来自动发现有效的特征、特征组合，来作为LR模型中的特征，以提高 CTR预估（Click-Through Rate Prediction）的准确性。
c分类树和回归树
分类树使用信息增益或增益比率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。回归树使用最小均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。
均方差：
其中，y为标签，c为预测结果。
基尼指数：,基尼指数越小，效果越好（当前分类样本的不确定性越小）。
d提升树算法
提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，残差的意义如公式：残差 = 真实值 - 预测值 。提升树即是整个迭代过程生成的回归树的累加。
举例：
训练集是4个人，A，B，C，D年龄分别是14，16，24，26。样本中有购物金额、上网时长、经常到百度知道提问等特征。提升树的过程如下：
图（1）
算法流程：
其中，M表示有M个特征。
e.GBDT(Gradient Boosting Decision Tree)梯度提升决策树
利用损失函数的负梯度在当前模型的值，作为回归问题中提升树算法的残差的近似值，拟合一个回归树。让损失函数持续下降，就能使得模型不断改性提升性能。
其中，m为第m棵树。N表示样本个数。j表示决策特征（例如图（1）中的第一棵树将购物金额是否大于1k为分割特征）。
算法1步获得使得损失函数最小的常数估计值，是一个只有根节点的树。在2.1步计算损失函数的负梯度在当前模型的值，将它作为残差估计。在2.2步估计回归树的叶结点区域，来拟合残差的近似值。在2.3步利用线性搜索估计回归树叶结点区域的值，使损失函数最小化。2.4更新回归树。第3步获得输出的最终模型。
Eg:为什么损失函数是绝对值损失函数或huber函数，优化就变难了呢？
    当损失函数是MSE时，直接求出最优解需要满足X是列满秩的（X表示训练特征矩阵），而且求矩阵的逆比较慢，因此最小二乘法求解存在局限性，可以采用梯度下降法近似求解。
 “残差 = 真实值 - 预测值” 只是负梯度在平方损失函数上的特例。在别的损失函数上，残差就不是这么计算了。
4.Adaboost
AdaBoost Algorithm： 
1、初始化样本权值分布 
2、基于分布Dt从数据集D中训练处分类器ht 
3、估计ht的误差 err.
4、确定分类器ht的权重 
5、更新样本分布，其中Zt是规范化因子，以确保Dt+1是一个分布
具体过程见《统计学习方法》P138
AdaBoost应用：
1）用于二分类或多分类的应用场景
2）用于做分类任务的baseline：无脑化，简单，不会overfitting，不用调分类器
3）用于特征选择（feature selection)
4）Boosting用于对badcase的修正：只需要增加新的分类器，不需要变动原有分类器
正则化是最小化策略的实现5）邮件过滤、文本分类、人脸识别
Adaoost特性：
1） 训练的错误率上界，随着迭代次数的增加，会逐渐下降；
2） adaboost算法即使训练次数很多，也不会出现过拟合的问题。
3）每次迭代改变的是样本的分布，而不是重复采样（re weight)
4）样本分布的改变取决于样本是否被正确分类：总是分类正确的样本权值低，总是分类错误的样本权值高（通常是边界附近的样本）
5）最终的结果是弱分类器的加权组合：权值表示该弱分类器的性能
5.Xgboost
与GBDT最主要的差异在于损失函数定义的不同：
1） 除了要计算L(y,f(x))外，Xgboost在后面添加了正则项和一个常数项。
2） GBDT的梯度下降只用了损失函数的一阶导数，在这里利用泰勒展开式添加了二阶导数的信息。
tip:下式中，y(t-1)+f(f)。根据模型的生成方式：t时刻的树模型是之前树模型的和。所以y^(t)等于y^(t-1)+f(f).
残差实际就是下一阶段的f(x)
    上式等价于
正则项Ω(f)定义为：
其中，T为叶子结点的个数，w为叶子权重。
树中结点分割点的选择：采用贪心的思想。遍历数据中所有的分割点，选择分割前后增益最
大点：。
衡量方法：
统一后的损失是指：j（1-T）表示的是每一个叶节点，里面可能有多个样本，则将样本按叶节点分块，计算。每棵树所有叶子结点。
XGB是预剪枝。就像上面所说的选择损失函数最小的进行分裂，此时就相当于对所有节点进行分裂，然后根据上面的述的，如果增益为负数就不分裂。
6.LightGBM（Light Gradient Boosted Tree）
1）LightGBM相较XGBOOST的优化：
基于直方图的决策树算法
带深度限制的Leaf-wise的叶子生长策略
直方图做差加速
直接支持类别特征(Categorical Feature)
Cache命中率优化
多线程优化
2）XGBoost工作特点及缺点
首先，对所有特征都按照特征的数值进行预排序。
其次，在遍历分割点的时候用O(#data)的代价到一个特征上的最好分割点。
最后，到一个特征的分割点后，将数据分裂成左右子节点。
这样的预排序算法的优点是能精确地到分割点。
3）基于Histogram的决策树算法
直方图算法的基本思想：先把连续的特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散值作为索引在直方图中累积统计量，然后根据直方图的离散值，遍历寻最优的分割点。
优点：
    空间消耗小：直方图算法不仅不需存储预排序的结果，而且可以只保存特征离散化后的值，
而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。
计算代价小：计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data*#feature)优化到O(k*#features)
做差加速特性（直方图-直方图=直方图）：
一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的
直方图，在速度上可以提升一倍。
效果分析：
Histogram算法并不是完美的。由于特征被离散化后，到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。
4）带深度限制的Leaf-wise的叶子生长策略（逐级树增长）
Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
Leaf-wise则是一种更为高效的策略：每次从当前所有叶子中，到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。
Leaf-wise的缺点：可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。