LightGBM 下的 boosting 简介
每天真的是想到或看到什么就记录什么，文章没写几篇，文集倒是已经建立了好几个了。。。
废话不多说，“大自然的搬运工” 开始干活了。
LightGBM它和xgboost一样是对GBDT的高效实现，很多方面会比xgboost表现的更为优秀。GBDT采用负梯度作为划分的指标，XGBoost则利用到二阶导数。他们共同的不足是，计算信息增益需要扫描所有样本，从而找到最优划分点。在面对大量数据或者特征维度很高时，他们的效率和扩展性很难使人满意。
GBDT是基于决策树的集成算法，采用前向分布算法，在每次迭代中，都是通过负梯度拟合残差，从而学习一颗决策树，最耗时的步骤就是找最优划分点。一种流行的方法就是预排序，核心是在已经排好序的特征值上枚举所有可能的特征点。另一种改进则是直方图算法，LightGBM则是后者。
LightGBM的优化点
1、采用直方图算法
2、树的生长策略优化
3、相对于xgboost和GBDT,LightGBM提出了两个新方法，使得LightGBM的效率要显著要高于GBDT和xgboost。这两种新方法是：Gradient-based One-Side Sampling和Exclusive Feature Bundling 。
直方图算法（Histogram）
直方图算法是先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
优点如下：
- 直方图只需对直方图统计量计算信息增益，相比较于预排序算法每次都遍历所有的值，信息增益的计算量要小很多
- 通过利用叶节点的父节点和相邻节点的直方图的相减来获得该叶节点的直方图，从而减少构建直方图次数，提升效率
- 存储直方图统计量所使用的内存远小于预排序算法
树的生长策略优化
- LightGBM 通过 leaf-wise (best-first)策略来生长树。它将选取具有最大信息增益最大的叶节点来生长。 当生长相同的叶子时，leaf-wise 算法可以比 level-wise 算法减少更多的损失。
- 当数据较小的时候，leaf-wise 可能会造成过拟合。 所以，LightGBM 可以利用额外的参数 max_depth 来限制树的深度并避免过拟合（树的生长仍然通过 leaf-wise 策略）。
GBDT(Gradient Boosting Decision Tree，别名: MART, GBRT)
默认的boosting参数。
RF（Random Forest）
就是随机森林。
DART(Dropouts meet Multiple Additive Regression Trees)
DART利用了深度神经网络中dropout设置的技巧，随机丢弃生成的决策树，然后再从剩下的决策树集中迭代优化提升树。
GOSS（Gradient-based One-Side Sampling，从减少样本的角度）
在AdaBoost算法中，我们在每次迭代时更加注重上一次错分的样本点，也就是上一次错分的样本点的权重增大，而在GBDT中并没有内在的权重来实现这样的过程，所以在AdaBoost中提出的采样模型不能应用在GBDT中。但是，每个样本的梯度对采样提供了非常有用的信息。也就是说，如果一个样本点的梯度小，那么该样本点的训练误差就小并且已经经过了很好的训练。我们可以丢弃这些数据。当然，改变数据分布会造成模型的精度损失。GOSS则通过保存大梯度样本，随机选取部分小梯度样本，并为其弥补上一个常数权重。这样，GOSS更关注训练不足的样本，同时也不会改变原始数据太多。
EFB（Exclusive Feature Bundling，从减少特征角度）
高维数据一般是稀疏的，可以设计一种损失最小的特征减少方法。并且，在稀疏特征空间中，许多特征都是互斥的，也就是它们几乎不同时取非0值。因此，我们可以安全的把这些互斥特征绑到一起形成一个特征，然后基于这个合成的特征构建直方图，这样又可以加速了。
