LightGBM算法详解（教你⼀⽂掌握LightGBM所有知识点）
LightGBM
（Light Gradient Boosting Machine）是⼀款基于决策树算法的分布式梯度提升框架。为了满⾜⼯业界缩短模型计算时间的需
求，LightGBM的设计思路主要是两点：
减⼩数据对内存的使⽤，保证单个机器在不牺牲速度的情况下，尽可能地⽤上更多的数据；
减⼩通信的代价，提升多机并⾏时的效率，实现在计算上的线性加速。
由此可见，LightGBM的设计初衷就是提供⼀个快速⾼效、低内存占⽤、⾼准确度、⽀持并⾏和⼤规模数据处理的数据科学⼯具。LightGBM是微软旗下的Distributed Machine Learning Toolkit （DMKT）的⼀个项⽬，由2014年⾸届阿⾥巴巴⼤数据竞赛获胜者之⼀柯国霖主持开发。虽然其开源时间才仅仅2个⽉，但是其快速⾼效的特点已经在数据科学竞赛中崭露头⾓。Allstate Claims Severity竞赛中的冠军解决⽅案⾥就使⽤了LightGBM，并对其⼤嘉赞赏。
特性
优化速度与内存使⽤。
稀疏优化。splitwise
优化准确率。使⽤leaf-wise⽣长⽅式，可以处理分类变量。
优化⽹络通讯。
⽀持三种模式并⾏。
（1）特征并⾏：
a. Workers find local best split point {feature, threshold} on the local feature set.
b. Communicate local best splits with each other and get the best one.
c. Perform the best split.
（2）数据并⾏：
a. Instead of “Merge global histograms from all local histograms”, LightGBM use “Reduce Scatter” to
merge histograms of different (non-overlapping) features for different workers. Then workers find the local best split on local merged histograms and sync up the global best split.
b. As aforementioned, LightGBM uses histogram subtraction to speed up training. Based on this, we can communicate histograms only for one leaf, and get its neighbor’s histograms by subtraction as well.
（3）投票并⾏：
Voting parallel further reduces the communication cost in data-parallel to constant cost. It uses two-stage voting to reduce the communication cost of feature histograms.
常见问题
LightGBM和XGBoost有什么区别？他们的loss⼀样么？ 算法层⾯有什么区别？
答：LightGBM：基于Histogram的决策树算法；Leaf-wise的叶⼦⽣长策略；Cache命中率优化；直接⽀持类别特征（categorical Feature）；XGBoost：预排序；Level-wise的层级⽣长策略；特征对梯度的访问是⼀种随机访问。
LightGBM有哪些实现，各有什么区别？
答：gbdt：梯度提升决策树，串⾏速度慢，容易过拟合；rf：随机森林，并⾏速度快；dart：训练较慢；goss：容易过拟合。
LigthGBM是boosting集合模型中的新进成员，由微软提供，它和XGBoost⼀样是对GBDT的⾼效实现，原理上它和GBDT及XGBoost类似，都采⽤损失函数的负梯度作为当前决策树的残差近似值，去拟合新的决策树。
LightGBM树的⽣长⽅式是垂直⽅向的，其他的算法都是⽔平⽅向的，也就是说Light GBM⽣长的是树的叶⼦，其他的算法⽣长的是树的层次。
LightGBM选择具有最⼤误差的树叶进⾏⽣长，当⽣长同样的树叶，⽣长叶⼦的算法可以⽐基于层的算法减少更多的loss。
不建议在⼩数据集上使⽤LightGBM。LightGBM对过拟合很敏感，对于⼩数据集⾮常容易过拟合。对于多⼩属于⼩数据集，并没有什么阈值，但是从我的经验，我建议对于10000+以上的数据的时候，再使⽤LightGBM。
LightGBM在很多⽅⾯会⽐XGBoost表现的更为优秀。它有以下优势：
更快的训练效率
低内存使⽤
更⾼的准确率
⽀持并⾏化学习
可处理⼤规模数据
⽀持直接使⽤category特征
从下图实验数据可以看出， LightGBM⽐XGBoost快将近10倍，内存占⽤率⼤约为XGBoost的1/6，并且准确率也有提升。
⾄于LGB为什么⽐XGB的精度⾼这⼀点，我的理解是选择梯度⼤(残差⼤)样本来进⾏特征分裂⽣成的树，借鉴了Adaboost的更改样本权重的思想。每棵树针对某些特定训练样本有着较好的划分能⼒，导致每棵树之间的异质性较⼤，对于效果近似但异质性⼤的模型加权往往会带来更⼤的提升。
通俗解释：LGB的优化⽅法是，在保留⼤梯度样本的同时，随机地保留⼀些⼩梯度样本，同时放⼤了⼩梯度样本带来的信息增益。
这样说起来⽐较抽象，我们过⼀遍流程： ⾸先把样本按照梯度排序，选出梯度最⼤的a%个样本，然后在剩下⼩梯度数据中随机选取b%个样本，在计算信息增益的时候，将选出来b%个⼩梯度样本的信息增益扩⼤ 1 - a / b 倍。这样就会避免对于数据分布的改变。
这给我的感觉就是⼀个公寓⾥本来住了⼗个⼈，感觉太挤了，赶⾛了六个⼈，但剩下的四个⼈要分摊他们六个⼈的房租。
举个例⼦，对于⼀列特征[1,nan,1,nan,1]和⼀列特征[nan,1,nan,1,nan]，他们正好可以合并成⼀列特征[1,2,1,2,1]。LGB的⽬标就是在于到这样的特征并且将他们合并在⼀起。
如果把特征抽象成图中的点，特征之间的冲突看作是图中的边，那么问题就转换为出图中的社团并使图中的社团数量最少。LGB⾥提出了⼀个贪⼼的策略，按照有权度来为图中所有的点排序，然后把特征合并到度⼩于某个阈值的社团中或单独创建⼀个社团。
对于特征如何合并，⼀个重要的原则就是使合并的两个特征可以被顺利区分出来，LGB采取了⼀个更改阈值的⽅法。例如对于特征x∈(0, 10)， 特征y∈(0, 20)，就可以把特征y转换为y∈(10,30)，然后再去合并x与y。
看完这些惊⼈的实验结果以后，对下⾯两个问题产⽣了疑惑：XGBoost已经⼗分完美了，为什么还要追求速度更快、内存使⽤更⼩的模型？对GBDT算法进⾏改进和提升的技术细节是什么？
提出LightGBM的动机
常⽤的机器学习算法，例如神经⽹络等算法，都可以以mini-batch的⽅式训练，训练数据的⼤⼩不会受到内存限制。⽽GBDT在每⼀次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的⼤⼩；如果不装进内存，反复地读写训练数据⼜会消耗⾮常⼤的时间。尤其⾯对⼯业级海量的数据，普通的GBDT算法是不能满⾜其需求的。
LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地⽤于⼯业实践。
XGBoost的优缺点
精确贪⼼算法
每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的⼤⼩；如果不装进内存，反复地读写训练数据⼜会消耗⾮常⼤的时间。
优点：
可以到精确的划分条件
缺点：
计算量巨⼤
内存占⽤巨⼤
易产⽣过拟合
Level-wise迭代⽅式
预排序⽅法（pre-sorted）：⾸先，空间消耗⼤。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点，在这⾥XGBoost采⽤了特征粒度的并⾏化），这⾥需要消耗训练数据两倍的内存。其次时间上也有较⼤的开销，在遍历每⼀个分割点的时候，都需要进⾏分裂增益的计算，消耗的代价⼤。
优点：
可以使⽤多线程
可以加速精确贪⼼算法
缺点：
效率低下，可能产⽣不必要的叶结点
对cache优化不友好
在预排序后，特征对梯度的访问是⼀种随机访问，并且不同的特征访问的顺序不⼀样，⽆法对cache进⾏优化。同时，在每⼀层长树的时候，需要随机访问⼀个⾏索引到叶⼦索引的数组，并且不同特征访问的顺序也不⼀样，也会造成较⼤的cache miss。
LightGBM在哪些地⽅进⾏了优化？
概括来说，lightGBM主要有以下特点：
基于Histogram的决策树算法
带深度限制的Leaf-wise的叶⼦⽣长策略
直⽅图做差加速
直接⽀持类别特征(Categorical Feature)
Cache命中率优化
基于直⽅图的稀疏特征优化
多线程优化
XGBoost使⽤的是pre-sorted算法，能够更精确的到数据分隔点。
⾸先，对所有特征按数值进⾏预排序。
其次，在每次的样本分割时，⽤O(# data)的代价到每个特征的最优分割点。
最后，到最后的特征以及分割点，将数据分裂成左右两个⼦节点。
这种pre-sorting算法能够准确到分裂点，但是在空间和时间上有很⼤的开销。
由于需要对特征进⾏预排序并且需要保存排序后的索引值（为了后续快速的计算分裂点），因此内存需要训练数据的两倍。
在遍历每⼀个分割点的时候，都需要进⾏分裂增益的计算，消耗的代价⼤。
LightGBM使⽤的是histogram算法，占⽤的内存更低，数据分隔的复杂度更低。其思想是将连续的浮点特征离散成k个离散值，并构造宽度为k的Histogram。然后遍历训练数据，统计每个离散值在直⽅图中的累计统计量。在进⾏特征选择时，只需要根据直⽅图的离散值，遍历寻最优的分割点。
使⽤直⽅图算法有很多优点。⾸先最明显就是内存消耗的降低，直⽅图算法不仅不需要额外存储预排序的结果，⽽且可以只保存特征离散化后的值，⽽这个值⼀般⽤8位整型存储就⾜够了，内存消耗可以降低为原来的1/8。
Histogram algorithm
Histogram algorithm应该翻译为直⽅图算法，直⽅图算法的思想也很简单，⾸先将连续的浮点数据转换为bin数据，具体过程是⾸先确定对于每⼀个特征需要多少的桶bin，然后均分，将属于该桶的样本数据更新为bin的值，最后⽤直⽅图表⽰。（看起来很⾼⼤上，其实就是直⽅图统计，最后我们将⼤规模的数据放在了直⽅图中）
直⽅图算法有⼏个需要注意的地⽅：
使⽤bin替代原始数据相当于增加了正则化；
使⽤bin意味着很多数据的细节特征被放弃了，相似的数据可能被划分到相同的桶中，这样的数据之间的差异就消失了；
bin数量选择决定了正则化的程度，bin越少惩罚越严重，⽋拟合风险越⾼。
直⽅图算法需要注意的地⽅：
构建直⽅图时不需要对数据进⾏排序（⽐XGBoost快），因为预先设定了bin的范围；
直⽅图除了保存划分阈值和当前bin内样本数以外还保存了当前bin内所有样本的⼀阶梯度和（⼀阶梯度和的平⽅的均值等价于均⽅损失）；阈值的选取是按照直⽅图从⼩到⼤遍历，使⽤了上⾯的⼀阶梯度和，⽬的是得到划分之后△loss最⼤的特征及阈值。
Histogram 算法的优缺点：
Histogram算法并不是完美的。由于特征被离散化后，到的并不是很精确的分割点，所以会对结果产
⽣影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不⼤，甚⾄会好⼀些。原因在于decision tree本⾝就是⼀个弱学习器，采⽤Histogram算法会起到正则化的效果，有效地防⽌模型的过拟合。
时间上的开销由原来的O(#data * #features)降到O(k * #features)。由于离散化，#bin远⼩于#data，因此时间上有很⼤的提升。Histogram算法还可以进⼀步加速。⼀个叶⼦节点的Histogram可以直接由⽗节点的Histogram和兄弟节点的Histogram做差得到。⼀般情况下，构造Histogram需要遍历该叶⼦上的所有数据，通过该⽅法，只需要遍历Histogram的k个捅。速度提升了⼀倍。
决策树⽣长策略
在Histogram算法之上，LightGBM进⾏进⼀步的优化。⾸先它抛弃了⼤多数GBDT⼯具使⽤的按层⽣长 (level-wise)的决策树⽣长策略，⽽使⽤了带有深度限制的按叶⼦⽣长 (leaf-wise)算法。
XGBoost采⽤的是按层⽣长level（depth）-wise⽣长策略，能够同时分裂同⼀层的叶⼦，从⽽进⾏多线程优化，不容易过拟合；但不加区分的对待同⼀层的叶⼦，带来了很多没必要的开销。因为实际上很多叶⼦的分裂增益较低，没必要进⾏搜索和分裂。
LightGBM采⽤leaf-wise⽣长策略，每次从当前所有叶⼦中到分裂增益最⼤（⼀般也是数据量最⼤）的⼀个叶⼦，然后分裂，如此循环。因此同Level-wise相⽐，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出⽐较深的决策树，产⽣过拟合。因此LightGBM在Leaf-wise之上增加了⼀个最⼤深度的限制，在保证⾼效率的同时防⽌过拟合。
直⽅图差加速
LightGBM另⼀个优化是Histogram（直⽅图）做差加速。⼀个容易观察到的现象：⼀个叶⼦的直⽅图可以由它的⽗亲节点的直⽅图与它兄弟的直⽅图做差得到。通常构造直⽅图，需要遍历该叶⼦上的所有数据，但直⽅图做差仅需遍历直⽅图的k个桶。利⽤这个⽅
法，LightGBM可以在构造⼀个叶⼦的直⽅图后，可以⽤⾮常微⼩的代价得到它兄弟叶⼦的直⽅图，在速度上可以提升⼀倍。
直接⽀持类别特征
实际上⼤多数机器学习⼯具都⽆法直接⽀持类别特征，⼀般需要把类别特征，转化one-hotting特征，降低了空间和时间的效率。⽽类别特征的使⽤是在实践中很常⽤的。基于这个考虑，LightGBM优化了
对类别特征的⽀持，可以直接输⼊类别特征，不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。
one-hot编码是处理类别特征的⼀个通⽤⽅法，然⽽在树模型中，这可能并不⼀定是⼀个好的⽅法，尤其当类别特征中类别个数很多的情况下。主要的问题是：
可能⽆法在这个类别特征上进⾏切分（即浪费了这个特征）。使⽤one-hot编码的话，意味着在每⼀个决策节点上只能使⽤one vs
rest（例如是不是狗，是不是猫等）的切分⽅式。当类别值很多时，每个类别上的数据可能会⽐较少，这时候切分会产⽣不平衡，这意味着切分增益也会很⼩（⽐较直观的理解是，不平衡的切分和不切分没有区别）。
会影响决策树的学习。因为就算可以在这个类别特征进⾏切分，也会把数据切分到很多零碎的⼩空间上，如图1左边所⽰。⽽决策树学习时利⽤的是统计信息，在这些数据量⼩的空间上，统计信息不准确，学习会变差。但如果使⽤下图右边的分裂⽅式，数据会被切分到两个⽐较⼤的空间，进⼀步的学习也会更好。
下图右边叶⼦节点的含义是X=A或者X=C放到左孩⼦，其余放到右孩⼦。
LightGBM处理分类特征⼤致流程
为了解决one-hot编码处理类别特征的不⾜。LightGBM采⽤了Many vs many的切分⽅式，实现了类别特征的最优切分。⽤LightGBM可以直接输⼊类别特征，并产⽣上图右边的效果。在1个k维的类别特征中寻最优切分，朴素的枚举算法的复杂度是O(2k)，⽽LightGBM采⽤了如On Grouping For Maximum Homogeneity的⽅法实现了O(klogk)的算法。
算法流程下图所⽰：在枚举分割点之前，先把直⽅图按每个类别的均值进⾏排序；然后按照均值的结果依次枚举最优分割点。从下图可以看到，Sum(y)/Count(y)为类别的均值。当然，这个⽅法很容易过拟合，所以在LGBM中加⼊了很多对这个⽅法的约束和正则化。
下图是⼀个简单的对⽐实验，可以看到该最优⽅法在AUC上提升了1.5个点，并且时间只多了20%。
下⾯具体来讲下在代码中如何求解类别特征的最优切分的流程：
离散特征建⽴直⽅图的过程：统计该特征下每⼀种离散值出现的次数，并从⾼到低排序，并过滤掉出现次数较少的特征值, 然后为每⼀个特征值，建⽴⼀个bin容器, 对于在bin容器内出现次数较少的特征值直接过滤掉，不建⽴bin容器。
计算分裂阈值的过程：
先看该特征下划分出的bin容器的个数，如果bin容器的数量⼩于4，直接使⽤one vs other⽅式, 逐个扫描每⼀个bin容器，出最佳分裂点；对于bin容器较多的情况, 先进⾏过滤，只让⼦集合较⼤的bin容器参加划分阈值计算, 对每⼀个符合条件的bin容器进⾏公式计算:
公式如下: 该bin容器下所有样本的⼀阶梯度之和/该bin容器下所有样本的⼆阶梯度之和 + 正则项(参数cat_smooth)
这⾥为什么不是label的均值呢？其实上例中只是为了便于理解，只针对了学习⼀棵树且是回归问题的情况， 这时候⼀阶导数是Y, ⼆阶导数是1)，得到⼀个值，根据该值对bin容器从⼩到⼤进⾏排序，然后分从左到右、从右到左进⾏搜索，得到最优分裂阈值。但是有⼀点，没有搜索所有的bin容器，⽽是设定了⼀个搜索bin容器数量的上限值，程序中设定是32，即参数max_num_cat。LightGBM中对离散特征实⾏的是many vs many 策略，这32个bin中最优划分的阈值的左边或者右边所有的bin容器就是⼀个many集合，⽽其他的bin容器就是另⼀个many集合。
对于连续特征，划分阈值只有⼀个，对于离散值可能会有多个划分阈值，每⼀个划分阈值对应着⼀个bin容器编号，当使⽤离散特征进⾏分裂时，只要数据样本对应的bin容器编号在这些阈值对应的bin集合之中，这条数据就加⼊分裂后的左⼦树，否则加⼊分裂后的右⼦树。
直接⽀持⾼效并⾏
LightGBM原⽣⽀持并⾏学习，⽬前⽀持特征并⾏和数据并⾏的两种。特征并⾏的主要思想是在不同机器在不同的特征集合上分别寻最优的分割点，然后在机器间同步最优的分割点。数据并⾏则是让不同的机器先在本地构造直⽅图，然后进⾏全局的合并，最后在合并的直⽅图上⾯寻最优分割点。
LightGBM针对这两种并⾏⽅法都做了优化，在特征并⾏算法中，通过在本地保存全部数据避免对数据切分结果的通信；在数据并⾏中使⽤分散规约(Reduce scatter)把直⽅图合并的任务分摊到不同的机器，降低通信和计算，并利⽤直⽅图做差，进⼀步减少了⼀半的通信量。
基于投票的数据并⾏则进⼀步优化数据并⾏中的通信代价，使通信代价变成常数级别。在数据量很⼤的时候，使⽤投票并⾏可以得到⾮常好的加速效果。
⽹络通信优化
XGBoost由于采⽤pre-sorted算法，通信代价⾮常⼤，所以在并⾏的时候也是采⽤histogram算法；LightGBM采⽤的histogram算法通信代价⼩，通过使⽤集合通信算法，能够实现并⾏计算的线性加速。
LightGBM原理
提升树是利⽤加模型与前向分布算法实现学习的优化过程，它有⼀些⾼效实现，如XGBoost, pGBRT，GBDT(Gradient Boosting Decision Tree)等。其中GBDT采⽤负梯度作为划分的指标（信息增益），XGBoost则利⽤到⼆阶导数。他们共同的不⾜是，计算信息增益需要扫描所有样本，从⽽到最优划分点。在⾯对⼤量数据或者特征维度很⾼时，它们的效率和扩展性很难使⼈满意。解决这个问题的直接⽅法就是减少特征量和数据量⽽且不影响精确度，有部分⼯作根据数据权重采样来加速booisting的过程，但由于GBDT没有样本权重不能应⽤。
结合使⽤ GOSS 和 EFB 的 GBDT 算法就是 LightGBM。微软开源的LightGBM（基于GBDT的）则很好的解决这些问题，它主要包含两个算法：
单边梯度采样，Gradient-based One-Side Sampling（GOSS）
GOSS（从减少样本⾓度）：排除⼤部分⼩梯度的样本，仅⽤剩下的样本计算信息增益。GBDT虽然没有数据权重，但每个数据实例有不同的梯度，根据计算信息增益的定义，梯度⼤的实例对信息增益有更⼤的影响，因此在下采样时，我们应该尽量保留梯度⼤的样本（预先设定阈值，或者最⾼百分位间），随机去掉梯度⼩的样本。我们证明此措施在相同的采样率下⽐随机采样获得更准确的结果，尤其是在信息增益范围较⼤时。
GBDT使⽤决策树，来学习获得⼀个将输⼊空间映射到梯度空间的函数。假设训练集有n个实例x1,…,xn，特征维度为s。每次梯度迭时，模型数据变量的损失函数的负梯度⽅向表⽰为g1,…,gn，决策树通过最优切分点（最⼤信息增益点）将数据分到各个节点。GBDT通过分割后的⽅差衡量信息增益。
GOSS是⼀种在减少数据量和保证精度上平衡的算法。GOSS是通过区分不同梯度的实例，保留较⼤梯度实例同时对较⼩梯度随机采样的⽅式减少计算量，从⽽达到提升效率的⽬的。

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