XGBoost、LightGBM、catBoost是GBDT模型的三大工程化的实现。前面已经对XGBoost模型进行了讲解，这篇博客将对LightGBM与catBoost模型进行讲解。由于三大模型有很多需要相似的地方，大部分基础部分在XGBoost那片已经讲解过了，所以这篇博客将着重讲解模型自身创新的地方。
LightGBM模型介绍
在GBDT模型中，核心在于基本分类器(回归树)的生成，XGBoost模型也不例外。在XGBoost中，在找最佳分裂点的时候，所使用的方法是：针对每一个特征，去遍历所有训练实例，计算信息增益，从而得到最佳分裂点。但是，当实例的特征维度非常大，数据量也非常大的时候，计算效率会大幅降低，同时也非常地占用内存。而LightGBM模型正是从减小数据量以及特征维度这两方面，对XGBoost模型进行性能优化的GBDT模型。为了减小数据量，LightGBM中所使用的技术叫做：Gradient based One side sampling(GOSS)；为了减小特征数量，LgithGBM中所使用的技术叫做：Exclusive Feature Bundling(EFB)。下面，我们将从这两方面，来介绍LightGBM模型。
Gradient based One side sampling(GOSS)
GOSS，中文叫做：基于梯度的单边采样。它的目标是：减小数据量。那么怎么做呢？作者发现：训练集中具有不同梯度的实例对于计算信息增益的作用是不一样的。那么具有较小梯度的实例，说明其已经被训练的差不多了，其对于信息增益的大小影响较小；而那些具有较大梯度的实例对信息增益的影响较大。所以一个很自然地想法是：抛弃那些梯度较小的实例，只保存梯度较大的实例，这样的话，就达到了减小数据量的目标，同时还不够降低准确率。但是这样做会带来一个问题：抛弃实例会导致训练集的数据分布发生改变。为了解决这个问题，GOSS算法被提出来了。
GOSS的核心思想是：保存所有的梯度较大的实例，同时对梯度较小的实例进行一定比例的随机抽样。具体做法是：
- 首先，对训练实例按照梯度从大到小进行排序；
- 接着，选取并保存前$a\%$的梯度大的实例。即：$a\% *# samples$
- 接着，在选取$b\%$的梯度小的实例。即：$b\% *# samples$
- 合并选取的梯度大的与小的实例，作为新的训练集；
- 每一个梯度小实例乘以一个系数：$\frac {1-a}{b}$，这样做的作用在于：尽量保证数据分布不发生变化。
- 使用上述的样本训练一个弱分类器。
当$a$为0的时候，就是随机抽样算法；当$a$为1的时候，就没有抽样，使用全部训练实例。
Exclusive Feature Bundling(EFB)
EFB，中文叫做：独立特征合并。它的目标是：减小特征数量。这个算法的想法来源是：在实例的特征中，大部分的特征都是稀疏的，即特征向量大部分都是0。那么，如果我们能够将特征进行合并·，就可以减小使用的特征的数量，还能得到稠密的特征向量，易于训练。EFB算法的想法是：我们将两个完全互斥的特征进行合并，这个样才不会丢失信息；如果说两个特征之间并不是完全互斥的，我们可以使用冲突比率来对特征之间的不互斥的程度进行衡量，如果说这个值比较小，那么，我们还是可以将这两个特征进行合并，而不会影响到最后的性能。这样讲还是比较抽象，举个例子：特征a的数据为$[1, 0, 0, 0, 2, 0]$，特征b的数据为$[0, 0, 3, 0, 0, 2]$，可见他们的非零部分的位置都是没有冲突的，那么我们将其合并在一起$[1,0,3,0,2,4]$。这里b特征的数值2改成4，是因为a特征已经存在数值2．那么我们就将它改成其他数值避免数值上的冲突。那么问题来了：
- 第一个问题：我们如何确定哪些特征用来合并效果会比较好？
- 第二个问题：我们如何将确定好的特征进行合并？
第一个问题
对于第一个问题，这是一个NP-hard问题。我们可以将特征看作点，特征之间的冲突值看作边的权重，(这里的冲突值说的是特征的之间的cos值。)我们要做的是合并特征，并使得合并特征的数目最小，这其实是一个图着色问题。在EFB中，使用近似贪心算法来解决。先按照度来对每个特征做降序排序（度数越大与其他点的冲突越大），然后将特征合并到冲突数小于K的bundle或者新建另外一个bundle。算法的时间复杂度为O(#feature^2)。
第二个问题
第二个是怎么合并这些bundles。由于每一个bundle当中，features的range都是不一样，所以我们需要重新构建合并后bundle feature的range。在第一个for循环当中，我们记录每个feature与之前features累积totalRange。在第二个for循环当中，根据之前的binRanges重新计算出新的bin value：$（F[j]bin[i] + binRanges[j]）$，保证feature之间的值不会冲突。这是针对于稀疏矩阵进行优化。由于之前Greedy Bundling算法对features进行冲突检查确保bundle内特征冲突尽可能少，所以特征之间的非零元素不会有太多的冲突。比如，假设我们有两个特征，特征A的取值范围是[0,10)，而特征B的取值范围是[0,20)，我们可以给特征B增加偏移量10，使得特征B的取值范围为[10, 30)，最后合并特征A和B，形成新的特征，取值范围为[0,30)来取代特征A和特征B。如此一来，数据的shape就变成了$#samples * #bundles$，且$#bundles << #features$。EFB降低了数据特征规模提高了模型的训练速度。
树的生长方式
树的生长方式有两种：leaf-wise与level-wise。level-wise方式是：一次分裂是分裂同一层的所有的叶子结点，这样做的好处在于可以防止过拟合，但是缺点在于会产生不必要的开销，因为其实同一层的叶子结点，没必要去计算它们所有的信息增益。left-wise的方式是：从一层的叶子结点中找到信息增益最大的叶子结点，进行分裂，这样做的好处在于不需要对一层的叶子结点都进行分裂，就减小了计算量；坏处在于容易出现过拟合。在LightGBM模型中，采用了leaf-wise方式，并使用$max depth$来限制树的深度，从而来避免过拟合。
catBoost模型介绍
catBoost模型主要是为了处理类别特征问题而设计的。对于类别特征，一般的处理方式是：当它的取值个数比较小的时候，那么可以将其转换为one-hot编码；但是当其个数非常多的时候，那么这个时候就不能使用one-hot编码来。因为这样的话，会导致决策树无法学习，即分到这个叶子结点的样本数目太少。所以，catBoost就提出了几种关于处理类别特征的算法，具体的以后有时间再写吧🥱。参看链接：catBoost
参考文献
1 《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》
2 《CatBoost: gradient boosting with categorical features support》
