1 基本概念
- 集成学习的主要思路是先通过一定的规则生成多个学习器,再采用某种集成策略进行组合,最后综合判断输出最终结果。一般而言,通常所说的集成学习中的多个学习器都是同质的"弱学习器"。基于该弱学习器,通过样本集扰动、输入特征扰动、输出表示扰动、算法参数扰动等方式生成多个学习器,进行集成后获得一个精度较好的"强学习器"。
目前集成学习算法大多源于bagging、boosting、stacking三种思想。
2 bagging
- 一种提高分类模型的方法。
- (1) 从训练集\(S\)中有放回的随机选取数据集\(M\)\((∣M∣ < ∣S∣)\);
- (2) 生成一个分类模型\(C\);
- (3) 重复以上步骤\(m\)次,得到\(m\)个分类模型\(C_1,C_2,...,C_m\);
- (4)对于分类问题,每一个模型投票决定,少数服从多数原则;
- (5)对于回归问题,取平均值。
注意:这种抽样的方式会导致有的样本取不到,大约有\(\lim_{n \to \infty}(1-\frac{1}{n})^n\) = \(36.8%\)的样本取不到,这部分可用来做测试集。
- 优点: 通过减少方差来提高预测结果。
缺点: 失去了模型的简单性。
2.1 Random Forest
是一种基于树模型的bagging算法改进的模型。假定数据集中有\(M\)个特征和 \(N\)个观测值。每一个树有放回的随机抽出\(N\)个观测值\(m\)(\(m=M\)或者\(m=logM\))个特征。把每一个单一决策树的结果综合起来。
- 优点:
- (1) 减少了模型方差,提高了预测准确性。
- (2) 不需要给树做剪枝。
- (3) 在大规模数据集,尤其是特征较多的情况下,依然可以保持高效率。
- (4) 不用做特征选择,并且可以给出特征变量重要性的排序估计。
- 缺点:
- (1) 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合
- (2) 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的。
3 boosting
3.3 Xgboost
- XGBoost是陈天奇等人开发的一个开源机器学习项目,高效地实现了GBDT算法并进行了算法和工程上的许多改进。
- 目标函数:
\[L^{(t)} = \sum_{i=1}^{n}l(y_i, \hat{y}_i^{(t)}) + \Omega(f_t) \]
- 优点:
- (1)计算效率高,使用了二阶导。
- (2)有正则化,减少过拟合。
- (3)列特征抽样减少过拟合,同时有利于并行计算。
- 缺点:
- (1)每次迭代时都要遍历整个数据集。
- (2)内存占用大。
3.4 GBDT与XGboost联系与区别
- (1) GBDT是机器学习算法,XGBoost是该算法的工程实现。
- (2) 在使用CART作为基分类器时,XGBoost显式地加入了正则项来控制模型的复杂度,有利于防止过拟合,从而提高模型的泛化能力。
- (3) GBDT在模型训练时只使用了代价函数的一阶导数信息,XGBoost对代价函数进行二阶泰勒展开,可以同时使用一阶和二阶导数。
- (4) 传统的GBDT采用CART作为基分类器,XGBoost支持多种类型的基分类器,比如线性分类器。
- (5) 传统的GBDT在每轮迭代时使用全部的数据,XGBoost则采用了与随机森林相似的策略,支持对数据进行采样。
- (6) 传统的GBDT没有设计对缺失值进行处理,XGBoost能够自动学习出缺失值的处理策略。
3.5 LightGBM
- LightGBM也是一种基于决策树的梯度提升算法,相比XGboost有做了许多改进。
在树分裂计算分裂特征的增益时,xgboost 采用了预排序的方法来处理节点分裂,这样计算的分裂点比较精确。但是,也造成了很大的时间开销。为了解决这个问题,Lightgbm 选择了基于 histogram 的决策树算法。相比于pre-sorted算法,histogram在内存消耗和计算代价上都有不少优势。
- Histogram算法简单来说,就是先对特征值进行装箱处理,形成一个一个的bins。在Lightgbm中默认的#bins为256(1个字节的能表示的长度,可以设置)。具体如下:
- (1) 把连续的浮点特征值离散化成N个整数,构造一个宽度为N的直方图;对于分类特征,则是每一种取值放入一个bin,且当取值的个数大于max_bin数时,会忽略那些很少出现的category值。
- (2) 遍历数据时,根据离散化后的值作为索引在直方图中累积统计量。
- (3) 一次遍历后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。
- Level-wise 和 Leaf-wise
- 相对于xgboost的level—wise的生长策略,lightgbm使用了leaf-wise树生长策略。由于level-wise在分裂时,部分增益小的树也得到了增长,虽然容易控制误差,但是分裂有时是不合理的,而lightgbm使用level-wise,只在增益大的树上分裂生长,甚至对Feature f如果分裂无收益,那么后续也将不会对f计算。体现在参数上,xgboost使用max_depth,而lightgbm使用num_leaves控制过拟合。
- Level-wise过一次数据可以同时分裂同一层的叶子,容易进行多线程优化,也好控制模型复杂度,不容易过拟合。但实际上Level-wise是一种低效的算法,因为它不加区分的对待同一层的叶子,带来了很多没必要的开销,因为实际上很多叶子的分裂增益较低,没必要进行搜索和分裂。

- Leaf-wise则是一种更为高效的策略,每次从当前所有叶子中,找到分裂增益最大的一个叶子,然后分裂,如此循环。因此同Level-wise相比,在分裂次数相同的情况下,Leaf-wise可以降低更多的误差,得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树,产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合。

3.6 Xgboost与LightGBM对比
3.6.1 切分算法(切分点的选取)
- 占用的内存更低,只保存特征离散化后的值,而这个值一般用8位整型存储就足够了,内存消耗可以降低为原来的1/8。
- 降低了计算的代价:预排序算法每遍历一个特征值就需要计算一次分裂的增益,而直方图算法只需要计算k次(k可以认为是常数),时间复杂度从O(#data#feature)优化到O(k#features)。(相当于LightGBM牺牲了一部分切分的精确性来提高切分的效率,实际应用中效果还不错)
- 空间消耗大,需要保存数据的特征值以及特征排序的结果(比如排序后的索引,为了后续快速计算分割点),需要消耗两倍于训练数据的内存
- 时间上也有较大开销,遍历每个分割点时都需要进行分裂增益的计算,消耗代价大
- 对cache优化不友好,在预排序后,特征对梯度的访问是一种随机访问,并且不同的特征访问的顺序不一样,无法对cache进行优化。同时,在每一层长树的时候,需要随机访问一个行索引到叶子索引的数组,并且不同特征访问的顺序也不一样,也会造成较大的cache miss。
- XGBoost使用的是pre-sorted算法(对所有特征都按照特征的数值进行预排序,基本思想是对所有特征都按照特征的数值进行预排序;然后在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点最后,找到一个特征的分割点后,将数据分裂成左右子节点。优点是能够更精确的找到数据分隔点;但这种做法有以下缺点
- LightGBM使用的是histogram算法,基本思想是先把连续的浮点特征值离散化成k个整数,同时构造一个宽度为k的直方图。在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点;优点在于
3.6.2 决策树生长策略
- XGBoost采用的是带深度限制的level-wise生长策略,Level-wise过一次数据可以能够同时分裂同一层的叶子,容易进行多线程优化,不容易过拟合;但不加区分的对待同一层的叶子,带来了很多没必要的开销(因为实际上很多叶子的分裂增益较低,没必要进行搜索和分裂)
- LightGBM采用leaf-wise生长策略,每次从当前所有叶子中找到分裂增益最大(一般也是数据量最大)的一个叶子,然后分裂,如此循环;但会生长出比较深的决策树,产生过拟合(因此 LightGBM 在leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合)。
- Histogram做差加速。一个容易观察到的现象:一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶。利用这个方法,LightGBM可以在构造一个叶子的直方图后,可以用非常微小的代价得到它兄弟叶子的直方图,在速度上可以提升一倍。
- 直接支持类别特征:LightGBM优化了对类别特征的支持,可以直接输入类别特征,不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。
3.6.3 分布式训练方法上(并行优化)
- 在特征并行算法中,通过在本地保存全部数据避免对数据切分结果的通信;
- 在数据并行中使用分散规约(Reducescatter)把直方图合并的任务分摊到不同的机器,降低通信和计算,并利用直方图做差,进一步减少了一半的通信量。基于投票的数据并行(ParallelVoting)则进一步优化数据并行中的通信代价,使通信代价变成常数级别。
- 特征并行的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点,然后在机器间同步最优的分割点。
- 数据并行则是让不同的机器先在本地构造直方图,然后进行全局的合并,最后在合并的直方图上面寻找最优分割点。
- LightGBM针对这两种并行方法都做了优化,
- Cache命中率优化
- 基于直方图的稀疏特征优化
- DART(Dropout + GBDT)
- GOSS(Gradient-based One-Side Sampling):一种新的Bagging(row subsample)方法,前若干轮(1.0f /gbdtconfig->learning_rate)不Bagging;之后Bagging时, 采样一定比例g(梯度)大的样本。
4 stacking
集成学习总结
原文:https://www.cnblogs.com/zingp/p/11076362.html