Kaggle实战系列之"San Francisco Crime
XGBoost、Light GBM、CatBoost
算法和技术
XGBoost
XGBoost全称为eXtreme Gradient Boosting，是陈天奇大牛开发的一个大规模、分布式的通用Gradient Boosting（GBDT）库。它是GBDT的一种高效实现，GBDT是一个基于迭代累加的决策树算法，它通过构造一组弱的学习器（树），并把多颗决策树的结果累加起来作为最终的预测输出。XGBoost在Gradient Boosting框架下实现了GBDT和一些广义的线性机器学习算法。XGBoost是boosting算法的一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器。因为XGBoost是一种提升树模型，所以它是将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型。XGBoost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。
* 和GBDT不同，xgboost给损失函数增加了正则化项（L1或L2正则化项，视学习目标不同而取不同正则化参数。
* 有些损失函数是难以计算导数的，鉴于这种情况，xgboost使用损失函数的二阶泰勒展开作为损失函数的拟合
* GBDT的节点分裂方式是遍历所有特征的所有可能划分，再选取最优者分裂。xgboost使用分位点及分位数法，近似地计算，有效降低计算量
LightGBM
LigthGBM是boosting集合模型中的新进成员，由微软提供，它和XGBoost一样是对GBDT的高效实现，原理上它和GBDT及XGBoost类似，都采用损失函数的负梯度作为当前决策树的残差近似值，去拟合新的决策树。LightGBM在很多方面会比XGBoost表现的更为优秀。LigthGBM的优势在于：更快的训练效率、低内存使用、更高的准确率、支持并行化学习、支持直接使用category特征、可处理大规模数据。
根据机器学习算法之LightGBM提供的的实验数据可以看出， LightGBM比XGBoost快将近10倍，内存占用率大约为XGBoost的1/6，并且准确率也有提升。概括来说，lightGBM主要有以下特点：
* 基于Histogram的决策树算法
* 带深度限制的Leaf-wise的叶子生长策略
* 直方图做差加速
* 直接支持类别特征(Categorical Feature)
* Cache命中率优化
* 基于直方图的稀疏特征优化
* 多线程优化
前2个特点使我们尤为关注的。
XGBoost使用的是pre-sorted算法：首先，对所有特征按数值进行预排序。其次，在每次的样本分割时，用O(# data)的代价找到每个特征的最优分割点。最后，找到最后的特征以及分割点，将数据分裂成左右两个子节点。这种pre-sorting算法能够准确找到分裂点，但是在空间和时间上有很大的开销。原因在于该算法需要对特征进行预排序并且需要保存排序后的索引值（为了后续快速的计算分裂点），因此内存需要训练数据的两倍；且在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
LightGBM使用的是histogram算法，用的内存更低，数据分隔的复杂度更低。Histogram算法（直方图算法）的基本思想：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
Leaf-wise vs Level-wise
值得注意的是，直方图算法使用bin替代原始数据相当于增加了正则化；使用bin意味着很多数据的细节特征被放弃了，相似的数据可能被划分到相同的桶中，这样的数据之间的差异就消失了；bin数量选择决定了正则化的程度，bin越少惩罚越严重，欠拟合风险越高。
在Histogram算法之上，LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise)的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise)算法。XGBoost采用的是按层生长level（depth）-wise生长策略，Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
LightGBM采用leaf-wise生长策略，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
XGBoost vs Light GBM
参考资料
一步一步理解GB、GBDT、xgboost
Python机器学习笔记：XgBoost算法
xgboost的数学模型、分位点及分位数法
从结构到性能，一文概述XGBoost、Light GBM和CatBoost的同与不同
谁是数据竞赛王者？CatBoost vs. Light GBM vs. XGBoost
